I have read only one proof online that shows that the Sprague-Grundy value of a position in an impartial game, denoted by say $g(x,y)$, is equal to $g_1(x) \otimes g_2(y)$, where $\otimes$ denotes Nim-multiplication (https://www.stat.berkeley.edu/~mlugo/stat155-f11/tartan.pdf). However, I was wondering if it can be proven as follows:

Let $b = g_1(x) \otimes g_2(y)$.

If it can be proven that (1) for all integers $a < b$, $a$ is a follower of the larger game $G$ and (2) no follower/move of $G$ has an SG-value equal to $b$. This shows that the Minimum-Excludant of $G$ is $b$.

Does anyone know if this proof is available or how to approach it?


Your Answer

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

Browse other questions tagged or ask your own question.