Урок 7. Игры и выигрышные стратегии

Математика · ~55 минут

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

• Что такое выигрышная и проигрышная позиция в игре.
• Как находить стратегию, рассуждая с конца игры.
• Победную стратегию в игре «отнимание камней» (секрет кратных 4).
• Стратегию симметрии — простой и красивый способ всегда выигрывать.

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

Представь: ты играешь с приятелем в простую игру с кучкой камней. Он каждый раз выигрывает. Каждый. Раз. Ты уже подозреваешь, что он жульничает. А он просто знает один секрет. И к концу урока этот секрет будешь знать ты — и сможешь обыграть кого угодно, даже не вспотев.

Мы поговорим про игры двух игроков, где:

• ходят по очереди;
• никто ничего не прячет — оба видят всю позицию (как в шахматах, а не в картах);
• нет случайностей (никаких кубиков);
• игра обязательно когда-нибудь кончается.

🤔 А знаешь ли ты? В любой такой игре есть удивительный факт: у одного из игроков всегда есть выигрышная стратегия. То есть он может играть так, что выиграет при любой игре соперника — хоть тот лоб расшибёт. Наша задача — найти, у кого она есть и как ему ходить.

Введём два важных слова.

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

Как их различить? Есть золотое правило, и оно работает через анализ с конца:

1. Позиция, где игра уже кончилась и ходить нельзя, — это проигрыш для того, кто должен был ходить (в игре «кто взял последний — выиграл» пустая куча означает, что предыдущий игрок забрал последнее и победил, а тебе ходить нечем → ты проиграл).
2. Позиция выигрышная, если из неё есть хотя бы один ход в проигрышную позицию (отдай сопернику плохую позицию — и он попал).
3. Позиция проигрышная, если все ходы из неё ведут только в выигрышные позиции (куда ни пойди — подаришь сопернику победу).

Смотри, как красиво: «выигрышная = есть ход в проигрышную», «проигрышная = все ходы в выигрышные». Если идти от конца игры назад, можно пометить каждую позицию буквой В или П. А дальше стратегия очевидна: всегда ходи так, чтобы отдать сопернику проигрышную позицию.

Это и есть анализ с конца — мы начинаем разбор не с начала игры, а с её финала, где всё ясно, и пятимся назад.

💡 Лайфхак: Не пытайся продумать игру вперёд — там слишком много веток. Начинай с финала, где всё очевидно, и иди назад. Это как разгадывать лабиринт, выйдя из выхода.

✍️ Разбор примеров

Пример 1. В куче 20 камней. Двое по очереди берут 1, 2 или 3 камня. Кто взял последний камень — победил. Кто выиграет при правильной игре и как?

⏱ Попробуй сам прикинуть на маленьких кучках (1, 2, 3, 4 камня), кто выигрывает, а потом читай дальше.

Как рассуждаем. Анализ с конца. Позиция = сколько камней осталось.

• 0 камней: тебе ходить нечем, значит соперник взял последний → ты проиграл. 0 — П.
• 1, 2, 3 камня: можешь забрать все и выиграть → В.
• 4 камня: сколько ни возьми (1, 2 или 3), сопернику останется 3, 2 или 1 — а это всё В-позиции (он заберёт всё). Значит из 4 все ходы ведут в В → 4 — П.
• 5, 6, 7: можно одним ходом оставить сопернику 4 (П-позицию) → В.
• 8: что ни возьми, останется 7, 6 или 5 — это В → 8 — П.

Видишь закономерность? Проигрышные позиции — это кратные 4 (0, 4, 8, 12, 16, 20). В начале 20 камней — это П-позиция! Значит первому игроку досталась плохая позиция, и побеждает второй. Его стратегия: всякий раз дополнять ход первого до 4. Первый взял $k$ камней — второй берёт $4-k$. После каждой такой пары ходов остаток уменьшается ровно на 4, оставаясь кратным 4: $20 \to 16 \to 12 \to 8 \to 4 \to 0$. Последние 4 камня заберёт пара ходов, и последний камень окажется у второго.

📌 Запомни: Вот он, секрет из начала урока! «Бери 1–3, последний выиграл» → держи кучу кратной 4 после своего хода. Если в начале число кратно 4 — везёт второму, иначе первому.

Ответ: выигрывает второй игрок; стратегия — всегда дополнять ход соперника до 4.

Пример 2. Та же игра (куча 20, берут 1–3), но теперь правило наоборот: кто взял последний камень — проиграл. Кто выигрывает?

Как рассуждаем. Снова с конца, но финал поменялся. Теперь брать последний камень плохо. Удобно думать про «отравленный» последний камень: ты хочешь оставить сопернику ровно 1 камень, чтобы он был вынужден его взять.

• 1 камень: ты обязан взять его (брать можно 1–3, но камень один) и проигрываешь → 1 — П.
• 2, 3, 4 камня: можешь оставить сопернику ровно 1 → В.
• 5 камней: что ни возьми (1–3), останется 4, 3 или 2 — это В → 5 — П.
• Дальше закономерность: проигрышные позиции — те, где остаток даёт остаток 1 при делении на 4 (1, 5, 9, 13, 17, 21, …).

В начале 20 камней. $20 = 4\cdot 5$, остаток при делении на 4 равен 0 — это не проигрышная позиция, значит 20 — В. Ходит первый и побеждает. Его первый ход: оставить сопернику число вида «кратное 4 плюс 1». Ближайшее снизу — 17. Значит первый берёт $20 - 17 = 3$ камня. Дальше он дополняет ходы соперника до 4, держа остаток в ряду $17, 13, 9, 5, 1$. В конце сопернику достанется 1 камень, и он вынужден взять последний — проигрывает.

Ответ: выигрывает первый; первым ходом берёт 3 (оставляет 17), затем дополняет ходы соперника до 4.

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

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

Если перед твоим ходом сумма равна 89, то ты прибавляешь $100 - 89 = 11$ — но максимум 10! Не дотянешь. Зато если ты оставил сопернику сумму 89, то он прибавит от 1 до 10 и получит от 90 до 99, а ты следующим ходом доберёшь до 100. Значит 89 — позиция, которую хочется подарить сопернику.

А до 89 — аналогично 78, 67, 56, 45, 34, 23, 12, 1. Это ключевые числа: они идут с шагом 11. Тот, кто называет эти числа, побеждает. Самое первое ключевое число — 1. Его может назвать первый игрок (прибавив 1 к нулю).

Ответ: выигрывает первый. Он называет 1, а затем после каждого хода соперника дополняет сумму так, чтобы получилось следующее ключевое число (то есть прибавляет до $1, 12, 23, 34, 45, 56, 67, 78, 89, 100$). Если соперник прибавил $k$, первый прибавляет $11-k$.

Пример 4. Двое кладут одинаковые круглые монеты на круглый стол. Монеты не должны налегать друг на друга и не должны свешиваться со стола. Ходят по очереди; кто не может положить монету — проиграл. Кто выигрывает?

⏱ Попробуй сам. Подсказка: у круглого стола есть одна особенная точка. Куда бы ты сходил первым?

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

Дальше первый играет «зеркально»: куда бы второй ни положил монету, первый кладёт свою в центрально-симметричную точку (по другую сторону от центра, на том же расстоянии). Почему это всегда возможно? Если второй смог положить монету в какое-то место, то симметричное место тоже свободно: оно было бы занято только симметричной монетой, но все монеты до этого ставились парами-зеркалами, плюс центральная (она симметрична сама себе и занята). Значит у первого всегда есть ответный ход. Игра конечна (стол не бесконечный), поэтому рано или поздно второму некуда будет ходить.

Ответ: выигрывает первый: первый ход — в центр, далее симметрично ответам соперника.

Пример 5. На прямоугольном столе двое по очереди кладут спички (одинаковые), спичка не должна налегать на уже лежащие и не должна свисать. Кто не может положить — проиграл. Есть ли тут симметрия? Кто выигрывает?

Как рассуждаем. У прямоугольника тоже есть центр симметрии. Но спичка — не круг, у неё есть направление! Чтобы симметрия работала, при центральной симметрии спичка должна переходить в «правильно лежащую» спичку. Если первый игрок кладёт первую спичку точно по центру стола вдоль одной из осей симметрии (например, параллельно длинной стороне, по центральной линии), то центральное место занято, и дальше он отвечает центрально-симметрично. При центральной симметрии спичка переходит в спичку того же направления — значит ответ всегда корректен и возможен.

Ответ: выигрывает первый — первая спичка в центр вдоль оси, далее симметрично.

Пример 6. Шоколадка 6×4 (24 дольки). За ход берут один кусок и ломают его по прямой линии (вдоль углубления) на два куска. Игра идёт, пока вся шоколадка не разломана на 24 отдельные дольки. Кто сделал последний разлом — победил. Кто выигрывает?

⏱ Попробуй сам. Тут есть подвох: посчитай, сколько вообще разломов придётся сделать. От чего это число зависит?

Как рассуждаем. Сначала кажется, что нужна сложная стратегия. Но найдём инвариант (привет уроку 6!). Каждый разлом берёт один кусок и делает из него два, то есть число кусков увеличивается ровно на 1. В начале кусок один. В конце кусков 24. Значит всего сделано $24 - 1 = 23$ разлома — независимо от того, как ломали! Число ходов фиксировано: 23. Ходы делают по очереди: 1-й, 2-й, 1-й, … Ход номер 23 — нечётный, значит его делает первый игрок (он делает ходы 1, 3, 5, …, 23).

Ответ: выигрывает первый — он всегда делает последний (23-й) разлом, как бы оба ни играли. Стратегия не нужна вовсе: исход предрешён числом кусков.

📌 Запомни: Иногда играть умно вообще не надо. Если число ходов фиксировано, победитель определяется одной только чётностью этого числа. Всегда сначала проверяй: а не предрешён ли исход заранее?

Заметь разницу: в примерах 1–3 нужно умно ходить, а в примере 6 побеждает «автоматически» тот, кому повезло с чётностью числа ходов.

💡 Запомни главное

• В честной игре двух игроков у кого-то всегда есть выигрышная стратегия.
• Анализ с конца: финал ясен, помечай позиции В/П, пятясь назад.
• П-позиция: все ходы ведут в В. В-позиция: есть ход в П.
• Стратегия: всегда отдавай сопернику проигрышную позицию.
• «Бери 1–3, последний выиграл» → проигрышные позиции кратны 4; дополняй ход соперника до 4.
• Симметрия: сходи в центр, потом зеркаль ходы соперника. Работает, когда у поля есть центр симметрии.
• Если число ходов фиксировано (как при ломании шоколадки) — победитель определяется только чётностью числа ходов.

📝 Домашнее задание

1. Куча 12 камней, берут 1, 2 или 3, кто взял последний — выиграл. Кто победит и как?

2. Куча 21 камень, берут 1, 2 или 3, кто взял последний — выиграл. Кто победит и какой первый ход?

3. Куча 15 камней, берут 1, 2, 3 или 4, кто взял последний — проиграл. Кто победит и как ходить? (Подумай, какие остатки при делении на 5 — проигрышные.)

4. Двое прибавляют к сумме 1, 2 или 3, начиная с 0. Кто назовёт 24 — победил. У кого стратегия?

5. Шоколадка 5×7 (35 долек), ломают как в примере 6, последний разлом — победа. Кто выигрывает? (Сначала посчитай число ходов.)

6. Двое кладут монеты на круглый стол (как в примере 4), но первый игрок по ошибке сделал первый ход не в центр. Может ли теперь второй перехватить выигрышную стратегию? Объясни идею.

7. Куча 100 камней, берут 1, 2, 3, 4 или 5; кто взял последний — выиграл. Кто победит и какова стратегия?

8. ⭐ На доске 7×7 двое по очереди ставят королей так, чтобы новый король не стоял на клетке, соседней (по стороне или диагонали) с уже стоящим королём. Кто не может поставить — проиграл. У кого выигрышная стратегия? (Подсказка: у доски 7×7 есть настоящая центральная клетка — вспомни стратегию симметрии.)