Мекс (математика)

В математике mex (« минимальное исключенное значение ») подмножества хорошо упорядоченного множества — это наименьшее значение из всего множества, которое не принадлежит подмножеству. То есть это минимальное значение дополнительного множества .

За пределами множеств подклассы хорошо упорядоченных классов имеют минимальные исключенные значения. Минимальные исключенные значения подклассов порядковых чисел используются в комбинаторной теории игр для назначения ним-значений беспристрастным играм . Согласно теореме Спрага–Гранди , ним-значение игровой позиции — это минимальное исключенное значение класса значений позиций, которые могут быть достигнуты за один ход из данной позиции. ^[1]

Минимальные исключенные значения также используются в теории графов , в жадных алгоритмах раскраски. Эти алгоритмы обычно выбирают порядок вершин графа и выбирают нумерацию доступных цветов вершин. Затем они рассматривают вершины по порядку, для каждой вершины выбирая свой цвет как минимальное исключенное значение набора цветов, уже назначенных ее соседям. ^[2]

Во всех следующих примерах предполагается, что заданный набор является подмножеством класса порядковых чисел :$${\displaystyle {\begin{array}{lcl}\operatorname {mex} (\emptyset )&=&0\\[2pt]\operatorname {mex} (\{1,2,3\})&=&0\\[2pt]\operatorname {mex} (\{0,2,4,6,\ldots \})&=&1\\[2pt]\operatorname {mex} (\{0,1,4,7,12\})&=&2\\[2pt]\operatorname {mex} (\{0,1,2,3,\ldots \})&=&\omega \\[2pt]\operatorname {mex} (\{0,1,2,3,\ldots ,\omega \})&=&\omega +1\end{array}}}$$

где ω — предельный порядковый номер натуральных чисел.

В теории Спрага–Гранди минимальный исключенный ординал используется для определения числа для беспристрастной игры с нормальной игрой . В такой игре любой игрок имеет одинаковые ходы в каждой позиции, и последний игрок, сделавший ход, выигрывает. Число равно 0 для игры, которая немедленно проиграна первым игроком, и равно mex чисел всех возможных следующих позиций для любой другой игры.

Например, в версии Nim с одной кучей игра начинается с кучи из n камней, и игрок, который должен сделать ход, может взять любое положительное количество камней. Если n равно нулю камней, то нимбер равен 0, поскольку mex пустого набора допустимых ходов равен нимберу 0. Если n равно 1 камню, то игрок, который должен сделать ход, оставит 0 камней, и mex({0}) = 1 дает нимбер для этого случая. Если n равно 2 камням, то игрок, который должен сделать ход, может оставить 0 или 1 камень, что дает нимбер 2 как mex нимберов {0, 1}. В общем случае, игрок, который должен сделать ход с кучей из n камней, может оставить от 0 до n − 1 камней; mex нимберов {0, 1, …, n − 1} всегда равен нимберу n . Первый игрок выигрывает в Ним тогда и только тогда, когда Нимбер не равен нулю, поэтому из этого анализа мы можем сделать вывод, что первый игрок выигрывает тогда и только тогда, когда начальное количество камней в игре Ним с одной кучей не равно нулю; выигрышный ход — забрать все камни.

Если мы изменим игру так, что игрок, который должен сделать ход, может взять только до 3 камней, то при n = 4 камнях последующие состояния будут иметь нимберы {1, 2, 3}, что даст mex 0. Поскольку нимбер для 4 камней равен 0, первый игрок проигрывает. Стратегия второго игрока заключается в том, чтобы ответить на любой ход первого игрока, взяв оставшиеся камни. При n = 5 камнях нимберами последующих состояний камней 2, 3 и 4 являются нимберы 2, 3 и 0 (как мы только что вычислили); mex набора нимберов {0, 2, 3} является нимбером 1, поэтому начало с 5 камней в этой игре является победой для первого игрока.

Более подробную информацию о значении значений нимбера см. в разделе nimbers .