Ним (игра)
Ним — игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет. В классическом варианте игры число кучек равняется трём.
Частный случай, когда кучка одна, но максимальное число предметов, которые можно взять за ход, ограничено, известен как игра Баше. Ним — конечная игра с полной информацией. Классическая игра Ним имеет фундаментальное значение для теоремы Шпрага — Гранди. Эта теорема утверждает, что обычная игра в сумму беспристрастных игр эквивалентна обычной игре в Ним. При этом каждой беспристрастной игре-слагаемому соответствует кучка Ним, число предметов в которой равно значению функции Шпрага — Гранди для игровой позиции данной игры.
История игры
Китайская игра ним упоминалась европейцами ещё в XVI веке. Имя «ним» было дано игре американским математиком Чарльзом Бутоном (англ. Charles Bouton), описавшим в 1901 году выигрышную стратегию игры. Существует несколько вариантов происхождения названия игры:
- от немецкого глагола nehmen или от староанглийского глагола Nim, имеющих значение «брать»;
- ананим от английского глагола Win («побеждать»).
Игрушка «Доктор Ним», небольшой шариковый компьютер, придуманный в 1960-х, играл не в ним, а в игру Баше.
Стратегия игры
В общем случае рассматривается [math]\displaystyle{ p }[/math] кучек предметов с [math]\displaystyle{ N_1, N_2, \cdots N_p }[/math] предметами. Игроки ходят по очереди. Ход заключается в том, что игрок берёт из кучки [math]\displaystyle{ i \in [1, p] }[/math] [math]\displaystyle{ n \in [1, N_i] }[/math] предметов. Каждой позиции игры ставится в соответствие ним-сумма этой позиции — результат сложения размеров всех кучек в двоичной системе счисления без учёта переноса разрядов, то есть сложение двоичных разрядов чисел в поле вычетов по модулю 2: [math]\displaystyle{ S=N_1 \oplus N_2 \oplus \cdots \oplus N_p }[/math]
Выигрышная стратегия состоит в том, чтобы оставлять после своего хода позицию с ним-суммой, равной нулю. Она основана на том, что из любой позиции с ним-суммой, не равной нулю, можно одним ходом получить позицию с нулевой ним-суммой, а из позиции с нулевой ним-суммой любой ход ведёт в позицию с ним-суммой, отличной от нуля.
Пример: предположим, в игре три кучки, в них соответственно 2 (0010 в бинарном представлении), 8 (1000) и 13 (1101) предметов. Ним-сумма этой позиции — 7 (0111). Следовательно, выигрышная стратегия состоит в том, чтобы взять три предмета из третьей кучки — там останется 10 (1010) предметов, и ним-сумма позиции станет 0 (0000). Предположим, после вашего хода противник забирает все предметы из первой кучки — выигрышная стратегия будет заключаться в том, чтобы забрать два предмета из третьей кучки. В таком случае после вашего хода в кучках будет соответственно 0 (0000), 8 (1000) и 8 (1000) предметов, ним-сумма по прежнему будет равняться 0.
Варианты
Обратный ним
Игроки дополняют кучки до некоего [math]\displaystyle{ N }[/math]. Имеется как квест в компьютерной игре «Космические рейнджеры». Игра эквивалентна обычному ниму с состоянием [math]\displaystyle{ \{N - N_i \}_{i=1}^p }[/math].
Ним-Баше
Можно брать не более [math]\displaystyle{ k }[/math] предметов. Игра эквивалентна обычному ниму с состоянием [math]\displaystyle{ \{N_i \operatorname{mod} (k+1) \}_{i=1}^p }[/math]
Шоколадка
Есть шоколадка [math]\displaystyle{ m \times n }[/math], одна долька «отравленная». Игрок своим ходом разламывает шоколадку по линии и съедает неотравленную часть. Проигрывает тот, кому останется отравленная долька. Игра эквивалентна ниму с четырьмя кучками.
Мизер
В этом варианте игрок, взявший последний объект, проигрывает. Выигрышная стратегия совпадает с выигрышной стратегией обычной игры до того момента, когда в результате хода игрока на столе должно остаться некоторое количество кучек с единственным предметом в каждой из них. В случае мизера игрок должен оставить нечётное количество кучек, тогда как выигрышная стратегия обычной игры требует оставить чётное количество кучек, чтобы ним-сумма равнялась нулю. Это можно сформулировать так: если осталась ровно одна кучка, содержащая более одного предмета, то забрать из неё все предметы или все кроме одного, чтобы осталось нечетное количество единичных кучек; иначе придерживаться выигрышной стратегии обычной игры.
Мультиним
Более общий случай игры Ним был предложен Элиакимом Муром. В игре [math]\displaystyle{ Nim_i }[/math] игрокам разрешается брать предметы из максимум [math]\displaystyle{ i }[/math] кучек. Легко видеть, что обычная игра ним является [math]\displaystyle{ Nim_1 }[/math]. Для решения необходимо записать размеры каждой кучки в двоичной системе счисления и просуммировать эти числа в [math]\displaystyle{ (i+1) }[/math]-ичной системе счисления без переносов разрядов. Если получилось число 0, то текущая позиция проигрышная, иначе — выигрышная и из неё есть ход в позицию с нулевой величиной.
Форкед-ним
Еще один вариант игры был предложен Матвеем Бернштейном. В нем можно произвольно разбивать любую кучку на две произвольные кучки вместо хода. Во всем остальном игра ведется по обычным правилам.
В кино и телевидении
- Эта игра служит метафорой происходящего в фильме «В прошлом году в Мариенбаде»[1].
См. также
Примечания
- ↑ Oliver Knill. Math in Movies: Last year in Marienbad (англ.). Math in Movies. Department of Mathematics Harvard University. Дата обращения: 22 июня 2009. Архивировано 21 февраля 2012 года.
Литература
- Болл У., Коксетер Г. Математические эссе и развлечения = Mathematical Recreations and Essays. — М.: Мир, 1986. — С. 47-51.
- Фомин С. В. Системы счисления. — 5-е изд. — М.: Наука, 1987. — С. 48.
- Гарднер М. Крестики-нолики. —М.: Мир, 1988. ISBN 5-03-001234-6.
- Jean-Paul Delahaye. Stratégies magiques au pays de Nim // Pour la science : Журнал. — Paris: Belin, 2009. — Т. 377, № 3. — С. 88-93. Архивировано 10 июня 2013 года.