A Combinatorial Game

Question

The following is a combinatorial game that I read about in a mathematical olympiad preparation book some time ago. I have forgotten the exact rules of this game, but the general idea of the problem goes something like this:

Two players A and B take turns placing counters on a 5 by 5 grid. Player A always goes first. Each turn, the player has the choice of placing either 1, 2 or 3 counters on the grid. The winner of the game is the person who has an even* number of tokens after all the squares on the grid have been used up.

*Due to the fact that I first read this problem several years ago, I am unable to remember whether the winner of the game was the one with an even or an odd number of tokens at the end of the game.

However, I am fairly certain that there was a winning strategy for player B. I have been unable to prove why that should be so for either case or find the original statement of the game. Has anyone seen this problem before? Does anyone have any idea of how to find a winning strategy for either case? Any help would be greatly appreciated.

Answer 1

Person $B$ has a winning strategy as the game rules stand right now (you win if you have even number of stones in the end). A $1$ is always answered by a $3$, and a $3$ by a $1$, but a $2$ is answered by a $1$ or $3$, depending on how many squares are left. I guess the easiest criterion to do mentally here is "whichever makes the number of squares left congruent to $0$ or $1$ modulo $4$".

If it is your turn and you have an even number of stones on the board, then you lose if there are $1$ or $4$ vacant squares left modulo $8$, and if you have an odd number of stones on the board, you lose if there are $0$ or $5$ squares left modulo $8$.

For instance, if you are at $0$ squares left modulo $8$ and you have an odd number of stones on the board, then either the game is over, and you've lost, or you have to put down stones. If you put down $2$ stones, then your opponent puts down $1$, and you're at odd stones, $5$ modulo $8$ squares left. If you put down $1$ or $3$, then you have an even number of stones on the board, and your opponent can make it $4$ squares left, modulo $8$.

The three other cases have to be checked as well, of course.

Having $0$ stones on the board (which is even) and $25\equiv 1$ squares left is a losing position, and if $A$ started out in one of the four losing positions, $B$ can force him back no matter what $A$ tries.

Answer 2

Suppose it's your turn to move and there are already $x$ tokens on the grid; moreover, use $e/o$ to denote whether the number of your token already on the grid is $e$ven or $o$dd.

For example, $24e$ means that there are 24 counters on the grid and that you have put down an even number. The only move left for you is to place $1$ token: $24e \rightarrow 25o$ and you have lost. Then $24e$ is a $L$osing position. In short:

$24e$ is $L$.

$24o$ is a $W$inning position: put down a token and close the game in $25e$.

$23e$ is $W$: put down two tokens and close the game in $25e$.

$23o$ is $W$: put down one token, forcing your opponent into $24e$ which is a losing position.

$22e$ is $W$: put down two tokens, forcing the opponent into $24e$.

$22o$ is $W$: put down three token and get $25e$.

$21e$ is $L$: no matter how you play, the opponent will be in $22o$ (22 tokens on the grid, and she has an odd number) or $23o$ or $24o$ which are all winning positions for her.

$21o$ is $W$: put down three tokens, forcing the opponent into $24e$.

$20e$ is $W$: put down one token, forcing the opponent into $21e$.

$20o$ is $L$: no matter how you play, the opponent will be in $21o$ or $22o$ or $23o$.

$19e$ is $W$: put down one token, forcing the opponent into $20o$.

$19o$ is $W$: put down two tokens, forcing the opponent into $21e$.

$18e$ is $W$: put down three tokens, forcing the opponent into $21e$.

$18o$ is $W$: put down two tokens, forcing the opponent into $20o$.

$17e$ is $W$: put down three tokens, forcing the opponent into $20o$.

$17o$ is $L$: no matter how you play, the opponent will be in $18e$ or $19e$ or $20e$.

$16e$ is $L$: no matter how you play, the opponent will be in $17e$ or $18e$ or $19e$.

$16o$ is $W$: put down one token, forcing the opponent into $17o$.

The rest of the pattern is clear: the next losing positions are $13e, 12o, 9o, 8e, 5e, 4o, 1o, 0e$. Player opens the game in $0e$ so he starts in a losing position. Playing optimally, B is guaranteed a win.

(Note: this technique is called backwards induction. I recall similar questions being asked on SE, but I cannot find a proper duplicate. See f.i Try not to get the last piece, but with a twist! [Game Theory])

Answer 3

Let's look at the game from Player A's point of view. At any stage in the game, there are $N$ grid cells left open, and Player A's state can be described as either "Even" or "Odd," depending on whether he has accounted for an even or an odd number of occupied cells. (As I mentioned in a comment below the OP, I prefer to think of the game in take-away format, with each player removing $1$, $2$, or $3$ counters from an initial pile of $25$, but I'm sticking with the OP's description to avoid any confusion.) Obviously, Player A Wins if there are no cells left open and he is in the Even state, and he Loses if there are no cells left open and he is in the Odd state.

In general, Player A can either stay in the state he is currently in by playing $2$ counters, or reverse his state by playing either $1$ or $3$ counters. Player A will remain in that state regardless of how many counters his opponent plays. This makes it possible to create a table of Win/Loss outcomes for A:

$$\pmatrix{&0&1&2&3&4&5&6&7&8&9&10&11&12&\cdots\\ E&W&L&W&W&L&W&W&W&W&L&W&W&L&\cdots\\ O&L&W&W&W&W&L&W&W&L&W&W&W&W&\cdots\\}$$

For example, the next column, for $N=13$, is a Win for the Even state, because Player A can play one counter, taking himself to the Odd state, thereby landing in either $(11,O)$, $(10,O)$, or $(9,O)$, all of which are Winning positions, after Player B plays $1$, $2$, or $3$ counters. But $(13,O)$ is a Loss: If Player A plays $2$ counters, Player B can send him to the Losing state $(8,O)$ by playing $3$ counters, while if he plays $1$ or $3$ counters, his opponent can send him to the Losing state $(9,E)$ by playing $3$ or $1$ counters. (Note: The first few columns of the table have fewer options to consider.)

A casual inspection of the table observes a regularity in the entries, and a bit of reflection concludes the pattern will persist: there is repetition with period $8$. Consequently, for the OP's game, Player A's opening position is $(25,E)$, which is a Loss, since $25\equiv1$ mod $8$ and $(1,E)$ is a Loss.

Remark: If you reverse the criterion for winning to playing an Odd number of counters, it turns out the table simply swaps the two rows. In that case, the game starting from $N=25$ is a Win for Player A.