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

Математика

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

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

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

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

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

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

Такие игры математики называют конечными играми с полной информацией. Слова длинные, а смысл простой: всё честно, всё на виду, случай ни при чём, и партия не может тянуться вечно. Именно про такие игры и можно доказать удивительные вещи.

🤔 А знаешь ли ты? В любой такой игре есть удивительный факт: у одного из игроков всегда есть выигрышная стратегия. То есть он может играть так, что выиграет при любой игре соперника, хоть тот лоб расшибёт. Наша задача — найти, у кого она есть и как ему ходить. (Правда, «есть стратегия» и «мы её знаем» — это разные вещи! Для шахмат доказано, что стратегия существует, но никто на Земле её не знает.)

Два главных слова: В-позиция и П-позиция

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

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

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

Золотое правило и анализ с конца

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

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

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

⚠️ Осторожно с логикой! Слова похожи, но правила разные: для В хватает одного хорошего хода, а для П нужно, чтобы все ходы были плохими. Это как «выиграть в лотерею» (достаточно одного счастливого билета) против «проиграть все билеты» (не повезло с каждым). Путать эти два случая — самая частая ошибка.

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

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

Почему у кого-то всегда есть стратегия

Почему золотое правило вообще работает и не бывает «ничьей неопределённости»? Разберём коротко. Пометим все позиции с конца. Финальная позиция (ходить нельзя) — П по правилу 1. Дальше любая позиция либо имеет ход в какую-то уже помеченную П (тогда она В), либо все её ходы ведут только в В (тогда она П). Третьего не дано: у позиции либо есть ход в П, либо нет. Поэтому каждая позиция получает ровно одну метку. А раз стартовая позиция помечена, значит уже в начале известно, кто выиграет при идеальной игре обоих. Никакой магии: просто аккуратно доведённое до начала рассуждение с конца.

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

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

Есть отдельная красивая идея, которая часто позволяет выиграть без всякого анализа с конца. Называется стратегия симметрии (или «зеркала»).

Суть: если поле обладает симметрией (например, у него есть центр), первый игрок делает особый первый ход, «занимающий центр», а дальше на каждый ход соперника отвечает симметричным ходом. Тогда у него всегда найдётся ответ: ведь если сопернику было куда сходить, то и в зеркальную точку тоже свободно. Раз у первого всегда есть ответ, застрять первым он не может: застрянет соперник. Мы разберём это на монетах и спичках ниже.

💡 Лайфхак: Симметрия — это способ «переложить» проблему хода обратно на соперника. Ты не придумываешь ход, ты просто копируешь чужой, отражая его. Пусть соперник думает за двоих!

Игра «ним»: король всех таких игр

А теперь — самая знаменитая игра этого урока. Она называется ним (по-английски nim). Правила такие: на столе лежат несколько кучек камней (например, три кучки). За ход игрок выбирает любую одну кучку и берёт из неё сколько хочет камней (хоть один, хоть всю кучку целиком), но только из одной кучки за ход. Кто взял последний камень со стола — победил.

Если кучка одна, скукота: первый забирает её целиком и выигрывает. Интересное начинается с двух и более кучек.

Две кучки. Попробуем анализ с конца, но по-хитрому. Утверждение: позиция с двумя кучками проигрышная (для того, кто ходит) ровно тогда, когда кучки равны. Почему?

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

Значит равные кучки — это П-позиция (всё ведёт в неравное = хорошее для соперника), а неравные — В-позиция (есть ход в равное). Стратегия для двух кучек: своим ходом уравнивай кучки. Тогда соперник всё время получает равные кучки, а последнюю равную пару ты добьёшь сам.

Заметь: это ведь та же стратегия симметрии! «Держи кучки равными» = «зеркаль соперника»: сколько он взял из одной кучки, столько ты берёшь из другой.

Три и больше кучек — намного хитрее, и там работает удивительное правило про двоичные числа (его придумали математики; называется «ним-сумма»). Оно выходит за рамки урока, но знай: у нима из любого числа кучек есть точная выигрышная стратегия, и её знают полностью. Ним — редкий пример игры, которую математики полностью решили.

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

Пример 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.

🤔 А знаешь ли ты? Сравни примеры 1 и 2: одна и та же игра, но одно слово в правилах («выиграл» → «проиграл») переворачивает ответ и сдвигает все проигрышные позиции на единицу. В таких играх правило про последний ход — самое важное. Всегда сначала спрашивай себя: а брать последнее — это хорошо или плохо?

Пример 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$.

💡 Лайфхак: «Бери 1–$n$, доберись до цели $N$» и «убирай 1–$n$ из кучи $N$» — это одна и та же игра, просто с разных сторон! Ключевой шаг всегда $n+1$. Здесь $n=10$, шаг $11$; в примере 1 было $n=3$, шаг $4$. Узнал одну — узнал все.

Пример 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 побеждает «автоматически» тот, кому повезло с чётностью числа ходов.

Пример 7. Ним из двух кучек: в одной 7 камней, в другой 4. За ход берут сколько угодно (но хотя бы один) камней из одной кучки. Кто взял последний камень — победил. Кто выигрывает и как?

Как рассуждаем. Мы уже вывели правило нима для двух кучек: проигрышны равные кучки. Сейчас кучки неравны ($7\ne 4$), значит текущая позиция выигрышная, и побеждает первый. Его первый ход — уравнять: взять из большей кучки $7-4=3$ камня, оставив $4$ и $4$.

Дальше он держит зеркало: сколько соперник возьмёт из одной кучки, столько первый берёт из другой, снова уравнивая. Позиции идут так: $(7,4)\to (4,4)\to$ (соперник ломает равенство) $\to$ (первый восстанавливает) $\to \cdots \to (0,0)$. Последний камень достаётся первому.

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

🤔 А знаешь ли ты? Проверь на маленьком: кучки $(1,1)$. Ты обязан взять из одной кучки, останется $(1,0)$, соперник забирает последний и выигрывает. Значит равные кучки и правда проигрышны, даже самые маленькие. С этого «зерна» и вырастает всё правило.

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

⏱ Попробуй сам. Подсказка: сравни это с нимом из двух кучек. Что играет роль «двух кучек»?

Как рассуждаем. Хитрость: расстояние вправо до правого края и расстояние вверх до верхнего края — это как раз две кучки! Ход «вправо на $k$» уменьшает первое расстояние на $k$ (берём из первой кучки), ход «вверх на $k$» — второе (из второй кучки). Привести ладью в угол = обнулить обе «кучки». Это в точности ним из двух кучек!

В начале ладья в левом нижнем углу доски 8×8: до правого края $7$ клеток, до верхнего края тоже $7$. Кучки равны ($7$ и $7$) → позиция проигрышная для того, кто ходит, то есть для первого. Значит выигрывает второй. Его стратегия — держать расстояния равными: если первый сдвинул ладью вправо на $k$, второй двигает вверх на $k$ (и наоборот). Ладья идёт по диагонали к углу, и последний ход делает второй.

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

💡 Лайфхак: Одна и та же математика прячется в разных костюмах: камни, ладья, монеты. Учись узнавать знакомую игру под новой обёрткой — «а это же ним!», «а это же кратные 4!». Половина олимпиадной задачи — понять, во что ты на самом деле играешь.

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

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

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

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

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

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

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

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

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

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

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