|
|
 |
Условие
На доске написаны $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$ подряд идущих чисел нельзя.
