Algebraic space

In combinatorial game theory, the mex, or "minimum excludant", of a set of ordinals denotes the smallest ordinal not contained in the set.

Some examples:

$\text{mex}(\{1,2,3\})=0$

$\text{mex}(\{0,1,4,7,12\})=2$

$\text{mex}(\{0,1,2,3,\dots \})=\omega$

$\text{mex}(\{0,2,4,6,\dots \})=1$

$\text{mex}(\{0,1,2,3,\dots ,\omega \})=\omega +1$

where ω is the limit ordinal for the natural numbers.

In the Sprague-Grundy theory the minimum excluded ordinal is used to determine the nimber of a normal-play impartial game, which is a game in which either player has the same moves in each position and the last player to move wins. The nimber is equal to 0 for a game that is lost immediately by the first player, and is equal to the mex of the nimbers of all possible next positions for any other game.

For example, in a one-pile version of Nim, the game starts with a pile of n stones, and the player to move may take any positive number of stones. If n is zero, the nimber is 0. If n is 1, the player to move will leave 0 stones, and the mex of { 0 }, 1, gives the nimber for this case. If n is 2, the player to move can leave 0 or 1 stones, giving 2 as the mex of { 0, 1 }. In general, the player to move with a pile of n stones can leave anywhere from 0 to n-1 stones; the mex of the numbers { 0, 1, ..., n-1 } is always n. From this we can conclude that the first player wins if n is not zero (by taking all the stones).

If we change the game so that the player to move can only take up to 3 stones, then when n=4, the successor states have nimbers { 1, 2, 3 }, giving a mex of 0. Now the first player loses; the second player's strategy is to respond to whatever move the first player makes by taking the rest of the stones. For n=5, the nimbers of the successor states 2, 3, and 4 are 2, 3, and 0 (as we just calculated); the mex of { 0, 2, 3 } is 1, so starting with 5 stones in this game is a win for the first player.

(See nimbers for more details on the meaning of nimber values.)

References

• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534