ММО 2020
Ошибка.
Попробуйте повторить позже
На доске написаны последовательных целых чисел. За ход можно разбить написанные числа на пары произвольным образом и
каждую пару чисел заменить на их сумму и разность (не обязательно вычитать из большего меньшее, все замены происходят одновременно).
Докажите, что на доске больше никогда не появятся
последовательных целых чисел.
Источники:
Подсказка 1
Каким способом можно доказать, что состояние фиксированного объекта в процессе его изменения не приведёт к тому, что он примет начальное состояние?
Подсказка 2
Найти полуинвариант! Давайте найдем величину, которая будет меняться монотонно в ходе процесса, и, как следствие, не вернется к изначальному состоянию.
Подсказка 3
Как найти полуинвариант в данной задаче? В условии задачи сказано, что при замене двух чисел x и y на их сумму x+y, второе число равно x-y или y-x. Было бы хорошо, если бы наш полуинвариант вел себя одинаково вне зависимости от этого выбора. Ясно, что данные числа равны по модулю. Как это помогает найти полуинвариант?
Подсказка 4
Пусть S является искомым полуинвариантом. Ясно, что S — это функция от набора чисел, написанных на доске в данный момент. Если мы положим в качестве S функцию от их квадратов, то значение S будет совпадать при выборе любой из разности чисел (x-y или y-x), что является хорошим знаком. Осталось доопределить S.
Подсказка 5
Самые естественные функции от набора переменных — их сумма или произведение. С суммой в данном случае работать проще (итак, в качестве предполагаемого полуинварианта мы пока положим S — сумму квадратов чисел написанных на доске), поскольку мы можем легко получить значения данного полуинварианта на каждом ходу. Поймите, как это можно сделать.
Подсказка 6
Если на доске были написаны числа x² и y², то сумма их квадратов измениться на (x-y)² + (x+y)² = 2(x²+y²). Таким образом, значение S после каждого шага увеличивается вдвое. Осталось показать, что не существует двух различных последовательностей из 1000 идущих подряд чисел таких, что отношение сумм их квадратов равно степени двойки. Каким способом это возможно сделать?
Подсказка 7
Мы можем показать, что степень вхождения двойки в сумму квадратов 1000 последовательных чисел является инвариантом. Можно ли найти ее явно?
Подсказка 8
Да, достаточно доказать, что 8 подряд идущих чисел дают остаток 4 при делении на 8. Пусть эти числа имеют вид n-3, n-2, ..., n+3, n+4 при некотором целом n. Чему равна сумма их квадратов?
Подсказка 9
Сумма квадратов равна 8n² + 8n + 44, дает остаток 4 по модулю 8, а значит, и сумма 1000 последовательных чисел сравнима с 4 по модулю 8, то есть всегда делится на 4 и не делится на 8.
Поскольку то сумма квадратов всех чисел на доске увеличивается в два раза с каждым ходом. Из
формулы
ясно, что сумма квадратов последовательных целых чисел даёт остаток
при делении на
Значит, сумма квадратов
последовательных целых чисел тоже даёт остаток
при делении на
Таким образом, после первого хода сумма квадратов чисел на доске всегда будет делиться на и, следовательно, на доске никогда
больше не появятся
последовательных целых чисел.
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!