Lino vs. Calvin

The $5 \times 5$ grid game is a two-player game of perfect information that is impartial (both players can make the same moves at each position), follows the normal play convention (the first player who cannot move loses), and has all games come to an end. By the Sprague-Grundy theorem , each position can be assigned a nim-value, or an equivalent Nim heap size. The nim-value of all final positions (here the upper-right corner) is 0, and the nim-value of all other positions is the minimum nim-value that cannot be reached with any subsequent move. The nim-values for this game are the following:

1 0 2 1 0

2 0 3 2 0

1 0 3 1 0

2 0 3 2 0

1 0 3 1 0

Lino and Calvin play two of these games simultaneously, so the nim-value of the resulting game is the binary exclusive-or of the two positions of the red and blue discs. A nim-value of 0 is a losing position for the first player, and this happens if and only if the nim-values of the red and blue discs are the same. Since there are ten 0s, six 1s, five 2s, and four 3s, there are $10^2 + 6^2 + 5^2 + 4^2 = 177$ positions in Lino and Calvin's game where the nim-value is 0, and the first player to move loses. Thus, there are $625 - 177 = 448$ winning positions for the first player.

We color the grid's unit squares as follow : image link .

Firstly, we consider the case which the tokens both start in black squares. Whenever the first player moves one of the tokens, the second player can move that token into a black square again. Therefore, after each turn, the tokens will remain in black squares. Then, with any positions of the tokens that both start in black squares, we can switch to the case the tokens are already in the top right square. In this case, the first player loses.

If there is only one token starts in one of the black squares, and the other token starts in a white or blue square, the first player can move the token which does not start in a black square into a black square. Therefore, the second player will lose, as we have already considered above. We have $2 \times 10 \times 15 = 300$ positions.

Otherwise, if both tokens do not start in black square, the players have to avoid moving tokens into black square, unless they want the other to win. Therefore, the players will move the tokens inside the first, third and fourth column (count from left to right) only, now we consider the $5 \times 3$ grid consists of these column.

If both tokens start in blue squares, by similar arguments as above, the first player will lose.

If there is exactly one token start in a blue square, the other tokens start in a white square, by similar arguments as above, the first player will win. There are $2 \times 6 \times 9 = 108$ positions.

Now we consider the most complicated case : both tokens start in white squares. As mention above, the player will have to move the tokens inside white square. Consider three special positions of the white squares : the fourth squares of the second and fourth rows (count from top to bottom) and the middle square of the first row, we shall call these squares as "dead-end" squares. If both tokens start in, or moved into one of these "dead-end" squares, it can not move anymore (into a white square again), therefore the first player will lose. Within the white squares, the player can move the tokens one unit only. If after an odd number of moves, both tokens move into "dead-end" squares, the first player will win, otherwise, the second player will win. We can count the number of position such that after an odd number of moves, both tokens move into "dead-end" squares, there are $40$ cases only.

Therefore, there are $300+108+40=448$ starting position such that the first player will win.

First, we consider the case where there is only one token on the $5\times 5$ grid. We define a square to be winning square if the player who starts the game can have winning strategy when the token is placed on that square, and losing square otherwise. Note that this implies two properties:

1. From a winning square, the player can move the token to a losing square, and

2. From a losing square, either the player cannot make a move or the player can only move the token to a winning square.

For convenience, number the squares from $1$ to $25$ from bottom to top, left to right. So bottom-left square is number $1$ , top-right square is number $25$ , bottom-right is number $5$ , etc. And we say a token a winning token if it's placed on a winning square, similarly for losing token.

Notice that the square $25$ is a losing square, since the player cannot make any move. Then it's easy to see that square $23$ and $24$ are winning square, since the player can move the token to the losing square. Then square $22$ is a losing square, since the player can only move to a winning square. If we continue this way, we can mark the grid as follows:

$\begin{array}{|c|c|c|c|c|}\hline W & L & W & W & L \\ \hline W & L & W & W & L \\ \hline W & L & W & W & L \\ \hline W & L & W & W & L \\ \hline W & L & W & W & L \\ \hline \end{array}$

Now we consider the case when there are two tokens on the grid. There are 3 cases:

1. If the two tokens are both in losing squares, then the player to move will lose, since the player either cannot make a move or it will move one of the token to a winning square (by property 2), and by property 1 the opponent will always have a move that brings the token to a losing square.

2. If one of the tokens is in losing square, and the other in winning square. Then the player to move will win, since by property 1 the player will be able to move the winning token to a losing square, facing the opponent with case 1. Since there are $10$ losing squares and $15$ winning squares, there are $2\cdot 10\cdot 15 = 300$ winning positions in this case for first player.

3. If the two tokens are both in winning squares. In this case, if the player move either of the winning tokens to a losing square, the opponent will win. So the optimal strategy would then requires the player to move a winning token to another winning square. Then we consider a sub-grid which contain only the winning square. This gives us a $5\times 3$ grid from the first, third, and fourth column of the original grid. Now we define a sub-game, which is played on this sub-grid, where the valid moves are move the token one unit to the right, or move the token to the left-most square of above row. Note that this fully captures the available moves on the winning square with optimal strategy.

Again we do the same as previously, considering the case of one token on this sub-grid, marking each square with winning square or losing square, as follows:

$\begin{array}{|c|c|c|}\hline L & W & L \\ \hline W & W & W \\ \hline L & W & L \\ \hline W & W & W \\ \hline L & W & L \\ \hline \end{array}$

Note that the two properties still hold in this sub-game.

So with two tokens we again have 3 cases:

1. The two tokens are on losing squares. Similar to the full game, the player to move will lose.

2. One of the tokens is on losing square, and the other on winning square. Similar to the full game, the player to move will win. There are $6$ losing squares and $9$ winning squares so there are $2\cdot 6\cdot 9=108$ winning positions in this case for first player.

3. Both of the tokens are on winning squares. Note that in this sub-game, from a winning square (except the top winning square and the right-most squares on row 2 and 4) there is only one possible winning square to move to. If we number the winning squares of this sub-grid $W_1,\ldots W_9$ from bottom to top, left to right, this relation can be visualized by this sequence: $W_1\rightarrow W_2\rightarrow W_3\rightarrow W_4, W_5\rightarrow W_6\rightarrow W_7\rightarrow W_8, W_9$ , where arrow means there is a move between the two squares. If we again consider a sub-sub-game of this, we can easily see that $W_9, W_8, W_6, W_4, W_2$ are losing squares, and the rest are winning squares, and that this sub-sub-game has additional property that from any winning square, a player can only move to a losing square, and vice-versa. So again considering the three cases of location of the two tokens, first player will win if and only if one of the tokens is on losing square, and the other on winning square. Since there are $5$ losing squares and $4$ winning squares, there are $2\cdot 5\cdot 4=40$ winning position in this case for first player.

Finally, combining the three results that we have, the total number of winning positions is: $300+108+40 = 448$

Additional interesting note:

Based on the above result, we can give three-bit binary number for each square, representing the winning (1) or losing (0) square of that square for each game, sub-game, and sub-sub-game, where the most significant bit represent the game, second bit the sub-game, and the least significant bit the sub-sub-game. The first player has a winning strategy if and only if the binary number of the two squares of the two tokens are different. The numbers will be as follows:

$\begin{array}{|c|c|c|c|c|}\hline 100 & 000 & 110 & 100 & 000 \\ \hline 110 & 000 & 111 & 110 & 000 \\ \hline 100 & 000 & 111 & 100 & 000 \\ \hline 110 & 000 & 111 & 110 & 000 \\ \hline 100 & 000 & 111 & 100 & 000 \\ \hline \end{array}$

So there are $10\times (000), 6\times (100), 5\times (110), 4\times (111)$ , where twice the sum of pair-wise product gives us the answer $448$ as well. This notation makes it easier to judge which player has winning strategy depending on the initial positions of the two tokens just by looking at the table above.

Colour the 2nd and 5th column white, the 1st, 3rd, 4th column black. Observe that any move from a white column moves to black column, and from any black square there exists a move to a white square.

Define a 'good position' as one where one token is on a black square and one token is on a white square - note that a move is always possible in a good position.

Observe then that if player 1 moves from a good position, he can then move such that both tokens are on white squares - this means that after player 2 moves, one token is on a black square and the other on a white square - a good position again. Thus a good position is winning for the player moving. Also, if both tokens are on white squares, the position is losing for the player who has to move.

We now consider the case where both tokens are on black squares. We can ignore moves to white squares, because such moves are losing as proven above. Thus, reduce the grid to a new one of 3x5 with columns 1,3,4 - relabel them as columns 1,2,3.

Denote the squares as follows: Column 1 consists of (3,6,9,12,15), Column 2 consists of (2,5,8,11,14), Column 3 consists of (1,4,7,10,13). The top row is (3,2,1) and the bottom row is (15,14,13)

Recursively fill in a 15x15 grid as follows:

1. (x,x) is losing - since the second player can just mirror the move of the first on the other token.

2. Any position that can move to a losing position is winning. Any position that only has moves to winning positions is losing - this is standard for recursive solutions of games like this.

3. (x,y) = (y,x)

We can fill this grid by considering (1,x) for x from 1 to 15, then continuing on for (2,x), (3x)...until (15,x) (Note that a valid move is from x to x-1, or from 3a+b to 3a where 5> a > 0 and 0 < b < 4)

We denote '1' for a winning position and '0' for a losing position.

Denote P_n as [(n,1), (n,2) .... (n,15)]

P_01 = [ 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 ]

P_02 = [ 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 ]

P_03 = [ 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 ]

P_04 = [ 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 ]

P_05 = [ 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 ]

P_06 = [ 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 ]

P_07 = [ 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 ]

P_08 = [ 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 ]

P_09 = [ 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 ]

P_10 = [ 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 ]

P_11 = [ 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 ]

P_12 = [ 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 ]

P_13 = [ 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 ]

P_14 = [ 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 ]

P_15 = [ 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 ]

Therefore the number of winning positions is $15*10*2 + 148 = 448$ since there are 15 black and 10 white squares corresponding to 300 combinations, and 148 more from the grid.

Look at the Grundy function of the single-counter game. As usual, this is defined recursively for each square on the board as the mex (minimum excluded value) of the Grundy values of each square that can be reached from that square by a single move. We obtain the following table of values: $\begin{array}{|c|c|c|c|c|}\hline 1 & 0 & 2 & 1 & 0 \\ \hline 2 & 0 & 3 & 2 & 0 \\ \hline1 & 0 & 3 & 1 & 0 \\ \hline 2 & 0 & 3 & 2 & 0 \\ \hline1 & 0 & 3 & 1 & 0 \\ \hline \end{array}$ Winning positions are those with a nonzero Grundy number; losing positions are those with a Grundy number of $0$ .

The Grundy value of a position in the two-counter game is just the Nim-sum of the Grundy values of each counter; winning positions are again those with a nonzero Grundy value, and losing positions are those with a Grundy value of $0$ . Since the Nim-sum $a\oplus b$ of two numbers is equal to $0$ precisely when $a=b$ , it is clear that the losing positions in the two-counter game are those where the Grundy values for the two counters are the same.

In the single-counter game, there are $10$ positions with Grundy value $0$ , $6$ positions with Grundy value $1$ , $5$ positions with Grundy value $2$ and $4$ positions with Grundy value $3$ . Thus there are $10^2+6^2+5^2+4^2=177$ losing positions in the two-counter game. Thus there are $448$ winning positions in the two-counter game. Thus $448$ of the possible opening positions are winning positions for the first player.

We can easily work out the Grundy number of each square on the board. It turns out that there are 10)\, \(6 , $5$ and $4$ squares with Grundy number zero, one, two and three respectively.

Now, the first player wins iff the two counters are on squares with different Grundy numbers. There are precisely $10 \times 15 + 6 \times 19 + 5 \times 20 + 4 \times 21 = 448$ such ways. Thus, the answer is $448$ .

We assign a number to each square in the grid as follows:

$1 0 2 1 0$

$20320$

$10310$

$20320$

$10310$

If both tokens are on the same number, then the next move (if there is one) must put them on two different numbers. On the other hand, if they are on an $n$ -square and an $m$ -square with $m<n$ , then there is a move that puts them both on $m$ -squares. Therefore, a starting position is a winning position for the first player if and only if the tokens are on different numbers, and there are

$25^2-(10^2+6^2+5^2+4^2)=448$

such positions.

The question asks us to analyze how many combinations of two impartial combinatorial games lead to a winning state for the first player. Sprague Grundy tells us that the combined game will be a winning position for the first player iff the binary sum of the grundy number (nimber) of the two game states is non-zero.

We can calculate the Grundy number of each of the 25 token positions readily using the mex operation (the grundy number for a game state is the minimum non-negative integer not accessible in one move).

   12345
1: 10210
2: 20320
3: 10310
4: 20320
5: 10310

Two integers will have a binary sum of 0 iff they are equal. Therefore we just subtract from 25*25 the number of ways both states could have the same grundy number. There are 10 zeros, 6 ones, 5 twos, and 4 threes so the answer is $25^2-10^2-6^2-5^2-4^2=448$