Игра 3: общий случай

Допустим, что на столе m фишек и каждым ходом можно брать от 1 до n фишек (n < m). Выигрывает тот, кто забирает последнюю фишку. Для какого из игроков существует выигрышная стратегия — для первого или второго? В чем она заключается? Если игрок, взявший последнюю фишку, будет проигрывать, как изменится стратегия?

Речь идет не об одной игре, а о группе абстрактных игр. Две предыдущие игры — ее частные случаи. Следовательно, выигрышная стратегия для этой игры — это общая стратегия, которая применима к бесконечному множеству аналогичных игр. Эта стратегия формулируется так. Поделим m на n + 1 и определим остаток от деления. Он будет находиться в интервале от 0 до n. Возможны два случая:

1. Остаток от деления равен 0. В этом случае существует выигрышная стратегия для второго игрока, который должен оставлять на столе число фишек, кратное n+1. Для этого на каждом ходу, если первый игрок берет p фишек (0<p<n+1), второй должен брать n+1—p фишек. Это число всегда положительно, так как находится на интервале от 0 до n.

2. Остаток от деления равен r(0<r<n+1).В этом случае существует выигрышная стратегия для первого игрока. На первом ходу он должен взять r фишек, оставив на столе число фишек, кратное n+1. Теперь он может действовать подобно второму игроку из первого случая. Иными словами, если второй игрок берет p фишек (0<p<n+1), первый должен взять n+1—р.

Это общее решение применимо к бесконечному множеству игр. Читатель может применить его для такой игры: на столе 2010 фишек, на каждом ходу можно брать от 1 до 49 фишек. Для какого игрока существует выигрышная стратегия? В чем она заключается? Если мы изменим правила и тот, кто берет последнюю фишку, будет проигрывать, то достаточно заметить следующее: для победы будет достаточно взять предпоследнюю фишку, оставив на столе всего одну. В этом случае стратегия не изменится, просто нужно будет учесть, что число фишек равно m - 1, а не m.

Все подобные игры, в которых используется только одна группа фишек, можно считать упрощенными вариантами игры Ним, о которой мы поговорим далее.