Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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".
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.
