ВСОШ 2025, 9 класс, задача 4
( баллов) В каждой клетке доски лежит по рублёвой монете. Даша и Соня играют, делая ходы по очереди, начинает Даша. За один ход можно выбрать любую монету и передвинуть её: Даша двигает монету на соседнюю по диагонали клетку, Соня — на соседнюю по стороне. Если две монеты оказываются в одной клетке, одна из них тут же снимается с доски и достаётся Соне. Соня может остановить игру в любой момент и забрать все полученные деньги. Найдите, какой наибольший выигрыш она может получить, как бы ни играла Даша.
(А. Кузнецов)
Ответ
Ответ. .
Решение. Сначала приведём стратегию за Соню. Пока она не получила больше монет, перед её ходом на доске остаётся хотя бы монета. Разобьём доску на квадратов . Получается, что какие-то две монеты лежат в одном и том же квадрате . Если эти две монеты соседние по стороне, то Соня надвигает одну на другую и получает ещё одну монету. Если они стоят по диагонали, то Соня сдвигает одну из них в столбец к другой (здесь и далее столбец имеет длину , строка — длину ). Теперь, какой бы ход ни сделала Даша, эти две монетки всё ещё будут соседними по стороне (либо одна будет снята и уйдёт в доход Сони), значит, своим следующим ходом Соня сможет получить ещё одну монетку. Таким образом, Соня всегда сможет увеличивать свой выигрыш, пока он меньше .
Теперь покажем, как играть за Дашу, чтобы Соня не получила больше монет. Пронумеруем столбцы числами от до по порядку, выберем в каждом нечётном столбце по одной монетке и мысленно покрасим их в красный цвет. Даше достаточно обеспечить, чтобы красные монетки всегда оставались на доске. Для этого, в свою очередь, достаточно, чтобы две красные монеты никогда не попадали в одну клетку, потому что когда в клетку попадают красная и не красная монеты, можно считать, что с доски снимается не красная.
Назовём расположение монет на доске стабильным, если по одной красной монете лежит в столбцах , , , , , а ещё одна располагается в одном из двух последних столбцов , . Легко видеть, что после любого хода из стабильной позиции две красные монеты не окажутся в одной клетке. Даша будет играть так, чтобы после каждого её хода получалась стабильная позиция. Если после хода Сони позиция осталась стабильной, то Даша двигает сотую красную фишку между двумя последними столбцами, так же Даша поступит и своим первым ходом. Если же после хода Сони позиция перестала быть стабильной, то Соня подвинула одну из красных монет из некоторого столбца в соседний столбец. Тогда Даша своим ходом вернёт её в столбец . Таким образом, на доске всегда останется хотя бы монет, и Соня заработает не более трёхсот рублей.
Решение разбивается на две части: (A) — стратегия за Соню, (B) — стратегия за Дашу. Баллы, набранные за разные части, суммируются.
(A) Полная стратегия за Соню с обоснованием.
Эта часть состоит из трёх шагов:
(A1) Указано, что пока на столе есть хотя бы монета, то какие-то две монеты располагаются в двух соседних строках и столбцах.
(A2) Показано, что Соня может забрать себе одну монету, когда две монеты лежат в соседних клетках.
(A3) Показано, что Соня может забрать себе одну монету за два хода, если они лежат в соседних по диагонали клетках.
Ситуация 1. В решении есть формулировки всех трёх шагов (A1)–(A3) с необходимыми логическими связями между ними, но ошибка допущена в одном из пунктов.
Примеры возможных ошибок.
Ошибка в (A1): неверное доказательство утверждения (например, с использованием «худшего случая»).
Ошибки в (A3). Во-первых, может быть сказано, что Соня ходит одной монетой просто в клетку, соседнюю с другой (а не в клетку того же столбца) — такая стратегия не работает. Во-вторых, после хода в соседний столбец может быть разобран лишь один из случаев, в котором Даша двигает или не двигает одну из монет.
Ситуация 1. В решении есть формулировки всех трёх шагов (A1)–(A3) с необходимыми логическими связями между ними, но ошибки допущены хотя бы в двух шагах.
Ситуация 2. В решении нет одного из шагов (A1), (A2), (A3), но есть любые два из этих шагов или лишь шаг (A3).
Ситуация 2. В решении нет одного из шагов (A1), (A2), (A3) и не выполнено условие предыдущего критерия.
(B) Стратегия за Дашу с обоснованием.
(B0) Лишь идея сохранять все красные монеты.
(B1) Стратегия с возвратом монеты в тот же столбец, которая не работает, если Соня подвинула красную монету, не меняя её столбца.