Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
If this is a NIM game, it's not about who goes first or second. It's about whether you start with a $N$ or $P$ position. You have shown that for $n$ even that if you are handed that you have a $P$ position and will win. However, if you are handed an $N$ position, ie $n$ odd, then there is no winning strategy for you since you have to hand the other player a $P$ position and they have a winning strategy. –  mathematics2x2life Dec 22 '13 at 0:45
    
For some $n$ not even, the first to move can still win. That is why I want to determine a generalization of when each player will win. –  okarin Dec 22 '13 at 0:46
    
First, we would say for $n$ odd, not '$n$ not even'. If this is true, then this is not a NIM game. For any NIM game, given a position and a first player, assuming perfect play from both players, then that first player either has a strategy so that they will win regardless of the other players moves or no possible strategy to win and hence will lose. –  mathematics2x2life Dec 22 '13 at 0:49
    
This game is equivalent to the following: Choose a pile, remove exactly two counters, and split the remainder into two piles (one of which can be empty). –  vadim123 Dec 22 '13 at 0:50
2  
There's a detailed treatment of games like this in Chapter 4 of Winning Ways For Your Mathematical Plays, Volume 1. <p> As @vadim123 said, this is equivalent to the game "Choose a pile, remove exactly two counters, and split the remainder into two piles", although one or both can be empty. The number of tiles in the rectangle = the number of counters in the pile. Placing a domino not on the end of a rectangle = splitting into two piles. –  DanTilkin Dec 22 '13 at 1:36

2 Answers 2

up vote 6 down vote accepted

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:

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

share|improve this answer
    
Actually, you can do better than computing things with mex for this and many similar games (see my answer). –  Mark S. Dec 22 '13 at 17:32

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.

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.