In mathematics, the mex ("minimum excluded value") of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset.
Beyond sets, subclasses of well-ordered classes have minimum excluded values.
Minimum excluded values of subclasses of the ordinal numbers are used in combinatorial game theory to assign nim-values to impartial games.
[1] Minimum excluded values are also used in graph theory, in greedy coloring algorithms.
[2] The following examples all assume that the given set is a subset of the class of ordinal numbers:
In the Sprague–Grundy theory the minimum excluded ordinal is used to determine the nimber of a normal-play impartial 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.
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 nimbers {0, 1, …, n − 1} is always the nimber n. The first player wins in Nim if and only if the nimber is not zero, so from this analysis we can conclude that the first player wins if and only if the starting number of stones in a one-pile game of Nim is not zero; the winning move is to take all the stones.