Ним (игра)
Материал из Википедии — свободной энциклопедии
Ним — математическая игра, в которой два игрока по очереди вынимают предметы из кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. В стандартном варианте игры выигрывает тот, кто берёт последний предмет, а число кучек равно трём.
Ним — конечная игра с полной информацией.
[править] Решение игры
Каждой позиции игры ставится в соответствие ним-сумма этой позиции — результат сложения размеров всех кучек в двоичной системе счисления без учёта переноса разрядов, т. е. сложение двоичных разрядов чисел в поле вычетов по модулю 2.
Выигрывающая стратегия состоит в том, чтобы оставлять после своего хода позицию с ним-суммой, равной нулю. Она основана на том, что из любой позиции с ним-суммой, не равной нулю, можно одним ходом получить позицию с нулевой ним-суммой, а из позиции с нулевой ним-суммой любой ход ведёт в позицию с ним-суммой, отличной от нуля.
[править] Литература
- Болл У., Коксетер Г. Математические эссе и развлечения = Mathematical Recreations and Essays. — М.: Мир, 1986. — С. 474.
- Фомин С. В. Системы счисления. — 5-е изд. — М.: Наука, 1987. — С. 48.
