What is the winning strategy in this pebble game?

The positions which are a win for the second player are those with:

  • an even number of pebbles in odd-numbered squares, and

  • an even number of pebbles in even-numbered squares.

Indeed, from a position in this set $P$, any move will be to a position not in that set, whereas from a position not in that set one can always make a move to a position in that set (if only the number of pebbles in the odd-numbered squares is odd, you can remove one, similarly for the even-numbered, and if both are odd, choose any pebble — that is not at the very leftmost square — and either more it to the left if that square is unoccupied or remove it along with the one to the left if it is).

So, systematically moving to a position in $P$ (as described in the parenthesis in the previous paragraph) provides a winning strategy provided one starts with a position not in $P$.


We can go further and find the nim-value of any position of this game.

Theorem. The nim-value of a position in this game is the Nim-sum of the contributions of its pebbles, where

  • Pebbles in odd-numbered squares contribute $1$.
  • Pebbles in even-numbered squares contribute $2$.

(Here we count the leftmost square as the $1^{st}$ square.)

Corollary. As in Gro-Tsen's answer, the winning positions (with nim-value $0$) are the ones with both an even number of pebbles in odd-numbered squares and an even number of pebbles in even-numbered squares.

Corollary. All positions have nim-value $0, 1, 2,$ or $3$.

The proof relies on the following idea, which is encoded in the lemma below.

Key Insight. A position in this pebble game is equivalent to the sum of an individual game for each pebble with its own private track.

Lemma. Given a position $P$ of pebbles $p_1, p_2, ... p_n$, consider the games $P_i$ which each consist of only the single pebble $p_i$ in the same square. Then $P$ is equivalent to $\sum_i P_i$.

Proof. To check this, we need only show that the game $P + \sum_i P_i$ is a zero game, by demonstrating a winning strategy for the second player. So consider the possible moves for the first player in the game $P + \sum_i P_i$:

  • If the first player removes two adjacent pebbles $p_i$ and $p_{i+1}$ in $P$, the second player can respond by moving the pebble in $P_{i+1}$ to the left, leaving behind two copies of $P_i$, which nim-cancel.

  • If the first player removes any one pebble, the second player responds by removing the corresponding pebble.

  • If the first player moves a pebble to the left in $P$, the second player responds by moving the pebble to the left in $P_i$.

  • If the first player moves a pebble to the left in a $P_i$, the second player responds by moving the corresponding pebble to the left in $P$. If that move is blocked by a pebble directly to the left, that's fine -- the second player instead removes those two pebbles, noting that there are now two copies of $P_{i-1}$ that nim-cancel out.

Proof of Theorem. Because of the Lemma, we need only consider the case of a single pebble in position $i$ (where position $1$ is the leftmost square). By induction on $i$,

  • There is always the option to remove the pebble, an option with nim-value $0$.
  • If $i$ is odd, there may also be the option to move the pebble to the left, which is an even-numbered square with nim-value $2$. Thus the nim-value in the odd case is $mex(0,2) = 1$.
  • If $i$ is even, there is always also the option to move the pebble to the left, which is an odd-numbered square with nim-value $1$. Thus the nim-value in the even case is $mex(0,1) = 2$.

How to Evaluate Positions.

Example 1. The nim-value of the position in the question

 . . O . . . O O . O . . . O O . . . . . O

is found quickly by seeing that a pebble in an odd-numbered position contributes nim-value 1, and a pebble in an even-numbered position contributes nim-value 2. So using this mask:

 . . O . . . O O . O . . . O O . . . . . O
 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

yields the Nim-sum

     1      +1+2  +2      +2+1          +1

which equals 2, so removing any of the even-numbered pebbles (the "2s") is a win.

Example 2. You are playing the sum of the following two positions:

 O . O . . . O O . O    +    O . O O

Evaluate each one with the mask:

 O . O . . . O O . O    +    O . O O
 1 2 1 2 1 2 1 2 1 2         1 2 1 2 
 1  +1      +1+2  +2    +    1  +1+2

This has a Nim-sum of 3, so moving any pebble to the left or removing any two adjacent pebbles (in either component!) is a win.

Tags:

Combinatorial Game Theory

Related

Examples of complicated parametric Jordan curves Maximal subgroups of odd index in $\mathrm{PSL}(3,q)$ Is this subset of matrices contractible inside the space of non-conformal matrices? Evaluation of the quality of research articles submitted in mathematical journals: how do they do that? Unexpected behavior involving √2 and parity Geometry of Level sets of elliptic polynomials in two real variables Does every $SL_2\mathbb{C}$ representation of a closed oriented surface extend over a compact oriented three-manifold? Which lattices are quotients of finite powerset lattices? Smallest $S\subset \mathbb C$ on which no degree $k$ polynomial always vanishes? Brown representability in slice category Are $\pm f\sqrt{1+g^2}$ and $\pm fg\sqrt{1+g^2}$ smooth if $f,fg,fg^2$ are smooth? Is this a new strange attractor?

Recent Posts