Question

1. На столе лежат 25 спичек. Играют двое. Игроки по очереди могут взять от одной до четырех спичек. Кто не может сделать ход (т.к. спичек не осталось), проигрывает. Другими словами, выигрывает взявший последнюю спичку. Выясните, у кого из игроков есть выигрышная стратегия. 2. Выясните, у кого из игроков есть выигрышная стратегия в такой игре: начальная позиция – на столе лежит 107 спичек, за один ход можно брать 1 или 2 спички. Выигрывает тот, кто взял последнюю спичку.

Answer 1

У этих игр очень простая стратегия. Запомните её один раз и будете решать любые подобные задачи.

Пусть дано P предметов и за ход можно брать от 1 до n предметов.
Вычисляем "магическое число" М = n+1.
Находим остаток целочисленного деления P на M - он покажет, сколько спичек надо взять при первом ходе для выигрыша. Если 0 - то игрок, делающий ход первым, проигрывает. Выигрышная стратегия проста. Если противник взял k предметов, мы берем M-k.

Рассмотрим задачу 1.
P=25, n=4
М=n+1=5, P/M дает в остатке 0 - игрок, делающий ход первым, проигрывает.
Выигрышная стратегия: брать 5-k предметов, оставляя противнику 20, 15, 10 и 5 предметов.

Рассмотрим задачу 2.
P=107, n=2
M=n+1=3, P/M дает в остатке 2 - игрок, делающий ход первым, берет 2 предмета и выигрывает.
Выигрышная стратегия: брать 3-k предметов, оставляя противнику 105, 102, 99, 96, ... предметов.

Answer 2

1. Для того чтобы выяснить, у кого из игроков есть выигрышная стратегия в первой игре, воспользуемся методом обратной индукции. Рассмотрим несколько начальных позиций:

• Если на столе лежит 1 спичка, то первый игрок обязательно проигрывает, так как он не может взять больше спичек, чем на столе.
• Если на столе лежит 2 спички, то первый игрок также обязательно проигрывает, потому что независимо от того, сколько спичек он возьмет (от 1 до 2), второй игрок возьмет оставшуюся спичку и выиграет.
• Если на столе лежит 3 спички, то первый игрок может взять 1 спичку. Тогда на столе останется 2 спички, и второй игрок обязательно проиграет, как мы выяснили выше.
• Если на столе лежит 4 спички, то первый игрок может взять 1, 2 или 3 спички. Но какую бы стратегию он не выбрал, второй игрок сможет выиграть, как мы уже знаем.

Таким образом, анализируя различные начальные позиции, мы можем увидеть закономерность: если на столе количество спичек кратно 5 (т.е. 5, 10, 15 и т.д.), то первый игрок проигрывает, в противном случае он может выиграть. Так как в начальной позиции у нас 25 спичек (что кратно 5), то первый игрок не имеет выигрышной стратегии, и второй игрок всегда сможет выиграть при правильной игре.

2. Для второй игры, где на столе лежит 107 спичек и можно брать 1 или 2 спички за один ход, также воспользуемся методом обратной индукции. Аналогично предыдущему случаю, рассмотрим несколько начальных позиций:

• Если на столе лежит 1 спичка, то первый игрок обязательно проигрывает.
• Если на столе лежат 2 спички, то первый игрок также проигрывает, потому что независимо от того, сколько спичек он возьмет (1 или 2), второй игрок возьмет оставшуюся спичку и выиграет.
• Если на столе лежат 3 спички, то первый игрок может взять 1 или 2 спички. В любом случае второй игрок сможет выиграть, возьмя оставшуюся спичку.
• Если на столе лежат 4 спички, то первый игрок может взять 1 или 2 спички. Если он возьмет 1 спичку, то на столе останется 3 спички, и второй игрок обязательно проиграет. Если первый игрок возьмет 2 спички, то на столе останется 2 спички, и второй игрок также проиграет.

Мы видим, что если на столе количество спичек кратно 3 (т.е. 3, 6, 9 и т.д.), то первый игрок проигрывает, в противном случае он может выиграть. Так как в начальной позиции у нас 107 спичек (которое не кратно 3), то первый игрок имеет выигрышную стратегию, и он сможет выиграть при правильной игре.