Выигрышные стратегии: спички, крестики-нолики, Ним
В некоторых играх исход можно рассчитать заранее: если знать правильную стратегию, выигрываешь всегда. Такие игры любят на олимпиадах и в кружках, потому что они учат думать с конца и искать закономерности. Разбираем три игры, которые можно попробовать прямо сейчас с друзьями.
Для 5–9 классов.
Игра в спички
На столе 21 спичка. Двое игроков по очереди берут от одной до трёх спичек. Кто взял последнюю, тот выиграл. Кто выиграет при правильной игре?
Решаем с конца. Если перед вашим ходом 1, 2 или 3 спички, вы забираете все и выигрываете. Если 4, вы проигрываете: сколько ни возьмите, соперник заберёт остальное. Значит, 4 проигрышная позиция для того, кто ходит. Если 5, 6 или 7, берите столько, чтобы осталось 4, и выиграете. Если 8, снова проигрыш: любой ваш ход даёт сопернику 5, 6 или 7.
проигрышные позиции: 4, 8, 12, 16, 20, …
Стратегия: всегда оставляйте сопернику число спичек, кратное 4. Из 21 первый игрок берёт 1, остаётся 20. Дальше, если соперник взял k, вы берёте 4 − k. После каждой пары ходов уходит ровно 4 спички, и последняя достанется вам.
Задача
В игре 30 спичек, брать можно от одной до четырёх, кто взял последнюю, выиграл. Кто выиграет и как?
Теперь за пару ходов можно гарантированно забрать 5 спичек: если соперник взял k, берём 5 − k.
Проигрышные позиции кратны 5. 30 уже кратно 5.
Значит, первый игрок проигрывает: что бы он ни взял, второй дополняет до пяти.
Ответ: выигрывает второй игрок, дополняя ходы соперника до 5.
Правило для любой такой игры: если можно брать от 1 до m, проигрышны позиции, кратные m + 1. Попробуйте сыграть с друзьями, не раскрывая секрета: они быстро решат, что вам просто везёт.
Крестики-нолики
Крестики-нолики на поле 3 × 3 полностью просчитаны: при правильной игре обеих сторон всегда ничья. Но чтобы не проиграть самому и наказать ошибку соперника, полезно знать несколько правил.
- Первый ход. Лучше всего угол или центр. С ходом в угол соперник, который ответит не в центр, почти наверняка проиграет.
- Отвечая на угол. Нолики должны встать в центр. Любой другой ответ даёт крестикам выигрыш.
- Вилка. Главный приём: ход, который создаёт две угрозы сразу. Соперник может закрыть только одну.
- Порядок проверки на каждом ходу: можно ли выиграть сейчас; нужно ли закрыть угрозу соперника; можно ли сделать вилку; можно ли помешать вилке соперника.
Поле 3 × 3 настолько маленькое, что все партии компьютер перебирает мгновенно: различных позиций меньше шести тысяч. А вот в «пять в ряд» на большом поле, которую называют гомоку, начинающий при правильной игре побеждает. Это доказали с помощью компьютера в 1990-х годах.
Игра Ним
Есть несколько кучек камней, например 3, 4 и 5. За ход можно взять сколько угодно камней, но только из одной кучки. Кто взял последний камень, выиграл. Эта старинная игра называется Ним, и её полное решение нашёл американский математик Чарльз Бутон в 1901 году.
Секрет в двоичной системе. Запишите размеры кучек в двоичном виде и сложите по разрядам без переноса, считая, сколько единиц в каждом разряде: чётное число единиц даёт 0, нечётное 1. Эту операцию называют «исключающее или». Если результат нулевой, позиция проигрышная для того, кто ходит.
Задача
Кучки 3, 4 и 5. Выигрышна ли позиция для первого игрока, и каким должен быть первый ход?
В двоичной записи: 3 = 011, 4 = 100, 5 = 101.
По разрядам: старший 0 + 1 + 1 = 2 единицы, чётно, 0. Средний 1 + 0 + 0 = 1, нечётно, 1. Младший 1 + 0 + 1 = 2, чётно, 0. Итог 010, не ноль. Позиция выигрышная.
Нужно сделать итог нулевым. Уменьшим кучку 3 до 1: 001, 100, 101. Старший разряд 2, средний 0, младший 2. Итог 000.
Ответ: первый выигрывает: нужно взять 2 камня из кучки в 3.
После такого хода соперник любым действием снова сделает итог ненулевым, а вы вернёте его к нулю. В конце все кучки опустеют на вашем ходу. Как переводить в двоичную систему, рассказали в статье о системах счисления.
Симметричная стратегия
Задача
Двое по очереди кладут одинаковые монеты на круглый стол так, чтобы они не перекрывались. Кто не может положить монету, проиграл. Кто выиграет?
Первый кладёт монету точно в центр стола.
Дальше на каждый ход второго первый кладёт монету симметрично относительно центра.
Если второй нашёл свободное место, симметричное ему тоже свободно. Значит, первый всегда сможет ответить, и первым застрянет второй.
Ответ: выигрывает первый, используя симметрию.
Симметрия один из самых красивых олимпиадных приёмов. Ещё больше идей в статье об олимпиадных задачах для 5–6 класса.
Разберём на занятии
Разберём эту тему и всё, что с ней связано, на живом занятии: преподаватель видит, как ребёнок решает, и поправляет на первом неверном шаге.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.
Частые вопросы
Зачем школьнику такие игры?
Они учат рассуждать с конца, искать закономерности и проверять гипотезы. Это те же навыки, что нужны в задачах на исполнителей по информатике и в последнем задании ЕГЭ по математике. А ещё в них просто интересно играть.
А если последнюю спичку брать проигрышно?
Тогда цель оставить сопернику одну спичку. Проигрышными становятся позиции 1, 5, 9, 13 и так далее, то есть на единицу больше кратных четырём. Стратегия та же, только сдвинута на одну спичку.
Как придумать стратегию для новой игры?
Начать с самых маленьких позиций, где ответ очевиден, и понять, какие из них выигрышные, а какие проигрышные. Потом найти закономерность и проверить её на следующих числах. Математики называют это анализом с конца.