Оценка + пример в задачах по теории чисел
Ошибка.
Попробуйте повторить позже
Дано натуральное число 
Рассмотрим множество всех целых чисел, по модулю не превосходящих 
Какое наибольшее число
элементов можно выбрать из этого множества так, чтобы не нашлось трех различных выбранных чисел 
и 
для которых
Подсказка 1
Для начала попробуйте построить пример. Для этого сделайте так, что сумма любых двух чисел одного знака была по модулю больше n. Какие примеры получаются для четного и нечетного n?
Подсказка 2
Верно! Для четного n можно взять числа n, n - 1, ... n/2 и те же с минусом до -n/2 - 1 (-n/2 не берём!). Для нечетного n возьмем n, n - 1, ... (n+1)/2 и те же с минусом. Пример на n + 1 есть. Осталась оценка. Попробуйте доказать ее по индукции.
Подсказка 3
База очевидна. Поэтому знаем для n = k, что больше, чем k + 1 чисел, выбрать нельзя. Хотим доказать, что для k + 1 нельзя выбрать k + 3 числа. Пусть можно. Какие числа мы тогда должны точно взять?
Подсказка 4
Правильно! По предположению мы должны взять числа k + 1 и - k - 1. Теперь попробуйте разбить числа на пары так, чтобы из каждой пары можно было взять только одно число. Как это сделать для четного k?
Подсказка 5
Верно! Надо взять в пару все числа, которые в сумме дают k + 1 и -(k + 1). Таких пар k, а, значит, взять k + 3 числа не получится. А какие пары для нечетного?
Пример для 
Если 
чётное, то возьмём числа 
и 
Суммы, где оба слагаемых отрицательны
или положительны, по модулю больше 
Cуммы, в которых слагаемые разных знаков, принимают значения из отрезка
![n n
[−2;2 − 1].](/api/latex-service/v1/GetSession/136633/index-f6d5b26c4457edadcf8209ccf146ffd8.svg)
Если 
— нечётное, то возьмём числа 
и 
Суммы, где оба слагаемых одного знака, по модулю
больше 
Суммы, в которых слагаемые разных знаков, принимают значения из отрезка ![n−1 n−1
[− 2 , 2 ].](/api/latex-service/v1/GetSession/136633/index-926f7dbdaef3554d99189d143b27d658.svg)
Теперь докажем оценку на 
по индукции:
База при 
Есть числа 
Если выбрать все, то 
Выбрать 
числа можно.
Переход. Пусть для 
можно выбрать не более 
чисел. Следовательно, если мы хотим для 
взять хотя бы 
числа, мы обязаны взять числа 
и 
потому что среди оставшихся чисел по предположению можно взять не более 
число.
Ясно, что в этом случае 
брать нельзя. Рассмотрим случаи.
Если 
чётно, то разобьём оставшиеся числа на пары: 
и 
— 
штук.
Если из какой-то пары взять оба числа, то их сумма будет 
то есть мы так сделать не сможем. Значит, из каждой пары взято
не более 
числа, то есть суммарно из этих пар взято не более 
чисел. Таким образом, мы выбрали не более 
чисел,
противоречие.
Если 
нечётно, то разобьём так: 
и 
Числа
оставим без пары. Получили 
пару, из каждой можно взять не более 
числа. Также среди чисел 
можно взять не более одного, потому что 
Таким образом, мы взяли не более 
чисел. Оценка
доказана.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
