Задача 4. Монеты Даши и Сони

Что считать и что доказать

Когда две монеты оказываются в одной клетке, одна из них уходит Соне — неважно, чей это был ход: Даши или самой Сони. Каждая встреча снимает с доски ровно одну монету. Поэтому в любой момент выигрыш Сони равен $400$ минус число монет на доске: чем меньше монет осталось, тем больше у Сони.

Значит, нужны два доказательства:

• Соня может, как бы ни играла Даша, довести число монет до $100$ и остановиться — тогда у неё $400 - 100 = 300$ рублей;

• Даша может, как бы ни играла Соня, сделать так, чтобы на доске всегда было не меньше $100$ монет, — тогда больше $300$ рублей Соня не получит.

Договоримся о словах. Пронумеруем столбцы слева направо: 1, 2, …, 200. Клетки соседние по стороне, если они в одном столбце (одна над другой) или в одной строке в соседних столбцах. Соседние по диагонали — в разных строках и в соседних столбцах. Если две монеты стоят в соседних по стороне клетках, Соня сразу ставит одну на другую и забирает монету.

Откуда берётся число $100$. Если любые две монеты стоят через столбец — не в одном столбце и не в соседних, — то соседей по стороне нет и Соне сразу ловить нечего. Столбцов $200$, и через один можно занять не больше $100$ из них (например, столбцы 1, 3, …, 199). Ниже увидим, что именно эта граница и решает игру.

Стратегия Даши: монет всегда не меньше 100

Разобьём столбцы на $100$ «домиков»: $99$ домиков — это отдельные нечётные столбцы 1, 3, 5, …, 197, а сотый домик — пара столбцов $199$ и $200$. Остальные столбцы 2, 4, …, 198 назовём свободными (рисунок ниже).

Правило Даши: перед каждым ходом Сони в каждом домике лежит хотя бы одна монета.

Сначала поймём, почему этого хватает. Домиков $100$, значит, перед ходом Сони монет не меньше $100$. Ход Сони снимает не больше одной монеты. Если монет хотя бы $101$, после её хода их останется не меньше $100$. Если монет ровно $100$, то в каждом домике по одной, а свободные столбцы пусты. Тогда номера столбцов любых двух монет отличаются хотя бы на $2$: соседние домики — столбцы через один, а монета последнего домика стоит в столбце $199$ или $200$, на расстоянии не меньше $2$ от столбца $197$. Значит, соседних по стороне монет нет, и Соня ничего не снимет.

Теперь — как Даше отвечать на любой ход Сони, чтобы правило снова выполнялось. Разберём случаи по порядку.

Случай 1: Соня вывела из домика его единственную монету. Ход вверх или вниз не меняет столбец, а ход между столбцами $199$ и $200$ не выводит из последнего домика. Значит, Соня сдвинула монету вбок, в соседний столбец, — а он свободный (или это столбец $198$, тоже свободный). Даша берёт монету, которая теперь стоит в этой клетке (если там случилась встреча, монета там одна), и возвращает её по диагонали в опустевший домик, в другую строку. Эта клетка пуста — ведь домик опустел, — поэтому встречи нет и монет не становится меньше.

Случай 2: все домики заняты, а в каком-то свободном столбце есть монета. Даша сдвигает её по диагонали в соседний столбец. Оба соседа свободного столбца нечётные, то есть это домики, и ни один домик не пустеет. Если при этом монеты встретились, то монет было хотя бы $101$: по одной в каждом из $100$ домиков и ещё эта. Значит, останется не меньше $100$.

Случай 3: свободные столбцы пусты, но в каком-то домике две монеты. Если это столбец $c$, где $c \le 197$, Даша сдвигает одну из двух монет по диагонали в столбец $c + 1$ — он свободный и пустой, встречи нет, а в домике остаётся вторая монета. Если это последний домик, Даша сдвигает одну из его монет по диагонали между столбцами $199$ и $200$: домик не пустеет, а возможная встреча не страшна — монет было хотя бы $101$.

Случай 4: в каждом домике ровно одна монета, свободные столбцы пусты. Здесь Даше нужно просто «потянуть время»: ходить она обязана, но любая монета из одностолбцового домика, сдвинувшись, его опустошит. Для этого последнему домику и нужны два столбца: Даша сдвигает его монету по диагонали из столбца $199$ в столбец $200$ или обратно. Клетка пуста (монета в домике одна), домик не пустеет.

Остался первый ход. Доска полна, поэтому любой ход Даши — встреча, и Соня сразу получает $1$ рубль. Даша сдвигает монету из столбца $2$ в столбец $1$: все домики по-прежнему заняты.

Итак, монет на доске никогда не становится меньше $100$, и Соня не может получить больше $400 - 100 = 300$ рублей.

Ловушка Сони: две монеты в одном столбце

Пусть перед ходом Даши две монеты стоят в одном столбце, одна над другой. Может ли Даша одним ходом их развести?

Монета, сдвинутая по диагонали, уходит в другую строку и в соседний столбец. Если Даша двигает верхнюю монету, та попадает в нижнюю строку — в клетку рядом с нижней монетой. Если нижнюю — в верхнюю строку, рядом с верхней (рисунок ниже). В обоих случаях монеты снова соседи по стороне. А если Даша двигает какую-то другую монету, эти две так и стоят одна над другой. Значит, следующим ходом Соня ставит одну из них на другую и забирает монету. Если же Даша сама устроит встречу, Соня получит монету ещё раньше.

Отсюда главное следствие: если перед ходом Сони две монеты стоят в одном столбце или в соседних столбцах, Соня получит монету не позже чем через два своих хода. Действительно:

• две монеты в одном столбце или в одной строке в соседних столбцах — соседи по стороне, и Соня сразу ставит одну на другую;

• две монеты в соседних столбцах, но в разных строках (по диагонали) — Соня сдвигает одну из них вбок, в столбец другой. Получается ловушка: монеты одна над другой. (Если клетка, куда Соня сдвигает монету, уже занята, монеты встречаются сразу — тем лучше.)

Как это заметить: в модели сыграй за Дашу и попробуй развести две монеты одного столбца — ни один из четырёх ходов не помогает (кнопка «Пример: ловушка в одном столбце» показывает это по кадрам).

Стратегия Сони: не меньше 300

Разобьём доску на $100$ квадратов $2\times2$: столбцы $1$ и $2$, $3$ и $4$, …, $199$ и $200$ (рисунок ниже). Пусть перед ходом Сони на доске хотя бы $101$ монета. Квадратов всего $100$, поэтому в каком-то квадрате лежат хотя бы две монеты (принцип Дирихле). Любые две клетки квадрата $2\times2$ стоят в одном столбце или в соседних столбцах — и по шагу 3 Соня получает монету не позже чем через два своих хода.

Соня повторяет это, пока монет больше $100$. Каждая встреча снимает ровно одну монету, поэтому число монет уменьшается по одному: $399$, $398$, … — и в какой-то момент станет ровно $100$. Затянуть игру бесконечно Даша не может: пока монет хотя бы $101$, каждые два хода Сони приносят ей монету.

Когда монет осталось $100$, Соня останавливает игру. С доски снято $400 - 100 = 300$ монет, и все они у Сони.

Ответ: 300 рублей

Соня умеет получить $300$ рублей при любой игре Даши (шаг 4), а Даша умеет не дать ей больше $300$ (шаг 2). Значит, наибольший выигрыш, который Соня может себе гарантировать, — $300$ рублей.

Обе стратегии держатся на одной картинке: две монеты в одном или в соседних столбцах — добыча Сони, монеты через столбец — защита Даши. На $200$ столбцах через столбец помещается ровно $100$ монет. Те же рассуждения работают для любой доски $2\times n$ с чётным $n$: Соня забирает $\frac{3n}{2}$ монет, а $\frac n2$ остаются. В модели на доске $2\times6$ это $9$ монет из $12$.