<ul>
<li>Grundy number of losing states is 0
</li>
<li>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
<ul>
<li>mex: minimum excluded value</li>
</ul>
</li>
<li>The number of stones in a pile in <a href="/en/Nim">Nim</a> matches the Grundy number
</li>
<li>Why is it OK to XOR?
<ul>
<li>Let gi be the Grundy number for each mountain</li>
<li>Let g be the one joined by xor</li>
<li>$g = \bigoplus_i g_i$</li>
<li>Since we can prove that this g satisfies the Grundy number condition</li>
<li>half finished proof<ul>
<li>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.</li>
<li>$g_1 &amp; m = m$</li>
<li>$g_1 \oplus g &lt; g_1$, so transition is possible</li>
<li>$\left( \bigoplus_i g_i [i \neq 1] \right) \oplus (g_1 \oplus g) = \left(g_1 \oplus \bigoplus_i g_i [i \neq 1] \right) \oplus g = \left( \bigoplus_i g_i \right) \oplus g = g \oplus g = 0$</li>
<li>see <a href="https://www.creativ.xyz/grundy-number-1065/">Theory of Grundy numbers (Nim numbers, Nimber)</a></li>
</ul>
</li>
</ul>
</li>
</ul>
<hr>
This page is auto-translated from <a href="https://scrapbox.io/nishio/Grundy%E6%95%B0">/nishio/Grundy数</a> 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 <a href="https://twitter.com/nishio_en">@nishio_en</a>. I&#39;m very happy to spread my thought to non-Japanese readers.