СПбГУ 2024, 10–11 классы, задача 6

Первое решение. Покажем, что после каждой нетривиальной операции (то есть такой операции, во время которой уменьшалось хотя бы одно число) на доске будут выписаны все последовательные числа от до некоторого (возможно, с повторениями). Это означает, что если какое-то число не выписано, то при этом также не может быть выписано и никакое число, большее . Очевидно, перед самой первой операцией это утверждение верно. Пусть после некоторой операции утверждение также является верным, и сейчас Жора планирует проделать операцию с числом . Если , то в списке чисел на доске ничего не изменится. Если , то числа от до не изменятся, а числа от до превратятся в числа от до . Таким образом, после следующей операции на доске будут выписаны числа от до . Тогда если после операции на доске есть ровно одно ненулевое число, то это именно .

Второе решение. Посмотрим на два числа, которые изначально были последовательными и . Докажем, что если большее из них не станет , то они всегда будут последовательными. Из этого будет следовать решение задачи, если применить его к тому числу, которое в итоге осталось на доске, и числу, которое изначально было на единицу меньше него. Итак, пусть после очередного хода и остаются последовательными числами и . Если следующая операция будет производиться с , то оба числа не изменятся. Если с , то станет , а мы предположили, что это не так. Если же с , то числа превратятся в последовательные числа и .