Числовые наборы на карточках и досках

Ищем инвариант

Выпишем операцию формально: набор $\{a, b, \dots\}$ переходит в $\{|a-b|, \dots\}$. Количество чисел уменьшается на 1 за каждый ход. За 19 ходов от 20 чисел останется одно.

Посмотри, как меняется сумма всех чисел при одном ходе:

Если $a \geqslant b$, то $|a-b| = a - b$, и $\Delta S = -2b$ - сумма уменьшается на чётное число. Значит, чётность суммы - инвариант.

Начальная сумма: $1 + 2 + \dots + 20 = \dfrac{20 \cdot 21}{2} = 210$. Это чётное число. Значит, и в конце сумма (то есть само последнее число) должна быть чётной.

Пункт а: применяем инвариант

Число 3 - нечётное, а инвариант требует, чтобы итоговое число было чётным. Получить 3 нельзя. Ответ: нет.

Пункт б: строим пример

Число 0 - чётное, запрет инварианта не срабатывает. Нужно построить пример. Разобьём 20 чисел на 10 пар с равной разностью: $(1,2), (3,4), (5,6), \dots, (19,20)$. В каждой паре $|a-b| = 1$. После первых 10 ходов на доске останется десять единиц: $1, 1, 1, \dots, 1$ (10 штук). Далее попарно вычитаем единицы: $|1-1| = 0$. После 5 ходов получим пять нулей. Теперь $|0-0|=0$, и за 4 хода останется один 0. Ответ: да.

Пункт в: оценка плюс пример

Оценка. Покажем, что итог не больше 20. Если $a, b \leqslant M$, то $|a - b| \leqslant \max(a, b) \leqslant M$ - то есть максимум набора никогда не увеличивается. Начальный максимум равен 20, поэтому итоговое число $\leqslant 20$.

Пример. Построим процесс, в котором число 20 сохраняется, а остальные 19 чисел сводятся к нулю.

Шаг 1. Не трогаем 20. Парим соседей: $(2, 3) \to 1$, $(4, 5) \to 1$, $(6, 7) \to 1$, $(8, 9) \to 1$, $(10, 11) \to 1$, $(12, 13) \to 1$, $(14, 15) \to 1$, $(16, 17) \to 1$, $(18, 19) \to 1$. Использовали 18 карточек, получили 9 единиц. Плюс уже имевшаяся 1. На доске: десять единиц и число 20 (9 ходов).

Шаг 2. Пять раз делаем $(1, 1) \to 0$. Получим пять нулей и 20 (5 ходов).

Шаг 3. Четыре раза делаем $(0, 0) \to 0$. Останется одна пара: $\{0, 20\}$ (4 хода).

Шаг 4. $|20 - 0| = 20$. Остаётся одно число 20 (1 ход).

Всего $9 + 5 + 4 + 1 = 19$ ходов, как и должно быть.

Ответ в: 20.

Ищем полуинвариант

Выпишем операцию: пара $(a, b)$ заменяется на пару $(a + b, a - b)$. Количество чисел не меняется (их всегда 10). Посмотрим, какие величины сохраняются.

Сумма квадратов:

Вклад этих двух слагаемых в сумму квадратов удваивается. Значит, после каждого хода сумма квадратов всего набора увеличивается ровно на $a^2 + b^2$ (квадраты стёртых чисел). Поскольку $a^2 + b^2 \geqslant 0$, это полуинвариант: сумма квадратов не убывает.

Начальная сумма квадратов:

Пункт а: подбираем ход

После одного хода сумма изменилась так: вместо $a + b$ в сумме появилось $(a + b) + (a - b) = 2a$. Приращение суммы: $\Delta S = 2a - (a + b) = a - b$. Начальная сумма $1 + 2 + \dots + 10 = 55$. Для итоговой 63 нужно $\Delta S = 8$, то есть $a - b = 8$. Подойдёт пара $a = 9, b = 1$.

Ход: стираем $9$ и $1$, пишем $9 + 1 = 10$ и $9 - 1 = 8$. Новый набор: $\{2, 3, 4, 5, 6, 7, 8, 10, 10, 8\}$ (сортировать не обязательно). Сумма: $55 - 9 - 1 + 10 + 8 = 63$. Условие выполнено. Ответ: да.

Пункт б: применяем полуинвариант

Целевой набор - десять нулей, у него сумма квадратов $Q = 0$. Но $Q$ не убывает при каждом ходе, а в начале $Q_0 = 385 > 0$. Значит, $Q$ всегда $\geqslant 385$, и получить $Q = 0$ невозможно. Ответ: нет.

Пункт в: оценка плюс пример

Оценка. Сумма квадратов не убывает, значит в любой момент $Q \geqslant Q_0 = 385$.

Пример. Начальное состояние уже удовлетворяет $Q = 385$. Если не делать ни одного хода, сумма квадратов равна 385. Задача допускает «любое число ходов», в том числе ноль.

Более того, в любом последующем состоянии $Q \geqslant 385$ и равенство достигается, только когда все $a^2 + b^2 = 0$ на каждом шаге, то есть когда стираемая пара - два нуля. Но в начальном наборе нулей нет, значит любой реальный ход строго увеличивает $Q$. Единственный способ достичь $Q = 385$ - начальное состояние.

Ответ: 385.