Game involving tiling a 1 by n board with 1 x 2 tiles?

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?

Solutions Collecting From Web of "Game involving tiling a 1 by n board with 1 x 2 tiles?"

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:

  1. You can tabulate the “value” of each position, where the “value” is a non-negative integer
  2. A position with no legal moves has value 0.
  3. A position with legal moves to one or more positions has the value $$mex(val(p_1), val(p_2), \ldots)$$ where $val(p_1)\ldots$ are the values of the positions to which one can legally move, and $mex(S)$ is the smallest non-negative integer not in $S$.
  4. If a position $p$ is actually a disjoint sum of two subpositions, $p = p_1 + p_2$, where a move in one subposition can’t affect the play in the other subposition, then $val(p) = val(p_1) \oplus val(p_2)$, where $\oplus$ is the “bitwise exclusive or” operation, also sometimes described as “add in base 2, but without carrying”.
  5. A position is a win for the player who moves to it if, and only if, its value is 0. If its value is positive, it is a win for the next player to move from it.

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:

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

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.)

In the context of what’s known about impartial games like this, vadim123 and DanTilkin made the key observation: This game is a counter-removing game where you can remove two counters and leave 0, 1, or 2 piles as remainder. Basic counter-removing games are called octal games and are denoted by a code. The code for this game happens to be “.07”, but this game actually has a name: it’s “Dawson’s Kayles”, which is related to a more famous game called Dawson’s Chess. You can play your game at cut-the-knot, as well as a version of Dawson’s Chess.

If you’re unfamiliar with Sprague-Grudy, the strategy for Nim, and/or Octal Periodicity, check out this community wiki collection of tutorials about them, because they’re necessary for getting the full answer.

Since octal games leave disjoint piles (sometimes envisioned as strips of paper boxes), and the Sprague Grundy theory tells us that bitwise xor is all we need to combine disjoint piles, all you need to know to play an octal game perfectly is the sequence of [Grundy] values for a single “pile” (1xn board). MJD outlined the beginnings of this computation in their answer.

However, many octal games, including Dawson’s Kayles are special in that the sequence of values is eventually periodic. (In fact, we can’t prove that’s not the case for all octal games.) There’s a nice theorem called Guy-Smith periodicity that says “if the sequence for an octal game looks periodic for a little while, then it will stay periodic”. (A proof can be found in this paper by Siegel.)

In particular, it turns out that the values Dawson’s Kayles are eventually periodic. Dawson’s Chess (code .137) is a “first cousin” of Dawson’s Kayles, which means that their sequences of values are the same, except for a shift: Dawson’s Kayles has an extra 0 at the beginning. Here is the sequence for Dawson’s Chess which “has period 34 with the only exceptions at n=0, 14, 16, 17, 31, 34 and 51.” The table is easier to read in Figure 2 of this paper by Plambeck. In short, this periodicity lets you have an efficient strategy for any game of Dawson’s Kayles, without doing much computation. In particular, the losing rows are the ones with length 0, 1, 15, 35, and all numbers congruent to 5, 9, 21, 25, or 29 modulo 34 (and all other boards have a strategy for the first player: make moves where the bitwise xor of the remaining boards’ values is zero).

If you play on a bigger board (not even necessarily a rectangle), but players on only play pieces horizontally, then each contiguous row is independent and you can use bitwise xor to calculate the value of the whole game.

As an aside, if you play on a bigger board, and players can place the domino horizontally or vertically, then this game has the name “[normal play] Cram” and not too much is known, even for rectangular boards when the board has width bigger than 3.