Имеется кучка из $M$ спичек и лист бумаги, на котором написано число $M$. Двое играют в такую игру. Ходят по очереди. Ход состоит в том, что игрок берёт из кучки или возвращает в кучку от 1 до $k$ спичек и записывает на листе, сколько спичек стало в кучке. (Вначале все имеющиеся спички лежат в кучке — у игроков спичек нет.) Проигравшим считается тот, кто не может сделать ход или вынужден записать число, уже имевшееся на листе ранее. Кто из игроков выигрывает при правильной игре, если
Ответ: начинающий игрок (назовём его $A$) выигрывает во всех случаях, когда $M$ не делится на $m=4{\left[\dfrac k2\right]}$, т. е. на $m=4$ при $k=2$ и на $m=8$ при $k=5$; если $M$ кратно $m$, то выигрывает второй игрок (назовём его $B$).
Идея выигрышной стратегии игрока $B$ при $M$ кратном $m$ ($M=ms$) относительно проста. Все числа от $M-1$ до 0 разбиваются на пары, и на каждый ход соперника игрок отвечает выписыванием парного числа. Сложность в том, чтобы гарантировать возможность ответа на любой ход, а для этого при $k\gt2$ разбиение приходится производить постепенно, в зависимости от ходов $A$.
Пусть теперь $M$ не кратно $m$: $M=ms+n$. Если $1\le n\le k$, то игрок $A$ первым ходом берёт $n$ спичек, а дальше действует по выигрышной стратегии второго игрока для $M=ms$. Если же $M=ms+n$, где $k\lt n\lt m$, то $A$ сразу начинает играть по этой стратегии для $M=m(s+1)$, условно считая, что первым ходил $B$, взяв $m-n$ спичек ($m-n\lt2k-k=k$). Это обеспечило бы выигрыш $A$, даже если бы у $B$ действительно были эти $m-n$ спичек, и тем более, когда их у $B$ нет.
Теперь объясним подробнее, как должен играть второй игрок при $M=ms$, если а) $k=2$ и б) $k=5$.
$A$ — первый ход игрока $A$ в восьмёрку $(8n-1,8n-8)$, $B$ — ответ игрока $B$; дужками показано разбиение на пары; $p$ — запас спичек у игрока $B$, создаваемый после первого ответа, $q$ — запас спичек, достаточный для повторных ответов.
а) Разобьём числа от $M-1$ до 0 на четвёрки последовательных чисел ($M=4s$), а каждую четвёрку — на две пары вида $(4n-1,4n-3)$ и $(4n-2,4n-4)$. На каждый ход $A$ игрок $B$ отвечает парным числом, поэтому новую четвёрку всегда будет «открывать» $A$, выписывая одно из двух её старших чисел — $4n-1$ или $4n-2$. После своего ответа на этот ход игрок $B$ приобретёт 2 спички, которые он зарезервирует для ответа на возможный повторный ход $A$ в эту четвёрку (если это будет ход $4n-3$ или $4n-4$). Таким образом, для $B$ всегда обеспечен ответный ход, а значит, и общий выигрыш.
б) Стратегия второго игрока при $k=5$ в целом такая же, как и при $k=2$. По-другому только делается разбиение на пары. Из чисел от 0 до $M-1$ образуются не четвёрки, а группы по $m=8$ штук. Каждая восьмёрка разбивается на пары после того, как будет выписано какое-то число из неё. Как и в п. а), это будет одно из $k=5$ старших чисел этой восьмёрки и выпишет его игрок $A$. Ответ $B$ и разбиение на пары для всех пяти вариантов приведены на рисунке. Коротко можно сказать так: в ответ на ход, «открывающий» новую группу, игрок $B$ выписывает наименьшее возможное число из этой группы, а оставшиеся её $m-2$ чисел разбивает на пары соседних (без учёта двух выписанных). Это правило годится для всех значений $k$. Запаса спичек, создаваемого после первого ответного хода $B$, будет достаточно, чтобы обеспечить возможность ответа на все дальнейшие ходы $A$ в эту группу; при $k=5$ это видно непосредственно из рисунка (запас состоит из 5, 4 или 3 спичек), а в общем случае это несложно проверить, причём здесь важно, что $m=4{\left[\dfrac k2\right]}$.
Таким образом, ответ, сформулированный в начале решения, справедлив при всех значениях $k$.
