Задача М8‍‍

Для того чтобы говорить об игре, необходимо как-то назвать её участников. Условимся раз навсегда называть одного из них Я, а другого Он.

Прежде всего немного обобщим условие задачи. Число $N$‍‍ спичек, лежащих на столе в начале игры, может быть любым, а не только нечётным. При этом для чётных $N$‍‍ один из игроков выигрывает, если в конце игры у обоих чётное число спичек, а другой — если нечётное.

Мы рассматриваем, строго говоря, сразу бесконечное число игр, так как $N$‍‍ и $m$‍‍ могут быть любыми натуральными числами. Даже если $m$‍‍ и $N$‍‍ заданы, возможны два варианта: Я выигрываю, если в конце игры у меня 1) чётное, 2) нечётное число спичек.

Будем говорить сначала обо всех вариантах этой игры вместе.

Давайте подумаем о том, что надо помнить игроку в ходе игры. Надо ли ему помнить все его ходы и ходы его противника с начала игры? Нет, в любом варианте ему достаточно знать следующее:

1. сколько осталось спичек на столе,
2. чётное ли у него число спичек,
3. чей ход.

Если заданы эти три параметра, то мы будем говорить, что задано состояние игры. В каждом таком состоянии игрок может сделать $m$‍‍ разных ходов (или меньше, если на столе осталось спичек меньше чем $m$‍).‍ Каждый его ход переводит игру в другое состояние, когда ходит его партнёр.

Состояния игры удобно изображать на бумаге в виде клеточек или кружочков, а возможные ходы в виде стрелок. Так мы и сделаем.

Таблица на рисунке 1 составлена для случая, когда $m=2$‍‍ (можно брать только одну или две спички за ход), и Я выигрываю, если в конце игры у меня чётное число спичек. Фактически нарисованы только те состояния, когда на столе осталось не более семи спичек.

Цветные стрелки показывают, как игроки могут ходить: игрок, чей ход в этой клетке, может пойти по любой стрелке, из неё выходящей. Например, первая слева клетка в строчке с номером 5 (серая) соответствует тому состоянию игры, когда на столе осталось 5 спичек, у меня чётное число спичек и мой ход, а две выходящие из этой клетки стрелки показывают, в какие состояния Я могу перевести игру очередным ходом.

Таблицу можно продолжать вниз сколько угодно далеко. Стрелки, выходящие из любой клетки, получаются параллельным сдвигом из стрелок, выходящих из какой-то одной клетки того же самого столбца (в верхних двух клетках некоторые стрелки, разумеется, «выпадают»).

Назовём состояние выигрышным и поставим в соответствующую ему клетку букву В, если, когда игра начинается из этого состояния, Я могу выиграть, как бы Он ни старался мне помешать.

Назовём состояние проигрышным и поставим в соответствующую ему клетку букву П, если, когда игра начинается из этого состояния, Он может выиграть и, если Он не ошибётся, Я не смогу этому воспрепятствовать.

Приступим теперь к основной части решения: расставим во все клетки таблицы буквы В и П. Мы сделаем это сначала для игры, соответствующей рисунку 1. В нулевой строке буквы, конечно, надо поставить так: ВВПП, поскольку мы считаем, что Я выиграл, если в конце игры у меня чётное число спичек. Дальше буквы надо расставлять сверху вниз по следующему закону.

Поскольку все стрелки в таблице ведут снизу вверх, то этот закон даёт возможность заполнять всю таблицу, сколько бы мы её ни продолжали.

В нашем случае ($m=2$‍)‍ для того, чтобы заполнить клетки $n$‍‍-й строки, достаточно знать только, как заполнены клетки $(n-1)$‍‍-й и $(n-2)$‍‍-й строк. В действительности вовсе не нужно чертить все стрелки, как на рисунке 1. Достаточно отдельно (на куске кальки) начертить «шаблон» — совокупность стрелок, выходящих из клеток одной строки, и, прикладывая этот шаблон по очереди ко всем строкам таблицы, заполнять их буквами В и П, следуя правилу, выписанному на голубом фоне. На рисунке 2 показан тот момент, когда мы заполнили всю таблицу до 5-й строки и готовы заполнять 6-ю. Так можно заполнить таблицу до любого места, например до 25-й строки и посмотреть, какая буква будет стоять в 25-й строке на первом месте. Если это В, то игру, в начале которой на столе лежит 25 спичек, начинающий выигрывает, а если это П, то проигрывает.

На самом деле, дальше пятой строки таблицу заполнять не нужно. Дело в том, что 4-я строка совпадает с нулевой, а 5-я с первой. Поэтому 6-я обязательно совпадёт со 2-й (так как каждая строка определяется двумя предыдущими). Тогда 7-я строка совпадёт с 3-й, 8-я с 4-й, 9-я с 5-й и т. д. Строки будут повторяться с периодом 4, откуда следует, что всякая

строка с номером $4k$‍‍ будет ВВПП;

строка с номером $4k+1$‍‍ будет ПВВП;

строка с номером $4k+2$‍‍ будет ВПВП;

строка с номером $4k+3$‍‍ будет ВПВП.

В частности, 25-я строка будет ПВВП ($25=4\cdot6+1$‍).‍

То, что период обязательно должен быть, можно было предвидеть заранее. Действительно, пусть мы заполнили таблицу до какой-то строки. Дальше всё зависит от того, как заполнены две последние строки. Число всех способов заполнить две строки буквами П и В конечно (оно заведомо не больше 28). Значит, при заполнении таблицы не может всё время появляться новая пара строк. А когда какая-то пара строк повторится, начнётся периодичность.

После того как в таблице расставлены буквы В и П, становится ясной и стратегия, которой Я должен придерживаться, чтобы выиграть: нужно каждый раз делать такой ход, который ведёт в клетку с буквой В. Закон расстановки букв В и П, указанный выше, составлен именно так, что если Я один раз попал в клетку В, то дальше Я смогу каждый раз ходить в В, и противник не сможет мне помешать.

Случай, когда Я выигрываю, если у меня в конце нечётное количество спичек, исследуется аналогично. Можно поставить в нулевой строке ППВВ и заполнять дальше таблицу по тому же самому закону. Период снова будет равен 4. Но можно всего этого и не делать, а использовать для этого случая тот же рисунок 2.

Заметим, что не дать игроку перед началом игры ничего и потребовать, чтобы у него в конце было нечётное число спичек, это всё равно, что дать ему перед началом игры одну спичку и потребовать, чтобы у него в конце игры было чётное число спичек. Таким образом, в этом новом случае Я выигрываю, если в таблице на рисунке 2 в клетке на пересечении $N$‍‍-й строки и

IV столбца стоит В, если Я начинаю,

V столбца стоит В, если Он начинает.

Заметим также, что шаблон не изменится, если поменять местами II столбец с IV, а III с V. В первой строке после такой перестановки вместо ВВПП будет стоять ППВВ. Поэтому таблицу для того случая, когда Я, чтобы выиграть, должен забрать нечётное число спичек, можно получить из таблицы для разобранного случая указанной перестановкой столбцов. Это же относится и ко всем другим значениям $m$‍.‍

Пусть теперь $m=3$‍.‍ Таблица по-прежнему будет состоять из тех же четырёх столбцов. Шаблон изменится (см. рис. 3). Теперь каждая строка зависит от предыдущих трёх строк. Для расстановки букв В и П применимо правило, выписанное на голубом фоне. Расставляя буквы, мы убеждаемся, что период состоит из восьми строк. В частности, 25-я строка совпадает с первой: ПВВП.

Таким образом, в случае $m=3$‍‍ и $N=25$‍‍ получается такой

Ответ: если выигравшим считается игрок, забравший чётное число спичек, то начинающий проигрывает, а если выигравшим считается забравший нечётное число спичек, то начинающий выигрывает.

Общий случай исследуется аналогично. Длина периода оказывается равной $m+2$‍,‍ если $m$‍‍ чётно, и $2m+2$‍,‍ если $m$‍‍ нечётно. Эти периоды изображены на рисунках 4, а, б. Шаблоны, данные для $m=8$‍‍ и $m=9$‍,‍ позволяют понять, какими будут шаблоны в общем случае. Рисовать стрелки здесь было неудобно. Клетки, закрашенные каждым цветом, — это состояния, в которые может пойти игрок из клетки, в которой стоит точка того же цвета. Правила расстановки букв В и П те же самые, выписанные на голубом фоне. Проверку того, что периоды действительно таковы, предоставим читателю. Заметим только следующее. Чтобы быть уверенным в том, что период будет повторяться, необходимо проверить расстановку букв во всех строках первого периода и в $m$‍‍ первых строках второго периода.

Как видим, при больших $m$‍‍ чаще всего кто начинает, тот и выигрывает. Все буквы, нарушающие это правило, на рисунках 4, а, б обведены кружками. Итак, начинающий проигрывает только в следующих случаях: $$ \begin{array}{l|c|c} \hline &&\\[-6pt] &\text{Выигрывает наб-}&\text{Выигрывает наб-}\\ &\text{равший «чёт»}&\text{равший «нечёт»}\\[-6pt] &&\\ \hline &&\\[-6pt] m~\text{чётно}&N~\text{даёт остаток}&N~\text{даёт остаток}\\ &1~\text{при делении}&m+1~\text{или}~0~\text{при}\\ &\text{на}~m+2&\text{делении на}~m+2\\[-6pt] &&\\ \hline &&\\[-6pt] m~\text{нечётно}&N~\text{даёт остаток}&N~\text{даёт остаток}\\ &1~\text{или}~m+1~\text{при}&0~\text{или}~m+2~\text{при}\\ &\text{делении на}~2m+2&\text{делении на}~2m+2\\[-6pt] &&\\ \hline \end{array} $$