Урок 5. Игры и стратегии: как гарантированно выиграть

Олимпиадная математика · ~40 минут

Двое играют в игру с чёткими правилами, без случайности, каждый видит всё. Вопрос олимпиады звучит не «кто выиграет, если повезёт», а «кто выиграет при правильной игре обоих». И почти всегда ответ можно доказать — не сыграв ни одной партии, а рассуждая. Это одна из самых красивых тем: ты доказываешь существование непобедимой стратегии.

🎯 Что ты узнаешь

• Что такое выигрышная и проигрышная позиция
• Стратегию симметрии — самый элегантный приём
• Анализ «с конца» (какие позиции проигрышны)
• Игру ним и её связь с двоичной записью

📖 Разбираемся в теме

Выигрышные и проигрышные позиции

Рассматриваем игры двух игроков, ходящих по очереди, без ничьих и случайности, где проигрывает тот, кто не может сделать ход (или, наоборот, кто делает последний ход — оговаривается в условии).

• Проигрышная позиция (П) — та, из которой любой ход ведёт в выигрышную позицию соперника. Кто оказался в ней перед своим ходом — проиграет при правильной игре противника.
• Выигрышная позиция (В) — та, из которой есть ход в проигрышную позицию для соперника.

📌 Запомни: Позиция проигрышна ⇔ все ходы из неё ведут в выигрышные. Позиция выигрышна ⇔ хотя бы один ход ведёт в проигрышную.

Анализ с конца

Конечную позицию (где игра кончилась) мы знаем: она П или В по правилам. Дальше идём назад: помечаем позиции, из которых игра близка к концу, потом всё более ранние. Так размечается вся игра.

💡 Часто проигрышные позиции образуют красивую закономерность (например, «кратно 4»). Найдёшь закономерность — найдёшь стратегию.

Пример: игра «21»

Двое по очереди называют число, прибавляя к текущей сумме от 1 до 3. Начинают с 0. Кто назовёт 21 — победил. Кто выиграет?

Проигрышные для того, кому ходить, суммы: $20$? Нет — из 20 можно взять 1 и получить 21 (победа). Победная сумма — 21. Значит позиции $18, 19, 20$ выигрышны (можно допрыгнуть до 21). А $17$ — проигрышна: что ни возьми (1,2,3), попадёшь в 18/19/20, откуда соперник берёт до 21. Идём назад с шагом 4: проигрышны суммы $\dots, 5, 9, 13, 17$ и, главное, стартовая $\ldots$ проверим: проигрышные для берущего — те, что дают остаток... $21 = 4\cdot5+1$. Проигрышные позиции — суммы, сравнимые с $21 \bmod 4 = 1$: то есть $1,5,9,13,17$ (для того, кому ходить из этой суммы... аккуратнее).

Проще: первый хочет после своего хода оставлять суммы $1,5,9,13,17,21$. Первым ходом он берёт 1 (сумма 1). Дальше на каждый ход соперника (тот прибавил $k\in{1,2,3}$) отвечает так, чтобы шаг был $4$: берёт $4-k$. Так он всегда оставляет $1,5,9,13,17$ и наконец $21$ — и побеждает. Выигрывает первый.

Стратегия симметрии

Иногда второй игрок может копировать ходы первого, сохраняя симметрию, и потому всегда имеет ответный ход — а значит, не проигрывает первым.

🤔 А знаешь ли ты? Классика: двое кладут одинаковые монеты на круглый стол, не накрывая друг друга, кто не может положить — проиграл. Первый кладёт монету в центр, а дальше отражает ходы соперника через центр. У него всегда есть симметричный ответ. Первый выигрывает!

Ним и двоичная запись

Ним: несколько кучек камней, за ход берут любое число (≥1) из одной кучки. Кто взял последний камень — победил.

📌 Теорема о ниме: Позиция проигрышна для того, кому ходить ⇔ «ним-сумма» равна нулю. Ним-сумма — это XOR (сложение по разрядам двоичных записей без переносов) размеров всех кучек.

Например, кучки $3, 5, 6$: в двоичной $011, 101, 110$. Складываем по столбцам без переноса (по модулю 2): получаем $000$. Ним-сумма 0 — позиция проигрышна для того, кто ходит.

⚠️ XOR — это не обычная сумма! $1+1=0$ в каждом разряде (перенос выбрасываем). Именно эта «странная» арифметика и управляет нимом.

✍️ Разбор задачи

Задача. На столе лежат 20 спичек. Двое по очереди берут 1, 2 или 3 спички. Кто возьмёт последнюю — проиграл (это «поддавки»). Кто выигрывает при правильной игре?

Решение. Проигрывает тот, кто вынужден взять последнюю спичку. Значит, «плохо» остаться перед 1 спичкой (придётся взять её). «Хорошо» — оставить сопернику ровно 1 спичку.

Разметим с конца. Пусть перед игроком $n$ спичек.

• $n=1$: проигрыш (берёшь последнюю). П
• $n=2,3,4$: можно оставить сопернику 1 спичку — В.
• $n=5$: что ни возьми (1/2/3), оставишь $4/3/2$ — всё это В для соперника. Значит П.

Видим закономерность: проигрышны позиции $n\equiv 1 \pmod 4$, то есть $n=1,5,9,13,17,\dots$. Стартовая позиция $n=20$: $20 = 4\cdot5$, остаток $0$ — это В для первого игрока.

Стратегия первого: свести число спичек к виду $4k+1$ для соперника. Из 20 берёт 3 → оставляет 17 (это $4\cdot4+1$). Дальше: если соперник взял $t$, первый берёт $4-t$, снова оставляя число вида $4k+1$: $13, 9, 5, 1$. В итоге сопернику остаётся 1 спичка — он вынужден её взять и проигрывает. Выигрывает первый. ∎

📝 Задачи

1. Игра «до 30»: сумма растёт, каждый прибавляет 1–4, кто назовёт 30 — выиграл. Кто победит и какова стратегия?

2. В игре «до 30» поменяли правило: кто назовёт 30 — проиграл. Теперь кто победит?

3. Две кучки по 10 камней. За ход берут любое число камней из одной кучки. Кто взял последний — выиграл. Кто победит? (Подсказка: симметрия!)

4. На доске $8\times 8$ в углу стоит фишка. Двое по очереди двигают её на одну клетку вправо или вверх. Кто не может сделать ход (фишка в противоположном углу) — проиграл. Кто выигрывает?

5. Ним с кучками $4, 7, 9$. Кто выигрывает — первый или второй? Если первый — какой первый ход выигрывает? (Посчитай ним-сумму.)

6. Двое по очереди кладут костяшки домино $1\times 2$ на доску $8\times 8$ (каждая накрывает две соседние пустые клетки, костяшки не перекрываются). Кто не может положить костяшку — проиграл. Кто выигрывает? (Подумай про центральную симметрию доски.)

7. Кучка из 100 камней. За ход берут число камней, являющееся степенью двойки (1, 2, 4, 8, ...). Кто взял последний — выиграл. Найди все проигрышные позиции (подсказка: посмотри остатки по модулю 3).

8. ⭐ Есть шоколадка $5\times 8$ (40 долек). Ход: взять один кусок и разломить его по прямой линии сетки на два. Игра кончается, когда все дольки разломаны (36 кусочков... подумай сколько). Проигрывает тот, кто не может сделать ход. Кто выигрывает? (Подсказка: посчитай общее число разломов — оно не зависит от игры! Это скрытый инвариант.)