# Does Alice has a winning strategy?

There are $n$ stones, Alice and Ben are playing a game that, each one take some stones in turn, and each turn one can only take 1, 2, 4, or 6 stones, the one take the last stone wins. If Alice is the first one to take stones, does she has a winning strategy, and how many stones shall A take in the first turn?

Note: It's similar to game Nim, but here only 1,2,4, or 6 are allowed.

Note2: I don't know which math area this quiz falls into, by my best guess I tagged it as "group theory".

• Not if $n=3$. There are always partitions of n into an odd number of parts otherwise.
– JMP
Feb 5, 2015 at 10:26
• Hint : use the mex ! en.wikipedia.org/wiki/Mex_(mathematics)
– Xoff
Feb 5, 2015 at 10:38
• It depends on $n$, right? So you want to know, for which values of $n$ Alice loses? Um, $n=0,3,8,11,16,19,24,\dots$.
– bof
Feb 5, 2015 at 10:51

There is a whole theory of such games, based on the mex operation, etc. But such games are analysed recursively. Call a number $n$ "good" if a player wins when he/she finds that number of stones when moving, and "bad" otherwise.

By definition of the game, $0$ is bad and $1,2,4,6$ are good, as a player can take all of them in that turn and win. So the first interesting number is $n=3$, where the player that has the turn has the options to take 1 or 2, and $3-1 = 2$ is good (so bad for the current player, as it's now the other player's turn!) and $3-2 = 1$ is good (same remark). So $3$ is bad, because all possible moves lead to "good" numbers for the other player.

On the other hand, if we have $n$ stones, and at least one of $n-1, n-2, n-4, n-6$ is bad, then $n$ is good, because the player moves to the bad number. So $n=5$ has a move to the bad number $n=3$, namely move 2, and so $n=5$ is good (and the wining move is $2$).

You can continue that way: assume you know for all numbers $<n$ whether they are good are bad. Then consider $n-1, n-2, n-4, n-6$. If one of them is bad, $n$ is good, and you know the winning move. If on the other hand all are good, $n$ is bad, and the player who has to play starting from that number always loses (against optimal play).

General theory says that the sequence of good/bad numbers will be periodic eventually (in this case, the numbers that are 0 and 3 modulo 8 are bad), and then you can prove the periodicity by induction, if you like.

• May I ask what is "General theory", is it a theory or just a general term? Feb 7, 2015 at 10:48
• The Sprague-Grundy theorem says that the value of a heap is some "nimber" (value of a classical nim heap), and there is a large class of spaces where this "nim"-sequence becomes periodical, and there is an open problem that states whether all finite so-called "octal games" have eventually periodic nim-sequences. I think for these games, where we have no breaking of heaps, this is true. See the book(s) "Winning Ways for your Mathematical Plays". Feb 7, 2015 at 11:57
• thank you for the explanation! Feb 8, 2015 at 7:34