1
$\begingroup$

I want to calculate the grundy number of these 4 normal-play nim heaps: 0, 7, 7, 7 I'm confused when comparing two wikipedia pages: sprague-grundy suggests I should find the mex of these 4 numbers, which is 1. while the nim page says I should XOR them all, which generates 7.

which is it?

$\endgroup$
3
$\begingroup$

The Grundy number is the nim-sum (i.e. the xor) of the numbers of items in all the heaps—namely $\ 7\ $ in this case.

You have misunderstood what the Wikipedia page is saying. There's no shame in that, though, since it's not particularly well written. The numbers $\ n_1, n_2,\dots, n_k\ $, over which the page says to take the mex aren't numbers of items in nim heaps, but the Grundy numbers of the positions you can move to in the game $\ G'\ $. If $\ G'\ $ were your game of nim with three heaps of size seven, for instance, there are effectively seven positions you can move to—two heaps of size seven, and one heap of any size from zero to six. The Grundy numbers of these positions are $\ 0,1,2,3,4,5,6\ $, so the mex of these numbers, namely $7$, is the Grundy number of the position you're facing.

$\endgroup$
  • $\begingroup$ thanks! where did you see the "positions you can move to" bit? can you recommend a better source for learning about the grundy theorem and solving nim? $\endgroup$ – ihadanny May 11 at 16:48

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.