Человек, начинающий изучать теорию игр, довольно быстро натыкается на эту задачу про монеты, возможно, в несколько иной формулировке.
Задача
В ряд лежат 2n+1 монет. За ход разрешается брать от 1 до n рядом лежащих монеты. Проигрывает тот, кому нечего брать. Кто выиграет при правильной игре?
Ответ: при правильной игре выиграет первый игрок (тот, который ходит первым).
Решение: Поскольку монет нечётное количество, существует центральная монета. Её своим первым ходом и должен взять Первый. Ряд разбился на два ряда, по n монет в каждом. Пусть своим ходом Второй берёт k монет. Тогда имеем такую ситуацию: в одном ряду n монет, в другом - n-k. Тогда первому игроку достаточно взять тоже k монет из ряда, в котором лежит n монет, причём таким же образом, как это и сделал Второй. Итак, опять имеем ситуацию, симметричную относительно центральной монеты. Таким образом получается, что на любой ход Второго Первый может ответить симметрично. Значит, у Первого "в запасе" всегда есть ход. Получается, рано или поздно Второй проиграет.
Приведённая выше стратегия игры Первого игрока называется симметричная.
Вот ещё несколько задач на применение этой стратегии (попробуйте их решить сами!):
- На доске написано число 1. Два игрока по очереди прибавляют любое число от 1 до 5 к числу на доске и записывают вместо него сумму. Выигрывает игрок, который первый запишет на доске число тридцать. Кто выиграет при правильной игре?
- У ромашки а) 12 лепестков; б) 11 лепестков. За ход разрешается сорвать либо один лепесток, либо два рядом растущих лепестка. Проигрывает игрок, который не сможет сделать ход. Как действовать второму игроку, чтобы выиграть независимо от ходов первого игрока?
- На плоскости отмечено 1968 точек, являющихся вершинами правильного 1968-угольника. Двое играют в следующую игру: каждый по очереди соединяет две вершины многоугольника отрезком, соблюдая следующие правила: нельзя соединять две точки, хотя бы одна из которых уже соединена с чем-то, и нельзя пересекать уже проведённые отрезки. Проигрывает тот, кто не может сделать очередного хода согласно этим правилам. Как нужно играть, чтобы выиграть? Кто выигрывает при правильной игре?
- Двое играют в крестики-нолики на доске 10×10 по следующим правилам. Сначала они заполняют крестиками и ноликами всю доску, ставя их по очереди (начинающий игру ставит крестики, его партнер – нолики). Затем подсчитываются два числа: K – число пятерок подряд стоящих крестиков и H – число пятерок подряд стоящих ноликов. (Считаются пятерки, стоящие по горизонтали, по вертикали и параллельно диагонали; если подряд стоят шесть крестиков, то это даёт две пятерки, если семь, то три и т. д.) Число K – H считается выигрышем первого игрока (проигрышем второго).
а) Существует ли у первого игрока беспроигрышная стратегия?
б) Существует ли у него выигрышная стратегия? - Два пирата делят добычу, состоящую из двух мешков монет и алмаза, действуя по следующим правилам. Вначале первый пират забирает себе из любого мешка несколько монет и перекладывает из этого мешка в другой такое же количество монет. Затем также поступает второй пират (выбирая мешок, из которого он берет монеты, по своему усмотрению) и т.д. до тех пор, пока можно брать монеты по этим правилам. Пирату, взявшему монеты последним, достается алмаз. Кому достанется алмаз, если каждый из пиратов старается получить его? Дайте ответ в зависимости от первоначального количества монет в мешках.
- Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять из одной кучки от 1 до 5 камней. Определите выигрышную стратегию в этой игре, если тот, кто взял последний камень а) выигрывает; б) проигрывает.
Пишите в комментарии, какие из этих задач стоит разобрать!
Не забывайте подписываться на канал, ставить лайк, и писать в комментарии идеи для статей!