Мекс (математика) - Mex (mathematics)

В математике Мекс из подмножество из хорошо организованный set - это наименьшее значение из всего набора, которое не принадлежит подмножеству. То есть это минимум ценность набор дополнений. Название «мекс» - это сокращение от «мминимум бывшийвключено "значение".

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

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

Примеры

Все следующие примеры предполагают, что данное множество является подмножеством класса порядковые номера:

${\displaystyle {\mbox{mex}}(\emptyset )=0}$

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

${\displaystyle {\mbox{mex}}(\{0,2,4,6,\ldots \})=1}$

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

${\displaystyle {\mbox{mex}}(\{0,1,2,3,\ldots \})=\omega }$

${\displaystyle {\mbox{mex}}(\{0,1,2,3,\ldots ,\omega \})=\omega +1}$

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

Теория игры

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

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

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

Видеть ловцы для более подробной информации о значении nimber-значений.

Рекомендации

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