Sprague-Grundy Theorem

This week, we continue our study of Impartial Games by learning about the Sprague-Grundy Theorem.

You may first choose to read the post Winning Positions if you have not already done so.

How would you solve the following?

1) The game Turning Turtles is played with a row of nn turtles, each of which is right side up or upside down. On a turn, a player chooses a turtle that is upside down and flips it to be right side up. That player may then also choose any turtle to the left of the chosen turtle and flip it. For each position in Turning Turtles (there are 2n2^n positions when playing with nn turtles), determine the Nim Sum of that position, and for each winning position, determine a winning strategy from that position.

2) For those who want a coding challenge, consider the following game.

Start with a regular nn-gon with nn vertices. On a turn, a player may choose to remove any remaining vertex along with its two neighbours (if they have not already been removed). The last player to remove a vertex wins. For what values of nn does the first player win?

Note by Calvin Lin
6 years, 3 months ago

No vote yet
11 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

An arrangement of turtles can be compared to a Nim board with:

  • an odd number of stacks of size jj, if the jjth turtle is upside down,

  • an even number of stacks of size jj, if the jjth turtle is the right side up.

The move of flipping the upside-down turtle jj corresponds to the Nim move of removing a single stack of size jj from the odd number of such stacks, leaving an even number of such stacks.

The move of flipping the upside-down turtle jj and flipping another turtle kk, where k<jk<j, corresponds to the Nim move of removing jkj-k counters from one of the stacks of size jj. There are an odd number of such stacks, and after the move there are an even number of stacks of size jj and one more stack of size kk than there used to be, so the evenness/oddness of the number of stacks of size kk has been switched.

This is not an exact correspondence between the Turning Turtles game and Nim, for the losing position in TT of all the turtles being the right way up (so no moves are available) corresponds to a Nim game where there is an even number of stacks of all sizes, and there are plays available here. However, such a Nim game is always a losing position for the player who has to play (if the player takes xx counters from a stack of size yy, the other player does exactly the same, which is possible since there are an even number of stacks of size yy to begin with; this just puts the first player back in the position of having an even number of stacks of each size before him, and eventually all the piles will be exhausted, and the first player will have nowhere to go). Thus the losing position in TT corresponds to a more long drawn-out, but inevitable, loss in Nim. More theoretically, since the Nim sum nnn\oplus n of a number with itself is always 00, the Nim sum of a game with an even number of stacks of each size must be 00, and hence that must be a losing position. Hence the lack of an exact correspondence does not matter.

Thus we can interpret a winning Nim strategy for TT as follows. For any layout of turtles, numbered 11 to nn from left to right, let A{1,2,,n}A\subseteq \{1,2,\ldots,n\} be the set of upside-down turtles.

If A=A = \varnothing, you have lost.

Otherwise, calculate the disjoint binary sum s(A)s(A) of the elements of AA: s(A)  =  jAj s(A) \; = \; \bigoplus_{j \in A} j

If s(A)=0s(A)=0, you are in a losing position. You can choose to resign, cheat or make any play and hope for a mistake on your opponent's part.

If s(A)0s(A) \neq 0, you are in a winning position. Let dd be the index of the most significant binary digit of s(A)s(A), so that the binary expansion of s(A)s(A) is (sdsd1s1s0)2(s_ds_{d-1}\cdots s_1s_0)_2 where sd=1s_d=1. Find xAx \in A such that the ddth binary digit of xx is 11. This must be possible, since otherwise sds_d would be 00. Calculate y=s(A)xy \,=\, s(A) \oplus x. If xx and yy have binary expansions (xmxm1x1x0)2(x_mx_{m-1}\cdots x_1x_0)_2 and (ymym1y1y0)2(y_my_{m-1}\cdots y_1y_0)_2 respectively (padding them with 00s at the front to make them the same length) then:

  • sj=0s_j = 0 for all j>dj > d, and hence yj=xjy_j = x_j for all j>dj > d.

  • xd=1x_d = 1 and yd=0y_d = 0.

  • 0(xd1xd2x1x0)2,(yd1yd2y1y0)22d1 0 \le (x_{d-1}x_{d-2}\cdots x_1x_0)_2, (y_{d-1}y_{d-2}\cdots y_1y_0)_2 \le 2^d-1.

From these facts it is clear that y<xy < x.

  • If y=0y=0, you just flip the upside-down turtle xx.

  • If y>0y > 0, you flip the upside-down turtle xx and also flip turtle yy.

This strategy leaves your opponent with a set BB of upside-down turtles (the set AA with xx removed and, if necessary, yy either added or removed) such that s(B)  =  s(A)xy  =  0 s(B) \; = \; s(A) \oplus x \oplus y \; = \; 0 which is thus a losing position for your opponent.

Mark Hennings - 6 years, 3 months ago

Log in to reply

Here is my take on the second problem...

After the first move, which must remove three adjacent vertices, the state of the game is a number of runs of adjacent vertices, with gaps between them corresponding to the vertices that have already been removed. We can regard this state as a Nim board where run of adjacent vertices corresponds to a stack, and the height of the stack is the number of adjacent vertices in the run. We can, as usual, describe a Nim board by a sequence of integers s=(n1,n2,,nk)s = (n_1,n_2,\ldots,n_k), representing kk stacks of heights n1,n2,,nkn_1,n_2, \ldots,n_k.

After the first move of the game, the second player is faced with the Nim board (n3)(n-3).

At each move, it is possible to:

  • remove one counter from a stack, leaving no stack behind (when the stack just has height one, so that the run of adjacent vertices consists of just one vertex),

  • remove two counters from a stack, leaving either no stack behind (when the stack has height two, so that the run of adjacent vertices consists of two neighbouring vertices) or one stack behind (when the stack has height three or more, so that the run of adjacent vertices consists of three or more adjacent vertices, and the vertex chosen to be removed, along with its neighbours, is one of the end ones),

  • remove three counters from a stack, leaving either no stack behind (when the stack has height three, so that the run of adjacent vertices consists of three adjacent vertices, and the vertex chosen to be removed along with its neighbours is the middle one) or one stack behind (when the stack has height four or more, so we have four or more adjacent vertices and the vertex chosen to be removed along with its neighbours is one of the two vertices "one in" from the end) or two stacks behind (when the stack has height five or more, so we have five or more adjacent vertices and the vertex chosen to be removed along with its neighbours is neither one of the end vertices nor one of the "one in" vertices).

In the language of octal games, this is the game 0.1370.137, or Dawson's Chess.

The Nim number for a Nim board in the state s=(n1,n2,,nk)s = (n_1,n_2,\ldots,n_k) is the disjoint binary sum G(s)  =  g(n1)g(n2)g(nk) G(s) \; = \; g(n_1) \oplus g(n_2) \oplus \cdots \oplus g(n_k) where gg is the Grundy function for this game, where g(n)g(n) is defined recursively as the mex (the smallest nonnegative integer not in the list) of the Nim numbers of the Nim boards after one move has been applied to the Nim board with just one stack of height nn. Thus g(n)  =  {0n=0mex{g(0)}  =  1n=1mex{g(0)}  =  1n=2mex{g(0),g(1)}  =  2n=3mex{g(1),g(2)}  =  0n=4mex{g(n2),g(n3),g(1)g(n4),g(2)g(n5),,g(n5)g(2),g(n4)g(1)}n5 g(n) \; = \; \left\{ \begin{array}{ll} 0 & n=0 \\ \mathrm{mex}\{g(0)\}\; = \; 1 & n=1 \\ \mathrm{mex}\{g(0)\}\; = \; 1 & n=2 \\ \mathrm{mex}\{g(0),g(1)\} \; = \; 2 & n=3 \\ \mathrm{mex}\{g(1),g(2)\} \; = \; 0 & n=4 \\ \mathrm{mex}\left\{\begin{array}{l}g(n-2),g(n-3),g(1)\oplus g(n-4),\\ g(2)\oplus g(n-5),\ldots,g(n-5)\oplus g(2),g(n-4)\oplus g(1)\end{array}\right\} & n \ge 5 \end{array} \right. Standard theory tells us that one move applied to a Nim board with state ss with G(s)=0G(s)=0 leads to a Nim board with state tt such that G(t)0G(t) \neq 0 and also that for any Nim board with state ss such that G(s)0G(s) \neq 0 it is possible to find a single move with puts the Nim board into a state tt with G(t)=0G(t) = 0. Thus states with Nim score 00 are losing states if you have to play next. Thus we deduce that the first player will win the game provided that the Nim number of the Nim board with one stack containing n3n-3 counters is 00. Thus the first player will win precisely when n3n \ge 3 is such that g(n3)=0g(n-3)=0.

The Grundy function gg for Dawson's Chess is completely known, and is eventually periodic of 3434. Basically, these are the values that g(n)g(n) takes as n0,1,2,3,4,,33n\,\equiv\, 0,1,2,3,4,\ldots,33 modulo 3434: 8  1  1  2  0  3  1  1  0  3  3  2  2  4  4  5  5  9  3  3  0  1  1  3  0  2  1  1  0  4  5  3  7  4 8\;1\;1\;2\;0\;3\;1\;1\;0\;3\;3\;2\;2\;4\;4\;5\;5\;9\;3\;3\;0\;1\;1\;3\;0\;2\;1\;1\;0\;4\;5\;3\;7\;4 with the sole exceptions that g(0)=g(14)=g(34)=0g(0) = g(14) = g(34) = 0 and g(16)=g(17)=g(51)=2g(16) = g(17) = g(51) = 2.

Thus the first player wins when n3=0,14,34n-3 = 0,14,34 or else n34,8,20,24,28n-3 \,\equiv\, 4,8,20,24,28 modulo 3434. In other words, the first player wins when n=3,17,37n=3,17,37 or else n7,11,23,27,31n \,\equiv\, 7,11,23,27,31 modulo 3434.

Mark Hennings - 6 years, 3 months ago

Log in to reply

It would help to define what defines the winning position --- a player loses if there are no upside-down turtles available

Mark Hennings - 6 years, 3 months ago

Log in to reply

As stated in Winning positions,

4) The first player who is unable to make a move loses the game.

Calvin Lin Staff - 6 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...