Нимбер

Число, используемое в комбинаторной теории игр

В математике нимберы , также называемые числами Гранди , вводятся в комбинаторной теории игр , где они определяются как значения куч в игре Ним . Нимберы — это порядковые числа, наделенные сложением нимберов и умножением нимберов , которые отличаются от порядкового сложения и умножения нимберов .

Из-за теоремы Спрага–Гранди , которая гласит, что каждая беспристрастная игра эквивалентна куче нимов определенного размера, нимберы возникают в гораздо большем классе беспристрастных игр. Они также могут встречаться в партийных играх, таких как Domineering .

Операции сложения и умножения нимберов ассоциативны и коммутативны. Каждый нимбер является своим собственным аддитивным обратным . В частности, для некоторых пар ординалов их сумма нимберов меньше любого из слагаемых. ^[1] Операция минимального исключения применяется к наборам нимберов.

Использует

Ним

Ним — это игра, в которой два игрока по очереди извлекают предметы из разных куч. Поскольку ходы зависят только от позиции, а не от того, кто из двух игроков в данный момент двигается, и где выплаты симметричны, Ним — беспристрастная игра. На каждом ходу игрок должен извлечь хотя бы один предмет и может извлечь любое количество предметов, при условии, что все они из одной кучи. Цель игры — стать игроком, который извлечет последний предмет. Нимбер кучи — это просто количество предметов в этой куче. Используя сложение нимов, можно вычислить нимбер игры в целом. Выигрышная стратегия — заставить нимбер игры стать равным 0 для хода противника. ^[2]

Крам

Cram — это игра, в которую часто играют на прямоугольной доске, в которой игроки по очереди размещают домино по горизонтали или вертикали до тех пор, пока больше нельзя будет разместить домино. Первый игрок, который не может сделать ход, проигрывает. Поскольку возможные ходы для обоих игроков одинаковы, это беспристрастная игра, и она может иметь значение нимбера. Например, любая доска, которая имеет четный размер на четный размер, будет иметь нимбер 0. Любая доска, которая имеет четный размер на нечетный размер, будет иметь ненулевой нимбер. Любая доска 2 × n будет иметь нимбер 0 для всех четных n и нимбер 1 для всех нечетных n .

Игра Норткотта

В игре Норткотта колышки для каждого игрока размещаются вдоль столбца с конечным числом ячеек. Каждый ход каждый игрок должен переместить фишку вверх или вниз по столбцу, но не может пройти мимо фишки другого игрока. Несколько столбцов сложены вместе, чтобы добавить сложности. Игрок, который больше не может делать ходов, проигрывает. В отличие от многих других игр, связанных с нимбером, количество ячеек между двумя фишками в каждом ряду равно размеру куч нимов. Если ваш противник увеличивает количество ячеек между двумя фишками, просто уменьшите его на следующем ходу. В противном случае сыграйте в игру ним и сделайте так, чтобы ним-сумма количества ячеек между фишками в каждом ряду была равна 0. ^[3]

Хакенбуш

Hackenbush — игра, придуманная математиком Джоном Хортоном Конвеем . В нее можно играть на любой конфигурации цветных отрезков линий, соединенных друг с другом своими конечными точками и с линией «земли». Игроки по очереди удаляют отрезки линий. Беспристрастная версия игры, то есть игра, которую можно анализировать с помощью нимберов, может быть найдена путем удаления различий из линий, что позволяет любому игроку отрезать любую ветку. Любые отрезки, зависящие от недавно удаленного отрезка для соединения с линией земли, также удаляются. Таким образом, каждое соединение с землей можно считать кучей нимов со значением нимбера. Кроме того, все отдельные соединения с линией земли также можно суммировать для получения нимбера состояния игры.

Добавление

Сложение нимбера (также известное как сложение нимбера ) может использоваться для вычисления размера одной кучи ним, эквивалентной набору куч ним. Оно определяется рекурсивно, где минимальный исключающий mex( S ) множества S ординалов определяется как наименьший ординал, который не является элементом S . $${\displaystyle \alpha \oplus \beta =\operatorname {mex} \!{\bigl (}\{\alpha '\oplus \beta :\alpha '<\alpha \}\cup \{\alpha \oplus \beta ':\beta '<\beta \}{\bigr )},}$$

Для конечных ординалов ним-сумма легко вычисляется на компьютере путем побитового исключающего ИЛИ (XOR, обозначается ⊕ ) соответствующих чисел. Например, ним-сумма 7 и 14 может быть найдена путем записи 7 как 111 и 14 как 1110; разряд единиц добавляет 1; разряд двоек добавляет 2, который мы заменяем на 0; разряд четверок добавляет 2, который мы заменяем на 0; разряд восьмерок добавляет 1. Таким образом, ним-сумма записывается в двоичном виде как 1001 или в десятичном виде как 9.

Это свойство сложения следует из того факта, что и mex, и XOR дают выигрышную стратегию для Nim, и такая стратегия может быть только одна; или это можно показать напрямую по индукции: пусть α и β будут двумя конечными ординалами, и предположим, что ним-сумма всех пар с одним из них уменьшена уже определена. Единственное число, чье XOR с α равно α ⊕ β, — это β , и наоборот; таким образом, α ⊕ β исключается. С другой стороны, для любого ординала γ < α ⊕ β , XOR ξ со всеми α , β и γ должно привести к уменьшению для одного из них (так как лидирующая 1 в ξ должна присутствовать по крайней мере в одном из трех); поскольку у нас должно быть либо, то γ включается как либо , и, следовательно, α ⊕ β является минимальным исключенным ординалом. $${\displaystyle \zeta :=\alpha \oplus \beta \oplus \gamma }$$ $${\displaystyle \zeta \oplus \gamma =\alpha \oplus \beta >\gamma ,}$$ $${\displaystyle {\begin{aligned}\alpha >\zeta \oplus \alpha &=\beta \oplus \gamma ,\\[4pt]\beta >\zeta \oplus \beta &=\alpha \oplus \gamma ;\end{aligned}}}$$ $${\displaystyle {\begin{aligned}(\beta \oplus \gamma )\oplus \beta ,\\[4pt]\alpha \oplus (\alpha \oplus \gamma );\end{aligned}}}$$

Сложение нимбера ассоциативно и коммутативно , с 0 в качестве элемента аддитивной идентичности . Более того, нимбер является своим собственным аддитивным обратным . ^[4] Из этого следует, что α ⊕ β = 0 тогда и только тогда, когда α = β .

Умножение

Умножение нимбера ( ним-умножение ) определяется рекурсивно:

$${\displaystyle \alpha \,\beta =\operatorname {mex} \!{\bigl (}\{\alpha '\beta \oplus \alpha \,\beta '\oplus \alpha '\beta ':\alpha '<\alpha ,\beta '<\beta \}{\bigr )}.}$$

Умножение нимбера ассоциативно и коммутативно, с порядковым числом 1 в качестве мультипликативного тождественного элемента . Более того, умножение нимбера распределяется по сложению нимбера. ^[4]

Таким образом, за исключением того факта, что нимберы образуют собственный класс , а не множество, класс нимберов образует кольцо . Фактически, он даже определяет алгебраически замкнутое поле характеристики 2, с нимбером , мультипликативно обратным ненулевому ординалу α, заданным как

$${\displaystyle \alpha ^{-1}=\operatorname {mex} (S),}$$где S — наименьший набор порядковых чисел (чисел), такой что

1. 0 — элемент S ;
2. если 0 < α ′ < α и β' является элементом S , то также является элементом S . ${\displaystyle {\tfrac {1+(\alpha '\oplus \alpha )\beta '}{\alpha '}}}$

Для всех натуральных чисел n множество чисел, меньших 2 ^{2 n ,} образует поле Галуа GF(2 ^{2 n} ) порядка  2 ^{2 n} . Следовательно, множество конечных чисел изоморфно прямому пределу при n → ∞ полей GF(2 ^{2 n} ) . Это подполе не является алгебраически замкнутым, поскольку ни одно поле GF(2 ^k ) с k, не являющимся степенью 2, не содержится ни в одном из этих полей и, следовательно, не содержится в их прямом пределе; например, многочлен x ³ + x + 1 , имеющий корень в GF(2 ³ ) , не имеет корня в множестве конечных чисел.

Так же, как и в случае сложения чисел, существует способ вычисления произведения чисел конечных ординалов. Это определяется правилами, которые

1. Произведение числа Ферма в степени 2 (чисел вида 2 ^{2 n} ) на меньшее число равно их обычному произведению;
2. Квадрат числа Ферма 2-й степени x равен 3 x /2 , если вычислить его при обычном умножении натуральных чисел.

Наименьшее алгебраически замкнутое поле чисел — это множество чисел, меньших ординала ω ω ^{ω ,} где ω — наименьший бесконечный ординал. Отсюда следует, что как число, ω ^{ω ω} трансцендентно над полем. ^[5]

Таблицы сложения и умножения

В следующих таблицах показано сложение и умножение первых 16 чисел.

Это подмножество замкнуто относительно обеих операций, поскольку 16 имеет вид  2 ^{2 n} . (Если вы предпочитаете простые текстовые таблицы, они здесь .)

Сложение чисел (последовательность A003987 в OEIS )
Это также таблица Кэли Z ₂ ⁴ – или таблица побитовых операций XOR
. Маленькие матрицы показывают отдельные цифры двоичных чисел.

Умножение чисел (последовательность A051775 в OEIS )
Ненулевые элементы образуют таблицу Кэли Z 15. Малые матрицы представляют собой переставленные двоичные матрицы Уолша .

Умножение нимбера степеней двойки (последовательность A223541 в OEIS )
Вычисление нимбер-произведений степеней двойки является решающим моментом в рекурсивном алгоритме умножения нимбера.

Смотрите также

• Сюрреалистическое число

Примечания

1. Достижения в компьютерных играх: 14-я Международная конференция, ACG 2015, Лейден, Нидерланды, 1–3 июля 2015 г., Пересмотренные избранные статьи . Херик, Яап ван ден,, Плаат, Аске,, Костерс, Вальтер. Чам. 24 декабря 2015 г. ISBN 978-3319279923. OCLC  933627646.{{cite book}}: CS1 maint: местоположение отсутствует издатель ( ссылка ) CS1 maint: другие ( ссылка )
2. Анани., Левитин (2012). Введение в проектирование и анализ алгоритмов (3-е изд.). Бостон: Pearson. ISBN 9780132316811. OCLC  743298766.
3. "Теория беспристрастных игр" (PDF) . 3 февраля 2009 г.
4. Brown, Ezra ; Guy, Richard K. (2021). "2.5 Арифметика Нима и алгебра Нима". Единство комбинаторики . Том 36 Математических монографий Каруса (переиздание). Американское математическое общество . стр. 35. ISBN 978-1-4704-6509-4.
5. Конвей 1976, стр. 61.

Ссылки

• Конвей, Джон Хортон (1976). О числах и играх . Academic Press Inc. (London) Ltd.
• Ленстра, HW (1978). Умножение Ним . Отчет IHES/M/78/211. Институт высших научных исследований. hdl : 1887/2125.
• Шлейхер, Дирк; Столл, Майкл (2004). «Введение в игры и числа Конвея». arXiv : math.DO/0410026 .в котором обсуждаются игры, сюрреалистические числа и числа.