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

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

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

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

Примеры

Во всех следующих примерах предполагается, что данный набор является подмножеством класса порядковых чисел : ${\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 для игры, которая немедленно проиграна первым игроком, и равно сумме чисел всех возможных следующих позиций для любой другой игры.

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

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

См. «Нимберы» для получения более подробной информации о значении значений нимберов.

Ссылки

^ Конвей, Джон Х. (2001). О числах и играх (2-е изд.). АК Петерс. п. 124. ИСБН 1-56881-127-6 .
^ валлийский, DJA; Пауэлл, МБ (1967). «Верхняя оценка хроматического числа графа и ее применение к задачам составления расписания» . Компьютерный журнал . 10 (1): 85–86. дои : 10.1093/comjnl/10.1.85 .

[1] Конвей, Джон Х. (2001). О числах и играх (2-е изд.). АК Петерс. п. 124. ИСБН 1-56881-127-6 .

[2] валлийский, DJA; Пауэлл, МБ (1967). «Верхняя оценка хроматического числа графа и ее применение к задачам составления расписания» . Компьютерный журнал . 10 (1): 85–86. дои : 10.1093/comjnl/10.1.85 .

[1]

[2]