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