1
$\begingroup$

I have an assignment to construct a game of Nim (a game in which two players must divide a pile of tokens into two unequal sizes; 6 can be divided into 2 & 4 but not 3 & 3). I was provided a game tree (the same one I find on Google), but I am confused. Shouldn't the first turn of the second player have access to S6, S5, and S4 and S3 since 7 can be divided into 4 & 3?

NIM game tree

$\endgroup$
2
$\begingroup$

No, the game tree is not correct for the description you gave.

If you look a few levels downward, there's the position F(2), which by your description should be a dead end: you can't make a move, since splitting a pile of 2 into non-equal parts is not possible. Yet, the tree gives two options. Your observation that you should be able to move from 7 to 5, 6, or 3+4 is also correct.

I think Hendrik Jan is right, and this tree describes the game where you either take one or two tokens from a pile, and the player who takes the last token wins.

$\endgroup$
2
$\begingroup$

There are many kinds of NIM. The one in the picture is a rather classic example. Take either one or two tokens, the one who takes the last token looses.

Does not sound like the version you suggest. Your game does not state what happens with the divided heaps?

$\endgroup$
2
$\begingroup$

The game that you outline, while it can be handled by the same Sprague-Grundy Theory that is used for Nim (and therefore can have a nim-value assigned to every position), is better known as Grundy's Game; note that there's no legal move on a heap of size 1 (since it can't be divided into two heaps) and no legal move on a heap of size 2 (since it can't be divided into two unequal heaps). As perhaps a bit more of a curiosity, while it was once conjectured that the game was periodic, its value has now been calculated for more than 30 billion starting heap sizes without any periodicity having been found.

$\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.