ММО 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.