Высшая проба 2025, 11 класс, задача 5
( баллов) Саша и Гоша поставили фишек в клетки доски и по очереди ходят. Саша своим ходом может взять две фишки, стоящие в левом верхнем и правом нижнем углу некоторого клетчатого прямоугольника (со сторонами больше ), и поместить их по одной в две другие угловые клетки того же прямоугольника. Гоша своим ходом может передвинуть любую фишку либо вправо вниз, либо влево вверх по диагонали на любое число клеток. Они заканчивают ходить, когда кто-то не может сделать ход. Могут ли они ходить бесконечно?
Ответ. Не могут.
Решение. Запишем в клетки доски положительные целые числа так: число записано в каждой клетке -й диагонали, параллельной главной диагонали, идущей слева сверху вправо вниз (ниже приведен пример для доски ).
Сопоставим каждой конфигурации фишек целочисленную величину , которая равна сумме чисел в клетках, занятых фишками. Тогда не меняется при действиях Гоши. Пусть последовательность быстро растет как функция от , например, . Покажем, что в этом случае строго увеличивается с каждым действием Саши. Пусть Саша выбрал прямоугольник, у которого левая верхняя и правая нижняя клетки имели числа и . Заметим, что в нашей расстановке для всякого числа числа, находящиеся строго ниже и левее него, имеют бо́льшие номера. Поэтому, после хода Саши числа изменятся с и на и , где — высота выбранного прямоугольника, измеренная в клетках (). Тогда , а значит, станет строго больше. При этом, все время остается целочисленным. Так как ограничено сверху (как минимум, оно меньше, чем ), игра не может продолжаться бесконечно
Верное решение.
Решение содержит мелкие неточности, которые легко устранить.
Приведен ограниченный целочисленный полуинвариант, для которого доказано, что ходы Саши меняют его строго в одну сторону.
Приведен полуинвариант, значение которого не меняется при ходах Гоши.
Грубые ошибки в построении полуинварианта.
Решение не соответствует ни одному из критериев выше.