# The reasoning behind the mex() function

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?

• – Ethan Bolker Dec 25 '16 at 23:27