Введение

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

В математике, нимберы, также называемые числами Гранди, вводятся в комбинаторной теории игр, где они определяются как значения куч в игре Ним. Нимберы – это порядковые числа, наделённые операциями нимберного сложения и нимберного умножения, которые отличаются от обычного сложения и умножения порядковых чисел. Благодаря теореме Спрага — Гранди, утверждающей, что любая беспристрастная игра эквивалентна куче Ним определённого размера, нимберы возникают в гораздо более широком классе беспристрастных игр. Они также могут встречаться в партийных играх, таких как Доминирование. Операции нимберного сложения и умножения ассоциативны и коммутативны. Каждый нимбер является своим собственным аддитивным обратным. В частности, для некоторых пар порядковых чисел их нимберная сумма меньше любого из слагаемых. Операция минимального исключённого (mex) применяется к множествам нимберов.

Ним

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

Задерживай .

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

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

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

Хакенбуш

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

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

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