ВсОШ 2026, 11 класс, задача 8
( баллов) Петя и Вася играют в следующую игру. На доске в каждой клетке лежит по конфет. Петя и Вася по очереди, начиная с Пети, выбирают непустую клетку и съедают из неё несколько конфет. При этом из угловых клеток разрешается съедать не более двух конфет, из клеток, имеющих соседа по стороне, — не более конфет, из всех остальных — не более конфет. Игрок, после чьего хода появляется пустая строка или пустой столбец, побеждает. Для скольких в диапазоне от до у Пети есть выигрышная стратегия?
Ответ
Ответ: .
Решение. Докажем, что при , делящихся на , выигрывает Вася. Стратегия за Васю:
- Если у Васи есть ход, после которого появляется пустая строка или столбец, то он его делает.
- Иначе, если Петя взял из центральной клетки конфет, то Вася берёт из неё конфет.
- Иначе Петя берёт конфет из не центральной клетки. Тогда Вася должен взять конфет из центрально-симметричной клетки.
Заметим, что после каждого хода Васи либо Вася побеждает этим ходом, либо на столе остаётся центрально-симметричная расстановка конфет, в центральной клетке которой количество конфет делится на . Покажем, что это стратегия действительная выигрышная, предположим противное. Тогда после некоторого своего хода выиграл Петя. Рассмотрим его последний ход.
Случай 1. Последний ход Пети был из центральной клетки. Так как перед его ходом в ней было кратное количество конфет, по после хода останется не кратное количество конфет, в частности, не . Таким образом, Петя не мог своим ходом опустошить центральную клетку, и, следовательно, победить.
Случай 2. Последний ход Пети был не в центральную клетку. Рассмотрим ряд, которых после хода Пети стал пустым. Заметим, что этот ряд не может быть центральной строкой или столбцом, так как центрально-симметричная клетка к клетке, из которой был сделан последних ход, не пустая. Рассмотрим ряд, центрально симметричный к ряду, ставшему пустым после хода Пети.
Перед ходом Пети положение конфет в этих рядах было центрально-симметрично, поэтому в любой из этих рядов был выигрышный ход. Своим последних ходом Вася менял не более одного из этих двух рядов. Но тогда у Васи был выигрышный ход в другой из этих рядов, который он и должен был бы сделать, согласно своей стратегии.
Таким образом, при , делящихся на выигрывает Вася. При , не делящихся на , выигрывает Петя: первым ходом он берёт несколько конфет из центральной клетки так, чтобы в ней осталось кратное количество монет; а после играет по описанной выше стратегии. От до ровно чисел, кратных , поэтому у Пети есть выигрышная стратегия для значений .
Верное решение.