Ответ: начинающий игрок (назовём его $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$.
а) Разобьём числа от $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$.
