- Ним (игра)
-
Ним — математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет.
В классическом варианте игры число кучек равняется трём.
Ним — конечная игра с полной информацией.
Содержание
История игры
Игра Ним попала в Европу в XVI веке из Китая. Имя «ним» было дано игре американским математиком Чарльзом Бутоном (англ. Chalres Bouton), описавшим в 1901 году выигрышную стратегию игры.
Существует несколько вариантов происхождения названия игры:
- от немецкого глагола Nimm или старо-английского глагола Nim, имеющих значение «брать»;
- от английского глагола WIN («побеждать»), переворачиванием слова;
Стратегия игры
В общем случае рассматривается кучек предметов с предметами. Игроки ходят по очереди. Ход заключается в том, что игрок берёт из кучки предметов.
Каждой позиции игры ставится в соответствие ним-сумма этой позиции — результат сложения размеров всех кучек в двоичной системе счисления без учёта переноса разрядов, то есть сложение двоичных разрядов чисел в поле вычетов по модулю 2:
Выигрышная стратегия состоит в том, чтобы оставлять после своего хода позицию с ним-суммой, равной нулю. Она основана на том, что из любой позиции с ним-суммой, не равной нулю, можно одним ходом получить позицию с нулевой ним-суммой, а из позиции с нулевой ним-суммой любой ход ведёт в позицию с ним-суммой, отличной от нуля.
Пример: предположим, в игре три кучки, в них соответственно 2 (0010 в бинарном представлении), 8 (1000) и 13 (1101) предметов. Ним-сумма этой позиции — 7 (0111). Следовательно, выигрышная стратегия состоит в том, чтобы взять 3 предмета из третьей кучки — там останется 10 (1010) предметов, и ним-сумма позиции станет 0 (0000). Предположим, после вашего хода противник забирает все предметы из первой кучки — выигрышная стратегия будет заключаться в том, чтобы забрать 2 предмета из третьей кучки. В таком случае после вашего хода в кучках будет соответственно 0 (0000), 8 (1000) и 8 (1000) предметов, ним-сумма по прежнему будет равняться 0.
Варианты игры
Мизер
В этом варианте игрок, взявший последний объект, проигрывает.
Выигрышная стратегия совпадает с выигрышной стратегией обычной игры до того момента, когда в результате хода игрока на столе должно остаться некоторое количество кучек с единственным предметом в каждой из них. В случае мизера игрок должен оставить нечётное количество кучек, тогда как выигрышная стратегия обычной игры требует оставить чётное количество кучек, чтобы ним-сумма равнялась нулю.
Мультиним
Более общий случай игры Ним был предложен Муром (Eliakim Moore). В игре игрокам разрешается брать предметы из максимум кучек. Легко видеть, что обычная игра ним является .
Решение такой задачи удивительно просто. Запишем размеры каждой кучки в двоичной системе счисления. Затем просуммируем эти числа в -ичной системе счисления без переносов разрядов. Если получилось число 0, то текущая позиция проигрышная, иначе — выигрышная (и из неё есть ход в позицию с нулевой величиной).
Ним в массовой культуре
Игра Ним занимает важное место в сюжете фильма «В прошлом году в Мариенбаде».[1]
См. также
- Функция Шпрага-Гранди
- Игра Баше
- Пешечная дуэль
- Хакенбуш
Примечания
- ↑ Oliver Knill Math in Movies: Last year in Marienbad (англ.). Math in Movies. Department of Mathematics Harvard University. Архивировано из первоисточника 21 февраля 2012. Проверено 22 июня 2009.
Литература
- Болл У., Коксетер Г. Математические эссе и развлечения = 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.
Категория:- Математические игры
Wikimedia Foundation. 2010.