Ним (игра)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Ним — математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет.

В классическом варианте игры число кучек равняется трём.

Ним — конечная игра с полной информацией.

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

История игры[править | править вики-текст]

Игра Ним попала в Европу в XVI веке из Китая. Имя «ним» было дано игре американским математиком Чарльзом Бутоном (англ. Chalres Bouton), описавшим в 1901 году выигрышную стратегию игры.

Существует несколько вариантов происхождения названия игры:

  • от немецкого глагола Nimm или старо-английского глагола Nim, имеющих значение «брать»;
  • от английского глагола WIN («побеждать»), переворачиванием слова;

Варианты игры[править | править вики-текст]

Шоколадка[править | править вики-текст]

Есть шоколадка m×n, одна долька «отравленная». Игрок своим ходом разламывает шоколадку по линии и съедает неотравленную часть. Проигрывает тот, кому останется отравленная долька.

Игра эквивалентна ниму с четырьмя кучками.

Мизер[править | править вики-текст]

В этом варианте игрок, взявший последний объект, проигрывает.

Выигрышная стратегия совпадает с выигрышной стратегией обычной игры до того момента, когда в результате хода игрока на столе должно остаться некоторое количество кучек с единственным предметом в каждой из них. В случае мизера игрок должен оставить нечётное количество кучек, тогда как выигрышная стратегия обычной игры требует оставить чётное количество кучек, чтобы ним-сумма равнялась нулю.

Это можно сформулировать так: если осталась ровно одна кучка, содержащая более одного предмета, то забрать из неё все предметы или все кроме одного, чтобы осталось нечетное количество единичных кучек; иначе придерживаться выигрышной стратегии обычной игры.

Мультиним[править | править вики-текст]

Более общий случай игры Ним был предложен Муром (Eliakim Moore). В игре Nim_i игрокам разрешается брать предметы из максимум i кучек. Легко видеть, что обычная игра ним является Nim_1.

Решение такой задачи удивительно просто. Запишем размеры каждой кучки в двоичной системе счисления. Затем просуммируем эти числа в (i+1)-ичной системе счисления без переносов разрядов. Если получилось число 0, то текущая позиция проигрышная, иначе — выигрышная (и из неё есть ход в позицию с нулевой величиной).

Форкед-ним[править | править вики-текст]

Еще один вариант игры был предложен Матвеем Бернштейном. В нем можно произвольно разбивать любую кучку на две произвольные кучки вместо хода. Во всем остальном игра ведется по обычным правилам.

В кино[править | править вики-текст]

Эта игра служит метафорой происходящего в фильме «В прошлом году в Мариенбаде».[1]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Oliver Knill. Math in Movies: Last year in Marienbad (англ.). Math in Movies. Department of Mathematics Harvard University. Проверено 22 июня 2009. Архивировано из первоисточника 21 февраля 2012.

Литература[править | править вики-текст]