Misère picking stones game with labels

65 Views Asked by At

Alice and Bob are playing a picking stones game with a pile of n stones labeled from '1' to 'n'. The rule is simple: Alice and Bob alternately take off 1 arbitrary stone or 2 consecutive stones(e.g. take off 2 stones labeled by '3' and '4', but '3' and '5' are not considered consecutive even if '4' has been taken). Whoever takes the last stone loses. Alice takes first. Proof that Alice always has a winning strategy for all n other than 1,4,9,12,20.

I personally think this must have been understood already, so references are also very welcome.

1

There are 1 best solutions below

1
On BEST ANSWER

This game is commonly known in combinatorial game theory as Kayles. And, yeah, it is well-explored. This seems to be a short paper on the process, although I haven't read it myself.