Задача 66863

Темы:    [ Индукция (прочее) ] [ Полуинварианты ] [ Выделение полного квадрата. Суммы квадратов ]

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

Условие

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

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

Решение

  По известной формуле  $1^2 + 2^2 + ... + (2n)^2$ = ⅓ $n(n + 1)(4n + 1)$.  Пусть  $m = \frac{n}{НОД(n,3)}$.  Тогда  $1^2 + 2^2 + ... + (2n)^2$  делится на $m$, но не на 2$m$. Это верно не только для суммы квадратов чисел от 1 до 2$n$, но и для суммы квадратов любых 2$n$ последовательных чисел: если из набора 2$n$ последовательных квадратов удалить квадрат в начале и добавить квадрат в конце, то остаток от деления их суммы на 2$m$ не изменится.
  Если $x$ и $y$ заменить на  $x + y$  и  $x - y$,  то  $x^2 + y^2$  заменится на  $(x + y)^2 + (x - y)^2 = 2x^2 + 2y^2$.  Поэтому в итоге сумма квадратов чисел умножается на 2 на каждом шаге. Сумма квадратов исходных чисел делится на $m$, но не делится на 2$m$. Но на каждом шаге сумма квадратов полученных чисел будет делиться на 2$m$, поэтому это не будут последовательные числа.

Замечания

10 баллов

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

олимпиада
Название	Турнир городов
номер/год
Номер	41
Год	2019/20
вариант
Вариант	весенний тур, сложный вариант, 10-11 класс
задача
Номер	6