Выигрышная стратегия игры Баше

Баше относится к комбинаторным играм с полной информацией: оба игрока видят всё поле и знают правила. У таких игр часто есть строгая оптимальная стратегия. В классическом Баше с ходами «1–3 палочки» она сводится к делению на четыре. Разберём, какие позиции выигрышные, докажем правило, посмотрим примеры партий и обобщим стратегию на любое число предметов.

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

На каждом шаге состояние игры полностью описывается одним числом — количеством оставшихся палочек. Никаких скрытых карт и случайности (если только соперник сам не играет наугад). Поэтому каждую позицию можно заранее отнести к одному из двух видов.

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

Для Баше с ходами 1–3 верно следующее:

• Если количество палочек кратно 4 (4, 8, 12, 16…), позиция проигрышна для ходящего.
• Если остаток при делении на 4 не равен нулю, позиция выигрышна: нужно взять столько палочек, каков остаток, и оставить сопернику число, кратное 4.

Математическое обоснование

Докажем правило индукцией по числу палочек n.

База. При n = 1, 2, 3 ходящий забирает все палочки и побеждает — позиции выигрышные. При n = 4 ходящий может взять 1, 2 или 3, после чего останется 3, 2 или 1 палочка — выигрышная позиция для соперника. Значит, n = 4 проигрышно.

Шаг индукции. Пусть для всех меньших n правило верно. Рассмотрим n > 4.

• Если n ≡ 0 (mod 4), то после любого допустимого хода k ∈ {1, 2, 3} остаётся n − k ≡ 1, 2 или 3 (mod 4), то есть не 0. По предположению индукции соперник окажется в выигрышной позиции. Значит, n проигрышно.
• Если n ≢ 0 (mod 4), положим r = n mod 4, где r ∈ {1, 2, 3}. Ход «взять r палочек» оставляет n − r ≡ 0 (mod 4) — проигрышную позицию для соперника. Значит, n выигрышно.

Отсюда практическая формула: оптимальный ход = n mod 4. Если остаток равен 0, позиция уже проигрышная, и «правильного» хода не существует.

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

Примеры партий

Правильная игра первого игрока (старт: 15 палочек):

1. Игрок 1: 15 mod 4 = 3 → берёт 3. Остаётся 12 (проигрышно для Игрока 2).
2. Игрок 2 берёт, допустим, 2. Остаётся 10.
3. Игрок 1: 10 mod 4 = 2 → берёт 2. Остаётся 8.
4. Игрок 2 берёт, допустим, 1. Остаётся 7.
5. Игрок 1: 7 mod 4 = 3 → берёт 3. Остаётся 4.
6. Игрок 2: любой ход оставляет 1–3 палочки.
7. Игрок 1 забирает остаток и побеждает.

Ошибка первого игрока (тот же старт):

1. Игрок 1 берёт 2 вместо 3. Остаётся 13.
2. Игрок 2: 13 mod 4 = 1 → берёт 1. Остаётся 12 — проигрышно для Игрока 1.
3. Дальше второй игрок, зная стратегию, доводит партию до победы при любых ответах первого.

Один неверный ход в начале отдаёт преимущество сопернику. Поэтому знание правила «mod 4» так важно.

Обобщение: N предметов и ходы от 1 до m

Число 4 появилось не случайно: это максимальный ход плюс один. Если за ход разрешено брать от 1 до m предметов, «ключевым» становится число m + 1. За пару ходов «соперник + вы» всегда можно убрать ровно m + 1 предметов: если соперник взял k, вы берёте m + 1 − k.

• Позиции, кратные m + 1, проигрышны для ходящего.
• Из любой другой позиции выигрышный ход — взять N mod (m + 1) предметов.
• Если начальное N кратно m + 1, при правильной игре побеждает второй игрок; иначе — первый.

Мизерный вариант: последний проигрывает

Если проигрывает тот, кто взял последний предмет, цель сдвигается на единицу: оставляйте сопернику число, дающее остаток 1 при делении на m + 1. Для ходов 1–3 это 1, 5, 9, 13… При 15 палочках первый игрок берёт 2 и оставляет 13.

Баше и игра Ним

Математически Баше — частный случай игры Ним с одной кучей и ограничением на размер хода. В обычном Ниме несколько куч и из одной кучи можно взять сколько угодно предметов; его полный анализ опубликовал Чарльз Бутон в 1901 году. В теории комбинаторных игр Баше и Ним относятся к беспристрастным играм (impartial games): у обоих игроков одинаковые ходы, а различаются они только очерёдностью. Позднее эту теорию систематизировали Элвин Берлекэмп, Джон Конвей и Ричард Гай.

Баше и задания 19–21 ЕГЭ по информатике

В ЕГЭ по информатике задания 19–21 посвящены теории игр. Два игрока, Петя и Ваня, по очереди изменяют кучу камней (например, добавляют камень или увеличивают кучу в несколько раз), и нужно определить, у кого есть выигрышная стратегия и за сколько ходов он может победить.

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

История и происхождение

Игра названа в честь французского математика Клода Гаспара Баше де Мезириака (1581–1638). В 1612 году он издал сборник занимательных арифметических задач «Problèmes plaisants et délectables». В нём описана игра с суммой: игроки по очереди прибавляют к общему счёту число от 1 до 10, и побеждает тот, кто первым доведёт сумму до 100. Это та же игра Баше с m = 10: ключевое число — 11, и выигрывает тот, кто называет суммы 1, 12, 23, … 89.

В русскоязычной литературе задача известна по книгам о занимательной математике — например, «В царстве смекалки» Е. И. Игнатьева и «Математической смекалке» Б. А. Кордемского. В вариантах с палочками, спичками или камешками её разыгрывали на переменах, в поездах и на даче.

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

Советы игроку

Перед каждым ходом мысленно вычисляйте остаток от деления на 4 и не оставляйте сопернику число палочек, кратное четырём. Если вы ходите первым при 15 палочках, начните с трёх.

Против случайной стратегии компьютера достаточно базовой дисциплины: даже без идеальной игры вы будете выигрывать чаще, потому что он регулярно «дарит» выигрышные позиции. В режиме «Победная» компьютер ходит первым из позиции 15 и после каждого своего хода оставляет вам 12, 8 или 4 палочки, поэтому при его правильной игре победить нельзя. Это наглядная демонстрация того, что исход Баше решается первым ходом: проверьте по таблице ходов, сколько палочек он вам оставляет.

Игрок, знающий стратегию, кажется новичку «везучим», хотя дело не в удаче, а в математике. Попробуйте объяснить правило mod 4 другу после серии партий — это лучший способ закрепить материал.

Вариации правил

В разных регионах встречаются модификации:

• Другое начальное число — при N ≡ 0 (mod 4) при идеальной игре выигрывает второй игрок, при N ≢ 0 — первый.
• Проигрыш последним ходом — инверсия цели меняет стратегию: оставлять сопернику нужно число с остатком 1 при делении на 4, а не 0 (см. мизерный вариант).
• Другой лимит хода — если разрешено брать до m палочек, ключевым числом становится m + 1 (см. обобщение). Для ходов 1–3 это как раз 4.

На нашем сайте реализован классический вариант: 15 палочек, ходы 1–3, победа последним ходом. Подробные правила игры — на отдельной странице.

Проверить стратегию в игре