Числа

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

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

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

Использование

Nim

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

Зубрить

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

игра Норткотта

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

Хакенбуш

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

Добавление

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

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

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

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

Умножение

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

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

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

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

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

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

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

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

Нимберальное произведение 2-степени Ферма (числа вида $2 2 н$ ) с меньшим числом равна их обычному произведению;
Нимбер-квадрат 2-степени Ферма $x$ равен $3 x /2$ , если его вычислить при обычном умножении натуральных чисел.

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

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

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

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

См. также

Сюрреалистический номер

Примечания

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

Ссылки

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

[1] Достижения в компьютерных играх: 14-я Международная конференция ACG 2015, Лейден, Нидерланды, 1-3 июля 2015 г., Пересмотренные избранные статьи . Херик, Яап ван ден, Плаат, Аске, Костерс, Вальтер. Чам. 24 декабря 2015 г. ISBN 978-3319279923 . OCLC 933627646 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) CS1 maint: другие ( ссылка )

[2] Анани., Левитин (2012). Введение в разработку и анализ алгоритмов (3-е изд.). Бостон: Пирсон. ISBN 9780132316811 . OCLC 743298766 .

[3] «Теория беспристрастных игр» (PDF) . 3 февраля 2009 г.

[Unity2021-4] Перейти обратно: ^а ^б Браун, Эзра ; Гай, Ричард К. (2021). «2.5 Арифметика Нима и алгебра Нима». Единство комбинаторики . Том. 36 математических монографий Каруса (переиздание). Американское математическое общество . п. 35. ISBN 978-1-4704-6509-4 .

[5] Конвей 1976, с. 61.

[1]

[2]

[3]

[4]

[5]