Trying to bite the bullet and finally understand this theorem for my own good, as it comes up a lot in number theory games.

I understand that in an impartial game, the xor operator is a convenient way to assess win and loss states because of these two facts:

  1. Every move from a losing position is a winning position (analogously: Any bit changed in a position where the xor-chain is equal to $0$, the entire expression must become non-zero)

  2. From a winning position, there exists at least one move that is a losing position (analogously: If we're looking at a xor-chain that is not equal to $0$, it can be shown that one of the values can have its bits modified to make the entire chain xor to $0$).

So this makes sense to use xor operator to assess the win/loss status of a $k$-pile game.

But what I don't quite understand is how the mex() function works when assessing the nim-value of a single game.

The Sprague-Grundy value of a single game is equal to the minimal excluded value (the "mex" function) of the set of Sprague-Grundy values of all the positions you can reach.

So $G(a_k) = \text{mex}(\{G(b_1) , G(b_2) , ... , G(b_m)\})$. where the $b$'s are other positions reachable from $a$.

Why is this the case? What is the reasoning behind why we use the mex() function here? I understand the utility in looking at all the Nim-values that are reachable from any given position, but I don't understand why we use mex() as opposed to, say, min() or max() or some other special function. What is it about mex() that gives the right answer here?


The key feature to the Nim value is that it is necessarily the number of sticks to add to the game as a separate Nim structure to make it a second-player win. To my knowledge, that's the definition of the Nim value of a game. So this is the property we have to look at.

Then given a position, let us imagine that there is a pile of Nim sticks to the side. The Mex allows a win by the second player by induction: if the first player takes from the Nim sticks, then the second player has a move to a position of Nim value equal to the number of sticks left, by the definition of Mex. If the first player moves in the actual game, though, the second player either can remove Nim sticks if the first player decreased the Nim value, or can play back down to the same Nim value in the original game, by induction and again by the definition of Mex.

So basically, the reason is that the second player always needs to be able to get back down to a losing position for the first player, and the Mex function is exactly the function that allows that.


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.