Problem 82. Game of Pebbles

-

We have a \(1 \times 20\) grid. Two players play the pebble game on this grid in alternative turns. Each time, a player places a pebble on one of the empty cells, provided that the cell itself and its adjacent cells (if exist) are also empty. The person who places the last pebble wins the game.

If both players play optimally, who will win?

-

The second player can win the game if he plays optimally.
The solution is based on the nim-value or the minimum excluded (mex) value of the game. We give a brief description of this method in the following: Consider a two-player combinatorial game in which players play alternatively and the winner is the player who makes the last move. Also, assume that the game is symmetric meaning that both players have the same set of moves for each state of the game. In this setting the Sprague–Grundy theorem states the following rules to find out the winner of the game for every state:

  • The mex value of a state in which no move is valid is equal to 0.

  • Otherwise, the mex value of a state \(s\) of the game is equal to the smallest value \(v \geq 0\) such that no move can change the state of the game from \(s\) to a state \(s'\) whose mex value is equal to \(v\).

  • If a state \(s\) of the game can be divided into several independent states, \(s_1, s_2, \ldots, s_k\) then the mex value of state \(s\) is the exclusive or (xor) of the mex values of \(s_1\) through \(s_k\).

  • The first player can win a state \(s\) if and only if the mex value of \(s\) is nonzero.

Now, we go back to the pebble game. We refer to a state of the game that only contains a grid of size \(1 \times n\) by \(G(n)\). Notice that after putting a pebble on cell \(3 \leq i \leq n-2\), the state of the game can be thought of as two independent states \(G(i-2), G(n-i-1)\) whose mex value is equal to the XOR of the mex values of the two states. Moreover, for \(i \in \{1,n\}\) putting a pebble on cell \(i\) would change the state of the game into \(G(n-2)\). Finally, for \(i \in \{2,n-1\}\) putting a pebble on cell \(i\) will change the state of the game into \(G(n-3)\). Thus, we can iteratively compute the mex values of the states of the game as follows:

  • \(G(0) = 0\) as there is no valid move for a grid of size \(0\).

  • The only state reachable directly from \(G(1)\) is \(G(0) \rightarrow\) mex=0 so the mex value of \(G(1)\) is 1.

  • The only state reachable directly from \(G(2)\) is \(G(0) \rightarrow\) mex=0 so the mex value of \(G(2)\) is 1.

  • States reachable directly from \(G(3)\) are \(G(0) \rightarrow\) mex=0, \(G(1) \rightarrow\) mex=1 so the mex value of \(G(3)\) is 2.

  • States reachable directly from \(G(4)\) are \(G(1) \rightarrow\) mex=1, \(G(2) \rightarrow\) mex=1 so the mex value of \(G(4)\) is 0.

  • States reachable directly from \(G(5)\) are \(\langle G(1), G(1) \rangle \rightarrow\) mex=(1 xor 1)=0, \(G(2) \rightarrow\) mex=1, \(G(3) \rightarrow\) mex=2 so the mex value of \(G(5)\) is 3.

  • States reachable directly from \(G(6)\) are \(\langle G(1), G(2) \rangle \rightarrow\) mex=(1 xor 1)=0, \(G(3) \rightarrow\) mex=2, \(G(4) \rightarrow\) mex=0 so the mex value of \(G(6)\) is 1.

  • States reachable directly from \(G(7)\) are \(\langle G(1), G(3) \rangle \rightarrow\) mex=(1 xor 2)=3, \(G(4) \rightarrow\) mex=0, \(G(5) \rightarrow\) mex=3, \(\langle G(2), G(2) \rangle \rightarrow\) mex=(1 xor 1)=0 so the mex value of \(G(7)\) is 1.

  • States reachable directly from \(G(8)\) are \(\langle G(2), G(3) \rangle \rightarrow\) mex=(1 xor 2)=3, \(\langle G(1), G(4) \rangle \rightarrow\) mex=(1 xor 0)=1, \(G(5) \rightarrow\) mex=3, \(G(6) \rightarrow\) mex=1 so the mex value of \(G(8)\) is 0.

  • States reachable directly from \(G(9)\) are \(\langle G(2), G(4) \rangle \rightarrow\) mex=(1 xor 0)=1, \(G(6) \rightarrow\) mex=1, \(\langle G(1), G(5) \rangle \rightarrow\) mex=(1 xor 3)=2, \(G(7) \rightarrow\) mex=1, \(\langle G(3), G(3) \rangle \rightarrow\) mex=(2 xor 2)=0 so the mex value of \(G(9)\) is 3.

  • States reachable directly from \(G(10)\) are \(\langle G(3), G(4) \rangle \rightarrow\) mex=(2 xor 0)=2, \(G(7) \rightarrow\) mex=1, \(G(8) \rightarrow\) mex=0, \(\langle G(1), G(6) \rangle \rightarrow\) mex=(1 xor 1)=0, \(\langle G(2), G(5) \rangle \rightarrow\) mex=(1 xor 3)=2 so the mex value of \(G(10)\) is 3.

  • States reachable directly from \(G(11)\) are \(\langle G(4), G(4) \rangle \rightarrow\) mex=(0 xor 0)=0, \(G(8) \rightarrow\) mex=0, \(G(9) \rightarrow\) mex=3, \(\langle G(1), G(7) \rangle \rightarrow\) mex=(1 xor 1)=0, \(\langle G(2), G(6) \rangle \rightarrow\) mex=(1 xor 1)=0, \(\langle G(3), G(5) \rangle \rightarrow\) mex=(2 xor 3)=1 so the mex value of \(G(11)\) is 2.

  • States reachable directly from \(G(12)\) are \(\langle G(2), G(7) \rangle \rightarrow\) mex=(1 xor 1)=0, \(G(9) \rightarrow\) mex=3, \(G(10) \rightarrow\) mex=3, \(\langle G(1), G(8) \rangle \rightarrow\) mex=(1 xor 0)=1, \(\langle G(4), G(5) \rangle \rightarrow\) mex=(0 xor 3)=3, \(\langle G(3), G(6) \rangle \rightarrow\) mex=(2 xor 1)=3 so the mex value of \(G(12)\) is 2.

  • States reachable directly from \(G(13)\) are \(\langle G(5), G(5) \rangle \rightarrow\) mex=(3 xor 3)=0, \(\langle G(3), G(7) \rangle \rightarrow\) mex=(2 xor 1)=3, \(G(10) \rightarrow\) mex=3, \(G(11) \rightarrow\) mex=2, \(\langle G(4), G(6) \rangle \rightarrow\) mex=(0 xor 1)=1, \(\langle G(1), G(9) \rangle \rightarrow\) mex=(1 xor 3)=2, \(\langle G(2), G(8) \rangle \rightarrow\) mex=(1 xor 0)=1 so the mex value of \(G(13)\) is 4.

  • States reachable directly from \(G(14)\) are \(\langle G(3), G(8) \rangle \rightarrow\) mex=(2 xor 0)=2, \(G(11) \rightarrow\) mex=2, \(G(12) \rightarrow\) mex=2, \(\langle G(2), G(9) \rangle \rightarrow\) mex=(1 xor 3)=2, \(\langle G(5), G(6) \rangle \rightarrow\) mex=(3 xor 1)=2, \(\langle G(1), G(10) \rangle \rightarrow\) mex=(1 xor 3)=2, \(\langle G(4), G(7) \rangle \rightarrow\) mex=(0 xor 1)=1 so the mex value of \(G(14)\) is 0.

  • States reachable directly from \(G(15)\) are \(\langle G(1), G(11) \rangle \rightarrow\) mex=(1 xor 2)=3, \(\langle G(2), G(10) \rangle \rightarrow\) mex=(1 xor 3)=2, \(G(12) \rightarrow\) mex=2, \(G(13) \rightarrow\) mex=4, \(\langle G(5), G(7) \rangle \rightarrow\) mex=(3 xor 1)=2, \(\langle G(3), G(9) \rangle \rightarrow\) mex=(2 xor 3)=1, \(\langle G(4), G(8) \rangle \rightarrow\) mex=(0 xor 0)=0, \(\langle G(6), G(6) \rangle \rightarrow\) mex=(1 xor 1)=0 so the mex value of \(G(15)\) is 5.

  • States reachable directly from \(G(16)\) are \(\langle G(1), G(12) \rangle \rightarrow\) mex=(1 xor 2)=3, \(\langle G(5), G(8) \rangle \rightarrow\) mex=(3 xor 0)=3, \(\langle G(4), G(9) \rangle \rightarrow\) mex=(0 xor 3)=3, \(\langle G(3), G(10) \rangle \rightarrow\) mex=(2 xor 3)=1, \(G(13) \rightarrow\) mex=4, \(G(14) \rightarrow\) mex=0, \(\langle G(6), G(7) \rangle \rightarrow\) mex=(1 xor 1)=0, \(\langle G(2), G(11) \rangle \rightarrow\) mex=(1 xor 2)=3 so the mex value of \(G(16)\) is 2.

  • States reachable directly from \(G(17)\) are \(\langle G(4), G(10) \rangle \rightarrow\) mex=(0 xor 3)=3, \(\langle G(7), G(7) \rangle \rightarrow\) mex=(1 xor 1)=0, \(\langle G(6), G(8) \rangle \rightarrow\) mex=(1 xor 0)=1, \(G(14) \rightarrow\) mex=0, \(G(15) \rightarrow\) mex=5, \(\langle G(1), G(13) \rangle \rightarrow\) mex=(1 xor 4)=5, \(\langle G(2), G(12) \rangle \rightarrow\) mex=(1 xor 2)=3, \(\langle G(5), G(9) \rangle \rightarrow\) mex=(3 xor 3)=0, \(\langle G(3), G(11) \rangle \rightarrow\) mex=(2 xor 2)=0 so the mex value of \(G(17)\) is 2.

  • States reachable directly from \(G(18)\) are \(\langle G(1), G(14) \rangle \rightarrow\) mex=(1 xor 0)=1, \(\langle G(2), G(13) \rangle \rightarrow\) mex=(1 xor 4)=5, \(G(15) \rightarrow\) mex=5, \(G(16) \rightarrow\) mex=2, \(\langle G(5), G(10) \rangle \rightarrow\) mex=(3 xor 3)=0, \(\langle G(3), G(12) \rangle \rightarrow\) mex=(2 xor 2)=0, \(\langle G(4), G(11) \rangle \rightarrow\) mex=(0 xor 2)=2, \(\langle G(6), G(9) \rangle \rightarrow\) mex=(1 xor 3)=2, \(\langle G(7), G(8) \rangle \rightarrow\) mex=(1 xor 0)=1 so the mex value of \(G(18)\) is 3.

  • States reachable directly from \(G(19)\) are \(\langle G(2), G(14) \rangle \rightarrow\) mex=(1 xor 0)=1, \(\langle G(8), G(8) \rangle \rightarrow\) mex=(0 xor 0)=0, \(\langle G(5), G(11) \rangle \rightarrow\) mex=(3 xor 2)=1, \(\langle G(1), G(15) \rangle \rightarrow\) mex=(1 xor 5)=4, \(\langle G(4), G(12) \rangle \rightarrow\) mex=(0 xor 2)=2, \(G(16) \rightarrow\) mex=2, \(G(17) \rightarrow\) mex=2, \(\langle G(3), G(13) \rangle \rightarrow\) mex=(2 xor 4)=6, \(\langle G(7), G(9) \rangle \rightarrow\) mex=(1 xor 3)=2, \(\langle G(6), G(10) \rangle \rightarrow\) mex=(1 xor 3)=2 so the mex value of \(G(19)\) is 3.

  • States reachable directly from \(G(20)\) are \(\langle G(3), G(14) \rangle \rightarrow\) mex=(2 xor 0)=2, \(\langle G(4), G(13) \rangle \rightarrow\) mex=(0 xor 4)=4, \(\langle G(6), G(11) \rangle \rightarrow\) mex=(1 xor 2)=3, \(\langle G(7), G(10) \rangle \rightarrow\) mex=(1 xor 3)=2, \(G(17) \rightarrow\) mex=2, \(G(18) \rightarrow\) mex=3, \(\langle G(8), G(9) \rangle \rightarrow\) mex=(0 xor 3)=3, \(\langle G(1), G(16) \rangle \rightarrow\) mex=(1 xor 2)=3, \(\langle G(2), G(15) \rangle \rightarrow\) mex=(1 xor 5)=4, \(\langle G(5), G(12) \rangle \rightarrow\) mex=(3 xor 2)=1 so the mex value of \(G(20)\) is 0.

Since the mex value of \(G(20)\) is equal to 0 then the second player can win the game if he plays optimally.