Cybernetics Wiki
Advertisement

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

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

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

История игры[]

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

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

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

Стратегия игры[]

В общем случае рассматривается кучек предметов с предметами. Игроки ходят по очереди. Ход заключается в том, что игрок берёт из кучки предметов.

Каждой позиции игры ставится в соответствие ним-сумма этой позиции — результат сложения размеров всех кучек в двоичной системе счисления без учёта переноса разрядов, то есть сложение двоичных разрядов чисел в поле вычетов по модулю 2:

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

Варианты игры[]

Мизер[]

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

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

Мультиним[]

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

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

Ним в массовой культуре[]

Игра ним занимает важное место в сюжете фильма «В прошлом году в Мариенбаде».[1]

См. также[]

Примечания[]

  1. Oliver Knill Math in Movies: Last year in Marienbad (англ.). Math in Movies. Department of Mathematics Harvard University. Проверено 22 июня 2009.


Литература[]

  • Болл У., Коксетер Г. Математические эссе и развлечения = Mathematical Recreations and Essays. — М.: Мир, 1986. — С. 474.
  • Гарднер М. Крестики-нолики.
  • Jean-Paul Delahaye Stratégies magiques au pays de Nim // Pour la science : Журнал. — Paris: Belin, 2009. — Т. 377. — № 3. — С. 88-93.
Advertisement