Нім — математична гра, в якій два гравці по черзі беруть предмети, розкладені на кілька купок. За один хід може бути взято будь-яку кількість предметів (більше нуля) з однієї купки. В нормальній грі виграє гравець, який взяв останній предмет, в мізер-грі цей гравець програє.
У класичному варіанті гри число купок дорівнює трьом.
Окремий випадок, коли купка одна, але максимальне число предметів, які можна взяти за хід, обмежена, відома як гра Баше.
Нім — кінцева гра з повною інформацією.
Класична гра Нім має фундаментальне значення для (теореми Шпрага-Гранді). Ця теорема стверджує, що звичайна гра в суму (неупереджених ігор) може прирівнюватися до гри в Нім. При цьому кожній неупередженій грі-доданку відповідає купка Нім, число предметів в якій дорівнює значенню функції Шпрага-Гранді для ігрової позиції даної гри.
Математична теорія
Нім розв'язали для будь-якої кількості купок і об'єктів. Існує простий спосіб обчислення, який з гравців виграє і, які виграшні кроки має гравець.
Ключ до теорії гри — це (двійкова) поцифрова сума розмірів куп, тобто, сума (двійкова) нехтуючи всіма переносами з однієї цифри в іншу. Ця операція також відома як "(додавання за модулем два)" (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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет