Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Нім — математична гра, в якій два гравці по черзі беруть предмети, розкладені на кілька купок. За один хід може бути взято будь-яку кількість предметів (більше нуля) з однієї купки. В нормальній грі виграє гравець, який взяв останній предмет, в мізер-грі цей гравець програє.
У класичному варіанті гри число купок дорівнює трьом.
Окремий випадок, коли купка одна, але максимальне число предметів, які можна взяти за хід, обмежена, відома як гра Баше.
Нім — кінцева гра з повною інформацією.
Класична гра Нім має фундаментальне значення для теореми Шпрага-Гранді. Ця теорема стверджує, що звичайна гра в суму неупереджених ігор може прирівнюватися до гри в Нім. При цьому кожній неупередженій грі-доданку відповідає купка Нім, число предметів в якій дорівнює значенню функції Шпрага-Гранді для ігрової позиції даної гри.
Математична теорія
Нім розв'язали для будь-якої кількості купок і об'єктів. Існує простий спосіб обчислення, який з гравців виграє і, які виграшні кроки має гравець.
Ключ до теорії гри — це двійкова поцифрова сума розмірів куп, тобто, сума (двійкова) нехтуючи всіма переносами з однієї цифри в іншу. Ця операція також відома як "додавання за модулем два" (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, Інтернет
Nim matematichna gra v yakij dva gravci po cherzi berut predmeti rozkladeni na kilka kupok Za odin hid mozhe buti vzyato bud yaku kilkist predmetiv bilshe nulya z odniyeyi kupki V normalnij gri vigraye gravec yakij vzyav ostannij predmet v mizer gri cej gravec prograye Sirniki rozkladeni ryadkami dlya gri v Nim Gravci po cherzi vibirayut ryadok i vidalyayut z nogo bud yaku kilkist sirnikiv U klasichnomu varianti gri chislo kupok dorivnyuye trom Okremij vipadok koli kupka odna ale maksimalne chislo predmetiv yaki mozhna vzyati za hid obmezhena vidoma yak gra Bashe Nim kinceva gra z povnoyu informaciyeyu Klasichna gra Nim maye fundamentalne znachennya dlya teoremi Shpraga Grandi Cya teorema stverdzhuye sho zvichajna gra v sumu neuperedzhenih igor mozhe pririvnyuvatisya do gri v Nim Pri comu kozhnij neuperedzhenij gri dodanku vidpovidaye kupka Nim chislo predmetiv v yakij dorivnyuye znachennyu funkciyi Shpraga Grandi dlya igrovoyi poziciyi danoyi gri Matematichna teoriyaNim rozv yazali dlya bud yakoyi kilkosti kupok i ob yektiv Isnuye prostij sposib obchislennya yakij z gravciv vigraye i yaki vigrashni kroki maye gravec Klyuch do teoriyi gri ce dvijkova pocifrova suma rozmiriv kup tobto suma dvijkova nehtuyuchi vsima perenosami z odniyeyi cifri v inshu Cya operaciya takozh vidoma yak dodavannya za modulem dva xor V kombinatornij teoriyi igor yiyi zazvichaj nazivayut nim suma yak i v cij statti Nim suma x i y zapisuyetsya x y shob vidrizniti vid zvichajnoyi sumi x y Navedemo priklad obchislen z kupkami rozmiriv 3 4 i 5 Dvijkova Desyatkova 0112 310 Kupa A 1002 410 Kupa B 1012 510 Kupa C 0102 210 Nim suma kup A B i C 3 4 5 2 Rivnoznachna procedura yaku chasto legshe vikonati podumkovo polyagaye v virazhenni rozmiriv kup yak sum stepeniv 2 vikresliti pari odnakovih stepeniv i todi dodati sho zalishilos 3 0 2 1 2 1 Kupa A 4 4 0 0 4 Kupa B 5 4 0 1 4 1 Kupa C 2 2 Te sho zalishilos pislya skorochennya 1 yi i 4 yi V normalnij gri vigrashna strategiya polyagaye v zavershenni kozhnogo kroku z nim sumoyu 0 Ce mozhlivo zavzhdi yaksho nim suma pered krokom bula ne nul Yaksho nim suma nul todi nastupnij gravec prograye yaksho inshij gravec ne pripustitsya pomilki Shob znajti yakij krok zrobiti nehaj X bude nim sumoyu rozmiriv vsih kup Znajti kupu nim suma yakoyi z X mensha nizh rozmir ciyeyi kupi vigrashna strategiya polyagaye v zmensheni rozmiru ciyeyi kupi do nim sumi yiyi potochnogo rozmiru z X U vishenavedenomu prikladi pidrahovuyuchi nim sumu rozmiriv X 3 4 5 2 Nim sumi okremih kup z X A X 3 2 1 Bo 011 010 001 B X 4 2 6 C X 5 2 7 Yedina kupa nim suma yakoyi z X mensha nizh rozmir kupi ce A otzhe vigrashnij krok ce zmenshennya rozmiru A do 1 vidalyayuchi dva ob yekti Yak okremij prostij priklad mozhna rozglyanuti vipadok z dvoma kupami Tut strategiya bude zmenshiti kilkist predmetiv v bilshij kupi do kilkosti predmetiv v menshij Pislya cogo nevazhlivo sho robitime suprotivnik zavzhdi mozhlivo bude zrivnyati kupi znov U razi mizer gri strategiya vidriznyayetsya lishe koli strategiya normalnoyi gri zalishaye lishe kupi rozmiru odin Todi pravilnij krok ce zalishiti neparnu kilkist kup rozmiru odin v normalnij gri pravilno bulo b zalishiti parnu kilkist takih kup LiteraturaBoll U Kokseter G Matematicheskie esse i razvlecheniya Mathematical Recreations and Essays M Mir 1986 S 47 51