Задача 66573

Темы:    [ Числовые последовательности (прочее) ] [ Теория чисел. Делимость (прочее) ]

Сложность: 4 Классы: 9,10,11

Условие

Автор: Грибалко А.В.

На доске написаны $2n$ последовательных целых чисел. За ход можно разбить написанные числа на пары произвольным образом и каждую пару чисел заменить на сумму и разность чисел этой пары (не обязательно вычитать из большего числа меньшее; все замены происходят одновременно). Докажите, что на доске больше никогда не появятся $2n$ последовательных чисел.

Решение

Рассмотрим набор из $2^k$ подряд идущих чисел, квадраты этих чисел имеют тот же набор остатков при делении на $2^{k}$, что и набор чисел $1^2$, $2^2$, $3^2$, $\ldots,$ $(2^k)^2$. Поскольку

$$\begin{align*} 1^2&+2^2 +3^2+\ldots + (2^{k})^2=\\ &=\frac{2^k(2^k+1)(2\cdot2^k+1)}6=\\ &=2^{k-1}\frac{(2^k+1)(2\cdot2^k+1)}3, \end{align*}$$ сумма квадратов $2^k$ подряд идущих чисел делится на $2^{k-1}$, но не делится на $2^k$.

Представим число $2n$ в виде $2^k\cdot l$, где $l$ нечётно. Тогда сумма $2n$ последовательных квадратов разбивается на $l$ сумм вида $2^{k-1}t_i$, где все $t_i$ нечётны, поэтому вся сумма также делится на $2^{k-1}$, но не делится на $2^k$. Следовательно, наибольшая степень двойки, на которую делится сумма квадратов $2n$ последовательных чисел, зависит только от $n$, но не от самих чисел.

В то же время сумма квадратов имеющихся чисел после замены удваивается. Действительно, заменив числа $a$ и $b$ на $a-b$ и $a+b$, получим:

$$(a-b)^2+(a+b)^2=2a^2+2b^2=2(a^2+b^2).$$ Таким образом, снова получить набор из $2n$ подряд идущих чисел нельзя.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	83
Год	2020
класс
Класс	11
задача
Номер	6