Intereting Posts

Lebesgue measurable subset of $\mathbb{R}$ with given metric density at zero
Is it possible for an irreducible polynomial with rational coefficients to have three zeros in an arithmetic progression?
How prove this $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1 $
Homological categories in functional analysis
Jacobian of exponential mapping in SO3/SE3
The Schur Theorem
Is kernel a complemented subspace
Identify $P(2014)$ if $P(i)=1/i$ for every positive integer $1\le i\le2013$
Characterization of smallest $\sigma$-Algebra on $\Omega=[0,1)$ that contains disjoint intervals of the form $[a,b)$ where $0<a<b<1$
${\rm rank}(BA)={\rm rank}(B)$ if $A \in \mathbb{R}^{n \times n}$ is invertible?
Image of the Riemann-sphere
Can a regular heptagon be constructed using a compass, straightedge, and angle trisector?
Finding a correspondence between $\{0,1\}^A$ and $\mathcal P(A)$
Prove an interpolation inequality
Can we distinguish $\aleph_0$ from $\aleph_1$ in Nature?

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?

- The application of Nimbers to Nim strategy
- Exceptional values in a combinatorial game
- Who has a winning strategy in “knight” and why?
- Name for a certain “product game”
- In the card game “Projective Set”: Compute the probability that $n$ cards contain a set
- board game: 10 by 10 light bulbs, minimum switches to get all off?

- Help: rules of a game whose details I don't remember!
- Very fascinating probability game about maximising greed?
- What is the sprague-grundy value of these games?
- Why can a Nim sum be written as powers of 2?
- Game: two pots with coins
- Good non-mathematician book on Game Theory
- Converting a Gomoku winning strategy from a small board to a winning strategy on a larger board
- The Last Man Standing
- A non-losing strategy for tic-tac-toe $\times$ tic-tac-toe
- Nimbers for misère games

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:

- You can tabulate the “value” of each position, where the “value” is a non-negative integer
- A position with no legal moves has value 0.
- 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$. - 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”.
- 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.)

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.

- Simply Connected Domain of the plane and the Jordan Curve Theorem
- $Z(I:J)$ is the Zariski closure of $Z(I)-Z(J)$
- Number of ways to write $n$ as sum of odd or even number of Fibonacci numbers
- Under what condition can converge in $L^1$ imply converge a.e.?
- Binomial Expansion, Taylor Series, and Power Series Connection
- Kindle as a Tool for Mathematicians?
- Why is the Artin-Rees lemma used here?
- Formula for computing integrals
- proving equalities in stochastic calculus
- Two paradoxes: $\pi = 2$ and $\sqrt 2 = 2$
- If $\lim_{n\to\infty}a_{n}=l$, Then prove that $\lim_{n\to\infty}\frac{a_{1}+a_2+\cdot..+a_n}{n}=l$
- Ruin-time in Gambler's Ruins
- Discrete to Continuous Representations of Functions via Laplace Transforms?
- What is the asymptotic behavior of a linear recurrence relation (equiv: rational g.f.)?
- Help with basic Ordinal arithmetic: what is $(\omega+2)\cdot \omega$