Consider a $1$ by $n$ tiled rectangle. You want to play a game with one opponent in which you place $1$ by $2$ "dominoes" on this rectangle. The player who places the last domino wins.
Which player can guarantee a win in the game and when (the one who goes first or the one who goes second)?
So far, I have determined that for $n$ is even, the player who goes first can guarantee a victory by implementing a mirror strategy. However, the player who goes first will not always win when $n$ is odd. Any ideas?
Best Answer
The Sprague-Grundy theory should kill this problem pretty dead; it solves any game of a large class that includes this game. Without getting into the theoretical details of the theory:
Let's say that $r_n$ represents a row of $n$ empty squares. Every position in your game is a disjoint sum of these. For example, after the first player moves in $r_6$, they leave either $r_4$ or $ r_1 + r_3, $ or $r_2 + r_2$. (Also $r_3+ r_1$, but the $+$ and $\oplus$ operations are commutative, so this is the same as $r_1+r_3$.)
The values for these rows are as follows:
$$\begin{array}{rrr} r_0 & & 0 \\ r_1 & & 0 \\ r_2 & mex(val(r_0) = 0) =& 1 \\ r_3 & mex(val(r_1) = 0) =& 1 \\ r_4 & mex(val(r_2) = 1, val(r_1)\oplus val(r_1) = 0) =& 2 \\ r_5 & mex(val(r_3) = 1, val(r_1)\oplus val(r_2) = 1) =& 0 \\ r_6 & mex(val(r_4) = 2, val(r_1)\oplus val(r_3) = 1, val(r_2)\oplus val(r_2) = 0) =& 3 \\ r_7 & mex(val(r_5) = 0, val(r_1)\oplus val(r_4) = 2, val(r_2)\oplus val(r_3) = 0) =& 1 \\ r_8 & mex(3, 0\oplus0=0, 2\oplus1 = 3, 1\oplus1=0) =& 1 \\ r_9 & mex(1, 3\oplus0=3, 0\oplus1 = 1, 2\oplus1=3) =& 0 \\ \vdots & & \vdots \end{array}$$
Let's look at $r_5$ for example. The next player to play can play at either end, leaving $r_3$, or in the middle, leaving a disjoint sum of $r_1$ and $r_2$. From an earlier calculation that $val(r_2) = 1$ and $val(r_1) = 0$. The value of the sum of $r_2 + r_1$ is $1\oplus 0 = 1$, and the value of $r_3$ is (from an earlier calculation) 1. So the value of $r_5$ is the mex of 1 and 1, which is the smallest nonnegative number not in the set $\{1, 1\}$, and this is 0.
This means that $r_5$ should be a win for the player who moved to it, and a loss for the next player to move. As indeed it is: whatever move the next player to move makes, their opponent wins trivially.
From $r_6$, on the other hand, one can move to $r_4$, to $r_3 + r_1$, or to $r_2 + r_2$. These have values $2$, $1\oplus 0$, and $1\oplus 1$, respectively. $1\oplus1 = 0$, so we need to find $mex(2, 1, 0)$ which is 3. This is not equal to zero, so the next player has a win, which they produce by moving to a position with value 0, in this case $r_2 + r_2$, which they can win by a symmetry argument.
$r_9$ should be a win for the player who moves to it; let's call her $P$ for "previous". Suppose the next player, $N$, moves to $r_3 + r_4$. $P$'s job now is to move to a zero position. $r_3$ has value 1 and $r_4$ has value 2. It must be possible to move from $r_4$ to a position with value 1, leaving $1\oplus 1 = 0$. So the correct move here is from $r_3 + r_4$ to $r_3 + r_2$. Now whichever component $P$ moves in leaves one remaining move in the other component for $N$, who wins, as predicted.
It may not be clear how to calculate the value for $r_n$ directly, but to calculate all the $r_i$ for $i\le n$ is straightforward if tedious. A computer calculation reveals that the 0 positions of length less than 100, which are the ones you want to move to if you want to win, are rows of 0, 1, 5, 9, 15, 21, 25, 29, 35, 39, 43, 55, 59, 63, 73, 77, 89, 93, 97, and 99 squares. Except for 0, these are all odd, as you observed they must be.
The winning strategy is always “Move to a position with value 0.” Because of the definition of $mex$, there is such a move if and only if the current position has a nonzero value.
(More detailed explanation of how this works, with extended example.)