1
$\begingroup$

I was reading the Wikipedia article on the Sprague-Grundy theorem, and I can't get through their example for combining games.

The example combines two sets of three heaps. The first set has 1, 2 and 2 elements in its heaps, and is described by starting position $\color{blue}S$, and the second set has 1, 1 and 1 elements in its heaps, and is described by starting position $\color{red}{S'}$:

$$ \color{blue}{S = \left\{ \left\{ *1, \left\{ *1 \right\}, *2 \right\}, \left\{ *2, \left\{ *1, \left\{ *1 \right\}, *2 \right\} \right\}, \left\{ \left\{ *1 \right\}, \left\{ \left\{ *1 \right\} \right\}, \left\{ *1, \left\{ *1 \right\}, *2 \right\} \right\} \right\}} $$

$$ \color{red}{S' = \left\{ \left\{ *1 \right\} \right\}} $$

Then the combined game's starting position is said to be:

$$ \color{blue}S + \color{red}{S'} = \left\{ \left\{ \color{blue}S, \color{red}{\left\{ *1 \right\}} \right\} \right\} \cup \left\{ \left\{ \color{red}{S'}, \color{blue}{\left\{ *1, \left\{ *1 \right\}, *2 \right\}} \right\}, \left\{ \color{red}{S'}, \color{blue}{\left\{ *2, \left\{ *1, \left\{ *1 \right\}, *2 \right\} \right\}} \right\}, \left\{ \color{red}{S'}, \color{blue}{\left\{ \left\{ *1 \right\}, \left\{ \left\{ *1 \right\} \right\}, \left\{ *1, \left\{ *1 \right\}, *2 \right\} \right\}} \right\} \right\} $$

I can't make sense of the elements of $\color{blue}{S} + \color{red}{S'}$. For example, if I expressed it as the numbers of objects in every heap, what position/positions does $\left\{ \color{blue}S, \color{red}{\left\{ *1 \right\}} \right\} \in \color{blue}{S} + \color{red}{S'}$ represent? Does this addition of sets represent positions that I could express like this at all? It doesn't seem right to me that, if $\color{blue}{S} + \color{red}{S'}$ is the starting position, I could pick $\left\{ \color{blue}S, \color{red}{\left\{ *1 \right\}} \right\}$ as my next position, then $\color{red}{\left\{ *1 \right\}}$, then $\color{red}{*1}$ and finally end the 6-heap game in four moves, that should be impossible.

$\endgroup$
  • $\begingroup$ What are the legal moves in this game? $\endgroup$ – saulspatz May 5 at 22:55
  • 1
    $\begingroup$ It's just two nim games of 3 piles each combined (i.e. a nim game of 6 piles). I was following the WIkipedia article which defines each position in the game as the set of possible next positions (e.g. no possible moves is the set {}. a position with a single move that leaves no possible next move is {{}}).f $\endgroup$ – tlongeri May 5 at 23:49
  • $\begingroup$ I'm not a computer right now to type up a correction / full answer, but the basic idea is that Wikipedia's example is wrong since a lot of those commas should be plus signs. $\endgroup$ – Mark S. May 6 at 22:04
  • $\begingroup$ That explains a lot! Having that I can start to see things make sense. If you'd like to go ahead and type up the answer, I would definitely accept it. $\endgroup$ – tlongeri May 7 at 4:14
1
$\begingroup$

Since Mark S. seems like he won't post an answer himself, I'll answer my own question with his correction.

The example is incorrect.

Something that is correctly stated in the article is the definition of the operation $+$ used for combining games. We'll say $S$ represents game one and $S'$ represents game two. This operation is recursively defined as:

$$ S + S' = \left\{ S + s' \mid s' \in S' \right\} \cup \left\{ s + S' \mid s \in S \right\}$$

Each element of $S + s'$ of $\left\{ S + s' \mid s' \in S' \right\}$ represents having picked $s'$ as the next position in game two, and thus combines this new position of game two with an untouched game one. Therefore, $\left\{ S + s' \mid s' \in S' \right\}$ will be the set of positions that can be reached by making a move in game two. The case for $\left\{ S' + s \mid s \in S \right\}$ is analogous.

The recursive expansion reaches its end with $\left\{\right\} + \left\{\right\} = \left\{\right\}$.

Thus, the correct expression for $\color{blue}S + \color{red}{S'}$ is:

$$\color{blue}S + \color{red}{S'} = \left\{ \color{blue}S + \color{red}{\left\{ *1 \right\}} \right\} \cup \left\{ \color{red}{S'} + \color{blue}{\left\{ *1, \left\{ *1 \right\}, *2 \right\}}, \color{red}{S'} + \color{blue}{\left\{ *2, \left\{ *1, \left\{ *1 \right\}, *2 \right\} \right\}}, \color{red}{S'} + \color{blue}{\left\{ \left\{ *1 \right\}, \left\{ \left\{ *1 \right\} \right\}, \left\{ *1, \left\{ *1 \right\}, *2 \right\} \right\}} \right\} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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