Нім (гра)
Нім — математична гра, в якій два гравці по черзі беруть предмети, розкладені на кілька купок. За один хід може бути взято будь-яку кількість предметів (більше нуля) з однієї купки. В нормальній грі виграє гравець, який взяв останній предмет, в мізер-грі цей гравець програє.
У класичному варіанті гри число купок дорівнює трьом.
Окремий випадок, коли купка одна, але максимальне число предметів, які можна взяти за хід, обмежена, відома як гра Баше.
Нім — кінцева гра з повною інформацією.
Класична гра Нім має фундаментальне значення для теореми Шпрага-Гранді. Ця теорема стверджує, що звичайна гра в суму неупереджених ігор може прирівнюватися до гри в Нім. При цьому кожній неупередженій грі-доданку відповідає купка Нім, число предметів в якій дорівнює значенню функції Шпраг-Гранді для ігрової позиції даної гри.
Математична теорія
Нім розв'язали для будь-якої кількості купок і об'єктів. Існує простий спосіб обчислення, який з гравців виграє і, які виграшні кроки має гравець.
Ключ до теорії гри — це двійкова поцифрова сума розмірів куп, тобто, сума (двійкова) нехтуючи всіма переносами з однієї цифри в іншу. Ця операція також відома як "додавання за модулем два" (xor). В комбінаторній теорії ігор її зазвичай називають нім-сума, як і в цій статті. Нім-сума x і y записується x ⊕ y, щоб відрізнити від звичайної суми, x + y. Наведемо приклад, обчислень з купками розмірів 3, 4 і 5:
Двійкова Десяткова 0112 310 Купа A 1002 410 Купа B 1012 510 Купа C --- 0102 210 Нім-сума куп A, B, і C, 3 ⊕ 4 ⊕ 5 = 2
Рівнозначна процедура, яку часто легше виконати подумково, полягає в вираженні розмірів куп як сум степенів 2,викреслити пари однакових степенів, і тоді додати, що залишилось:
3 = 0 + 2 + 1 = 2 1 Купа A 4 = 4 + 0 + 0 = 4 Купа B 5 = 4 + 0 + 1 = 4 1 Купа C -------------------------------------------------------------------- 2 = 2 Те, що залишилось після скорочення 1-ї і 4-ї
В нормальній грі виграшна стратегія полягає в завершенні кожного кроку з нім-сумою 0. Це можливо завжди, якщо нім-сума перед кроком була не нуль. Якщо нім-сума нуль, тоді наступний гравець програє, якщо інший гравець не припуститься помилки. Щоб знайти який крок зробити, нехай X буде нім-сумою розмірів всіх куп. Знайти купу нім-сума якої з X менша ніж розмір цієї купи — виграшна стратегія полягає в зменшені розміру цієї купи до нім-суми її поточного розміру з X. У вищенаведеному прикладі, підраховуючи нім-суму розмірів X = 3 ⊕ 4 ⊕ 5 = 2. Нім-суми окремих куп з X:
- A ⊕ X = 3 ⊕ 2 = 1 [Бо (011) ⊕ (010) = 001 ]
- B ⊕ X = 4 ⊕ 2 = 6
- C ⊕ X = 5 ⊕ 2 = 7
Єдина купа нім-сума якої з X менша ніж розмір купи це A, отже виграшний крок це зменшення розміру A до 1 (видаляючи два об'єкти).
Як окремий простий приклад можна розглянути випадок з двома купами. Тут стратегія буде зменшити кількість предметів в більшій купі до кількості предметів в меншій. Після цього неважливо, що робитиме супротивник, завжди можливо буде зрівняти купи знов.
У разі мізер-гри, стратегія відрізняється лише коли стратегія нормальної гри залишає лише купи розміру один. Тоді правильний крок — це залишити непарну кількість куп розміру один (в нормальній грі правильно було б залишити парну кількість таких куп).
Література
- Болл У., Коксетер Г. Математические эссе и развлечения = Mathematical Recreations and Essays. — М. : Мир, 1986. — С. 47-51.