Назад
Задача

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

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет