Grundy number

• Grundy number of losing states is 0

• The Grundy number of a state is the smallest non-negative integer other than the Grundy number of states from which it is possible to transition

  • mex: minimum excluded value

• The number of stones in a pile in Nim matches the Grundy number

• Why is it OK to XOR?

  • Let gi be the Grundy number for each mountain
  • Let g be the one joined by xor
  • $g={⨁}_i{g}_i$
  • Since we can prove that this g satisfies the Grundy number condition
  • half finished proof
    • Let m be the most significant bit of g. There are always an odd number of gi with m. Let g1 be one of them.
    • $g_1\&m=m$
    • $g_1\oplus g<g_1$, so transition is possible
    • $\left({⨁}_i{g}_i[i\ne 1]\right)\oplus (g_1\oplus g)=\left(g_1\oplus {⨁}_i{g}_i[i\ne 1]\right)\oplus g=\left({⨁}_i{g}_i\right)\oplus g=g\oplus g=0$
    • see Theory of Grundy numbers (Nim numbers, Nimber)

---

This page is auto-translated from /nishio/Grundy数 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.