Степени вхождения простых

Подсказка 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 после каждого шага увеличивается вдвое. Осталось показать, что не существует двух различных последовательностей из 2n идущих подряд чисел таких, что отношение сумм их квадратов равно степени двойки. Каким способом это возможно сделать?

Подсказка 7

Мы можем показать, что степень вхождения двойки в сумму квадратов 2n последовательных чисел является инвариантом для данного n. Для этого можно явно показать, как степень вхождения двойки в рассматриваемую сумму зависит от n.

Подсказка 8

Пусть 2n=l*2^k, где l - нечетное натуральное число, k - натуральное число, не меньшее 1. Докажите, что степень вхождения двойки в сумму квадратов 2n последовательных чисел равна k-1.

Подсказка 9

Искомую сумму можно представить как l сумм 2^k последовательных квадратов натуральных чисел. Если мы докажем, что каждая из них имеет вид 2^{k-1}t, для некоторого нечетного числа t, то явно получим, что и вся сумма делится на 2^{k-1}, но не делится на 2^k. Сделайте это!

Подсказка 10

Рассмотрим сумму последовательных 2^k квадратов по модулю 2^k. Квадраты этих чисел имеют тот же набор остатков при делении на 2k, что и набор чисел 1², 2², 3²,..., (2^k)², а значит сравнимо по этому модулю c суммой 1²+2²+...+(2^k)². Каким образом ее можно преобразовать?

Подсказка 11

По известной формуле суммы квадратов первых n чисел, 1²+2²+...+(2^k)²=2^{k-1}(2^k+1)(2^{k+1}+1)/3 - кратно 2^{k-1}, но не кратно 2^k. Это как раз то, что мы хотели показать!