Hra Nim a její varianty

Univerzita Karlova v Praze Matematicko-fyzik´aln´ı fakulta

´ ERE ˇ ˇ A ´ PRACE ´ ZAV CN

Kurz Vyuˇ cov´ an´ı vˇ seobecnˇ e vzdˇ el´ avac´ıho pˇ redmˇ etu matematika

Mgr. Krist´yna Kuncov´a Hra Nim a jej´ı varianty

Konzultant z´avˇereˇcn´e pr´ace: RNDr. Anton´ın Slav´ık, Ph.D.

Praha 2014

ˇ Kurz je akreditov´an u MSMT na z´akladˇe § 25 a § 27 z´akona ˇc. 563/2004 Sb., o pedagogick´ ych pracovn´ıc´ıch a o zmˇenˇe nˇekter´ ych z´akon˚ u, a v souladu se z´akonem ˇc. 500/2004 Sb. Pod ˇc. j. 27 655/2012 - 25 - 591.

R´ada bych touto cestou podˇekovala sv´emu vedouc´ımu RNDr. Anton´ınu Slav´ıkovi, Ph.D. za cenn´e pˇripom´ınky a nakaˇzliv´ y optimismus. D´ale bych chtˇela podˇekovat obˇetav´ ym kamar´ad˚ um za proˇcten´ı cel´eho textu a korektury.

Prohlaˇsuji, ˇze jsem tuto z´avˇereˇcnou pr´aci vypracovala samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u, literatury a dalˇs´ıch odborn´ ych zdroj˚ u. Beru na vˇedom´ı, ˇze se na moji pr´aci vztahuj´ı pr´ava a povinnosti vypl´ yvaj´ıc´ı ze z´akona ˇc. 121/2000 Sb., autorsk´eho z´akona v platn´em znˇen´ı, zejm´ena skuteˇcnost, ˇze Univerzita Karlova v Praze m´a pr´avo na uzavˇren´ı licenˇcn´ı smlouvy o uˇzit´ı t´eto pr´ace jako ˇskoln´ıho d´ıla podle §60 odst. 1 autorsk´eho z´akona.

V ............. dne ............

Podpis autora

Obsah ´ Uvod

1

1 Hra Nim 1.1 Pravidla . . . . . . . . . . . . . . 1.2 V´ yhern´ı strategie . . . . . . . . . 1.2.1 Pozice . . . . . . . . . . . 1.2.2 Dvojkov´a soustava . . . . 1.2.3 Nim-souˇcet hry . . . . . . 1.2.4 Nalezen´ı v´ıtˇezn´e strategie

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

2 2 3 4 4 5 6

2 Variace 2.1 Varianty Nimu . . . . . . 2.1.1 Mis`ere Nim . . . . 2.1.2 Moore˚ uv Nim . . . 2.1.3 Maticov´ y Nim . . . 2.1.4 Shannon˚ uv Nim . . 2.1.5 Wythoff˚ uv Nim . . 2.1.6 Tac Tix . . . . . . 2.2 Hry pˇrevoditeln´e na Nim . 2.2.1 Mince na p´asku . . 2.2.2 Stepinova hra . . . 2.2.3 Zelen´ y Hackenbush

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

9 9 9 10 10 11 11 11 12 12 13 13

jako metrick´ y prostor Metrick´e prostory . . . . . . . . . . . . . . . . . . . . . . . . . . . Stromy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Teorie her . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 17 21 24

3 Hra 3.1 3.2 3.3

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

Z´ avˇ er

28

Seznam literatury

30

´ Uvod C´ılem t´eto pr´ace je sezn´amit ˇcten´aˇre s hrou Nim. Jedn´a se o hru pro dva hr´aˇce s jednoduch´ ymi pravidly zaloˇzen´ ymi na odeb´ır´an´ı hrac´ıch kamen˚ u s c´ılem odebrat posledn´ı k´amen. Hra na prvn´ı pohled nep˚ usob´ı sloˇzitˇe, v´ yhern´ı strategie byla pops´ana jiˇz v roce 1901 Ch. L. Boutonem ([6]), avˇsak je velmi mnohotv´arn´a a lze na jej´ım pˇr´ıkladu elegantnˇe demonstrovat r˚ uzn´e obory matematiky, o coˇz se pokus´ıme v n´asleduj´ıc´ıch kapitol´ach. V prvn´ı ˇc´asti se budeme zab´ yvat hrou Nim v z´akladn´ı verzi, zavedeme pojmy v´ıtˇezn´e strategie a bezpeˇcn´e pozice a na z´avˇer, s malou odboˇckou k bin´arn´ı soustavˇe, sestav´ıme v´ıtˇeznou strategii pr´avˇe pro Nim. Kapitola druh´a se zamˇeˇruje na nˇekter´e varianty Nimu s upraven´ ymi pravidly a zkoum´a existenci strategie za takto upraven´ ych podm´ınek. V dalˇs´ı ˇca´sti se pod´ıv´ame na nˇekter´e hry, kter´e nemaj´ı s odeb´ır´an´ım kamen˚ u nic spoleˇcn´eho a pˇresto je lze vyhr´at stejnou strategi´ı jako Nim. Posledn´ı kapitola je v´ yletem do zemˇe metrick´ ych prostor˚ u a strom˚ u, kter´a nab´ız´ı siln´ y apar´at k pr´aci s nekoneˇcn´ ymi hrami. Aˇc je obecnˇejˇs´ı, na Nim lze tento apar´at snadno aplikovat a ˇcten´aˇri se tak uk´aˇze partie matematiky, kterou s hrami obvykle nespojujeme.

1

Kapitola 1 Hra Nim 1.1

Pravidla

Pˇ r´ıklad 1.1. Alice a Bob hraj´ı n´asleduj´ıc´ı hru. Pˇred sebou maj´ı tˇri hrom´adky po tˇrech, ˇctyˇrech a pˇeti hrac´ıch kamenech. Alice zaˇc´ın´a, pot´e se pravidelnˇe stˇr´ıdaj´ı a odeb´ıraj´ı kameny. Vˇzdy si vyberou hrom´adku a z n´ı vezmou alespoˇ n jeden k´amen, nejv´ yˇse vˇsechny. Ten z nich, kter´ y vezme posledn´ı k´amen, vyhr´al. Jak je moˇzn´e, ˇze Alice pokaˇzd´e vyhraje?

Obr. 1.1: Nim (5 − 4 − 3) Pr´avˇe popsan´a hra je jednou z variant hry Nim. Ta je hrou pro dva hr´aˇce, kteˇr´ı postupnˇe odeb´ıraj´ı kameny z hrom´adek pˇred sebou. Poˇcet hrom´adek ani kamen˚ u v nich nen´ı bl´ıˇze urˇcen, dokonce hrom´adky mohou m´ıt r˚ uzn´ y poˇcet kamen˚ u jako v pˇr´ıkladu v´ yˇse. Hr´aˇc, jenˇz je na tahu, m˚ uˇze odebrat prakticky libovoln´e mnoˇzstv´ı kamen˚ u, ale mus´ı vz´ıt alespoˇ n jeden a vˇsechny kameny mus´ı vz´ıt pouze z jedn´e hrom´adky. Hr´aˇc, kter´ y odebere posledn´ı k´amen, vyhr´al. Pˇ r´ıklad 1.2. Pod´ıvejme se na pˇr´ıklady povolen´ ych tah˚ u. P˚ uvodn´ı situaci, kdy m´ame v hrom´adk´ach 5, 4 a 3 kameny, budeme ve zkratce znaˇcit 5-4-3. Mus´ıme vz´ıt alespoˇ n jeden k´amen a vˇzdy jen z jedn´e hrom´adky. Tedy kdyˇz si vybereme prvn´ı hrom´adku, m˚ uˇzeme vz´ıt jeden, dva, tˇri, ˇctyˇri nebo pˇet kamen˚ u. V´ yslednou situaci pak zap´ıˇseme jako 4-4-3, 3-4-3, 2-4-3, 1-4-3 a 4-3. Cviˇ cen´ı 1.3. M´ame hern´ı situaci 2-2-3. Urˇcete, kter´e z n´asleduj´ıc´ıch tah˚ u jsou povolen´e:

2

(1) 1-2-1

(4) 1-2-2

(2) 2-2

(5) 2-2-2

(3) 1-2-3

(6) 2-3

1.2

V´ yhern´ı strategie

Hry, jako je Nim, se vyznaˇcuj´ı existenc´ı v´ıtˇezn´e strategie. Tak naz´ yv´ame postup, kter´ y bud’ zaˇc´ınaj´ıc´ımu hr´aˇci nebo jeho protihr´aˇci zaruˇc´ı v´ıtˇezstv´ı nez´avisle na taz´ıch protihr´aˇce, pokud jej bude peˇclivˇe dodrˇzovat. Ukaˇzme si dalˇs´ı pˇr´ıklad: Pˇ r´ıklad 1.4. Alice a Bob hraj´ı Nim 2-2, dvˇe hrom´adky o dvou kamenech. Bob zaˇc´ın´a. M˚ uˇze Alice vyhr´at, pˇrestoˇze nezaˇc´ın´a? A jak m´a hr´at, aby vyhr´ala? M˚ uˇze naopak vyhr´at Bob? V´ yˇse uveden´e ot´azky zodpov´ıme, pokud si nakresl´ıme strom t´eto hry, jak´ ysi diagram, kter´ y ukazuje vˇsechny moˇzn´e tahy a situace/pozice, do nichˇz se hr´aˇci mohou v pr˚ ubˇehu hry dostat. Tento strom vid´ıme na obr´azku 3.5. Jen upozorn´ıme, ˇze situace 1 − 2 a 2 − 1 jsou symetrick´e a tedy nen´ı potˇreba je rozeb´ırat zvl´aˇst’, v obr´azku jsou tedy zakresleny jen jednou (pozice [B]).

Obr. 1.2: Strom Nimu (2 − 2) ˇ Rozeberme si jej z pozice Boba (hr´aˇce 1) a Alice (hr´aˇce 2). Cerven´ a koleˇcka ilustruj´ı pozice, jeden ˇra´dek je jedna hrom´adka, ˇcern´e ˇca´ry moˇzn´e tahy. Na pozice budeme odkazovat velk´ ymi p´ısmeny v hranat´ ych z´avork´ach. Bob zaˇc´ın´a se dvˇema hrom´adkami po dvou kamenech [A]. M˚ uˇze vz´ıt jeden k´amen nebo celou jednu hrom´adku a Alice se tak ocitne v pozici 2-1 [B] nebo 2-0 [C]. V druh´em pˇr´ıpadˇe m˚ uˇze Alice vyhr´at - staˇc´ı, kdyˇz vezme zbyl´e kameny [G]. Co v prvn´ım pˇr´ıpadˇe, kdy Alice ˇcel´ı kombinaci 2-1? M˚ uˇze vz´ıt hrom´adku o dvou kamenech, Bob tak bude moci vz´ıt posledn´ı k´amen [F] a vyhr´at. M˚ uˇze vz´ıt i hrom´adku o jednom kameni [D]. Pak ale Bobovi staˇc´ı vz´ıt zbyl´e dva kameny a vyhraje. Zb´ yv´a tedy posledn´ı moˇznost, Alice vezme jeden k´amen tak, aby hra 3

byla ve stavu 1-1 [E]. Bobovi nezbude, neˇz vz´ıt jeden k´amen a na Alici zbude posledn´ı a vyhraje. Jak´ y je z´avˇer? Bob sice zaˇc´ınal, ale at’ hr´al jakkoli, tak pokud Alice neudˇelala chybu, vyhr´ala. Naˇsli jsme tedy v´ıtˇeznou strategii pro Alici - postup, kter´ y j´ı, bude-li dodrˇzov´an, zajist´ı v´ıtˇezstv´ı. Pro Boba naopak v´ıtˇeznou strategii naj´ıt nelze a pokud se Alice bude drˇzet postupu, Bob mus´ı prohr´at.

1.2.1

Pozice

Obdobn´ y hern´ı strom bychom mohli udˇelat pro vˇsechny moˇzn´e v´ ychoz´ı pozice hry a po jejich prozkoum´an´ı bychom zjistili, zda lze naj´ıt v´ıtˇeznou strategii a zda pro zaˇc´ınaj´ıc´ıho nebo pro druh´eho hr´aˇce. Jelikoˇz v´ ychoz´ıch pozic je nekoneˇcn´e mnoˇzstv´ı, mus´ıme zvolit jin´ y postup. Pojd’me se pod´ıvat na jednotliv´e pozice hr´aˇc˚ u bˇehem hry. Bob nemohl vyhr´at, byl tedy na zaˇc´atku v prohr´avaj´ıc´ı pozici 2-2. Stejnˇe tak se v pr˚ ubˇehu hry dostal do pozice, kterou nemohl zvr´atit. Byla to pozice 1-1. Tedy, pozice 1-1 a 2-2 byly pˇredem prohran´e. Naopak Alice, pokud nechybovala, se ocitala jen v pozic´ıch vyhr´avaj´ıc´ıch. Byly to 2-1, 2-0, 1-0. Co maj´ı spoleˇcn´eho pozice 1-1 a 2-2? Kaˇzd´a hrom´adka je tam dvakr´at“. Co ” tˇreba situace 3-3? Aniˇz bychom kreslili strom, je moˇzno nahl´ednout, ˇze i tato situace je prohr´avaj´ıc´ı. Staˇc´ı, kdyˇz bude druh´ y hr´aˇc kop´ırovat tahy toho prvn´ıho. A stejn´e je to u vˇsech symetrick´ ych pozic, napˇr. 5-5, 1-1-2-2, 2-2-3-3-4-4 . . . Jiˇz se pomalu bl´ıˇz´ıme k obecn´e v´ıtˇezn´e strategii pro libovolnou hru Nim. Neˇz si ji vˇsak pop´ıˇseme, budeme muset zav´est nˇekolik pojm˚ u.

1.2.2

Dvojkov´ a soustava

Obvykle zapisujeme ˇc´ısla pomoc´ı des´ıtkov´e soustavy. Bˇeˇznˇe tak pouˇz´ıv´ame ˇ ıslo 256 pak vlastnˇe znamen´a mocniny des´ıtky, asi aniˇz si to uvˇedomujeme. C´ 2 · 100 + 5 · 10 + 6 · 1, ˇc´ıslo 15027 zap´ıˇseme jako 15027 = 1 · 10000 + 5 · 1000 + 0 · 100 + 2 · 10 + 7 · 1 nebo, zaps´ano s mocninami des´ıtky, m´ame 5248 jako 5284 = 5 · 103 + 2 · 102 + 8 · 101 + 4 · 100 . Chceme-li zapsat ˇc´ıslo ve dvojkov´e (bin´arn´ı) soustavˇe, postupujeme analogicky. Jen m´ısto mocnin des´ıtky uˇz´ıv´ame mocniny dvojky a m´ısto ˇc´ıslic 0 − 9 uˇz´ıv´ame ˇc´ıslice 0 a 1. Napˇr´ıklad: 1 = 1 · 20 , 2 = 1 · 21 + 0 · 20 , 5 = 1 · 22 + 0 · 21 + 1 · 20 , 33 = 1 · 25 + 0 · 24 + 0 · 23 + 0 · 22 + 0 · 21 + 1 · 20 4

ˇ ısla ve dvojkov´e soustavˇe budeme zapisovat s 2 v doln´ım indexu, napˇr´ıklad atd. C´ 33 bude 1000012 . V tabulce na obr. 1.3 si m˚ uˇzeme prohl´ednout dvojkov´e z´apisy prvn´ı stovky pˇrirozen´ ych ˇc´ısel.

Obr. 1.3: Pˇrevod ˇc´ısel do bin´arn´ı soustavy V dalˇs´ım textu se n´am bude hodit i n´asleduj´ıc´ı n´ahled. Bin´arn´ım z´apisem ˇc´ısla x budeme rozumˇet koneˇcnou posloupnost xk , xk−1 , . . . x1 , x0 , kde xi ∈ {0, 1} pro i = 0, . . . k, takovou, ˇze pro pˇrevod do des´ıtkov´e soustavy plat´ı: x = xk · 2k + xk−1 · 2k−1 + · · · + x1 · 2 + x0 · 1. ˇ ıslo (xk , xk−1 , . . . x1 , x0 ) budeme nˇekdy zapisovat bez z´avorek a s 2 v doln´ım C´ indexu jako v´ yˇse. Tedy (1011) bude tot´eˇz jako 10112 . Vˇsimnˇeme si, ˇze tato posloupnost nen´ı urˇcena jednoznaˇcnˇe, protoˇze 10012 stejnˇe jako 00010012 je bin´arn´ı z´apis ˇc´ısla 9. Aˇz na tyto 0 na zaˇc´atku je takto zaveden´ y bin´arn´ı rozvoj ˇc´ısla ovˇsem jiˇz jednoznaˇcn´ y. Cviˇ cen´ı 1.5. Naleznˇete dvojkov´ y z´apis ˇc´ısel 10, 17, 31 a 256. Cviˇ cen´ı 1.6. Pˇreved’te do des´ıtkov´e soustavy ˇc´ısla 11112 , 1000012 a 101012 .

1.2.3

Nim-souˇ cet hry

V dalˇs´ıch kroc´ıch budeme potˇrebovat souˇcet dvou ˇc´ısel zapsan´ ych ve dvojkov´e soustavˇe bez pˇrenosu cifry do vyˇsˇs´ıho ˇra´du, takzvan´ y Nim-souˇcet nebo tak´e xor. Ten funguje tak, ˇze proch´az´ıme cifry na odpov´ıdaj´ıc´ıch si pozic´ıch; pokud jsou stejn´e, bude odpov´ıdaj´ıc´ı cifrou ve v´ ysledku jedniˇcka, jinak nula. Napˇr´ıklad 0112 ⊕ 1012 = 1102 . Z´apis ˇc´ısel pod sebou bude jeˇstˇe pˇrehlednˇejˇs´ı, tedy p´ar pˇr´ıklad˚ u: 1112 ⊕0012 1102 M´a-li jedno ˇc´ıslo m´enˇe cifer, dopln´ıme jej na zaˇca´tku nulami: 01102 ⊕10012 11112 5

Pro v´ıce ˇc´ısel je postup obdobn´ y, seˇcteme vˇsechny jedniˇcky na dan´e pozici a je-li jich lich´ y poˇcet, nap´ıˇseme 1, jinak p´ıˇseme 0. 0112 ⊕1012 ⊕1112 ⊕0112 0102 Cviˇ cen´ı 1.7. Najdˇete Nim-souˇcet ˇc´ısel: (1) 1102 ⊕ 100002 (2) 11002 ⊕ 101012 ⊕ 12 (3) 3 ⊕ 4 ⊕ 5 (4) 10 ⊕ 12 ⊕ 13 Pozn´ amka 1.8. Nim-souˇcet je komutativn´ı i asociativn´ı a pro kaˇzd´e ˇc´ıslo s nav´ıc plat´ı, ˇze s ⊕ s = 0.

1.2.4

Nalezen´ı v´ıtˇ ezn´ e strategie

Nyn´ı se jiˇz m˚ uˇzeme pod´ıvat, jak vyhr´at Nim. Mus´ıme zodpovˇedˇet n´asleduj´ıc´ı ot´azky: Existuje takov´a strategie? Pro kter´eho hr´aˇce? A jak pˇresnˇe vypad´a? Zaˇcnˇeme definic´ı. N´aslednˇe se za pomoci nˇekolika tvrzen´ı dobereme k v´ıtˇezn´e strategii. Budeme postupovat jako v ˇcl´anku[6]. Definice 1.9. Bezpeˇcnou pozic´ı budeme naz´ yvat takovou pozici, pˇri n´ıˇz Nimsouˇcet poˇctu kamen˚ u z jednotliv´ ych hrom´adek je roven 0. V opaˇcn´em pˇr´ıpadˇe bude pozice zv´ana nebezpeˇcn´a. Napˇr´ıklad pozice s hrom´adkami 1-4-5 je bezpeˇcn´a, nebot’ 1 ⊕100 ⊕101 000 Podobnˇe jsou bezpeˇcn´e pozice 1-2-3, 1-1-2-2, 3-5-6 nebo 5-8-13. Pozn´ amka 1.10. Vˇsimnˇeme si, ˇze zn´ame-li poˇcty kamen˚ u u dvou ze tˇr´ı hrom´adek (nebo obecnˇeji u vˇsech hrom´adek kromˇe jedn´e), jiˇz m˚ uˇzeme jednoznaˇcnˇe dopoˇc´ıtat poˇcet kamen˚ u v posledn´ı hrom´adce, aby Nim-souˇcet byl nulov´ y. Cviˇ cen´ı 1.11. Urˇcete poˇcet kamen˚ u v posledn´ı hrom´adce, v´ıte-li, ˇze Nim-souˇcet vˇsech hrom´adek je nulov´ y: (1) 1012 , 102 (2) 10, 12, 14 Tvrzen´ı 1.12. Jestliˇze Alice po sv´em tahu zanech´a na stole bezpeˇcnou pozici, Bob zanech´a pozici nebezpeˇcnou, a to at’ bude t´ahnout jakkoli.

6

D˚ ukaz. Na stole leˇz´ı hrom´adky s nulov´ ym Nim-souˇctem a Bob mus´ı ubrat kameny pr´avˇe z jedn´e z nich. At’ uˇz ale vybere kteroukoli hrom´adku, ostatn´ı z˚ ustanou ’ nezmˇenˇeny. Soustˇred me se na nˇe. Tyto hrom´adky (v duchu pozn´amky 1.10) jednoznaˇcnˇe urˇcuj´ı poˇcet kamen˚ u v hrom´adce posledn´ı. A pr´avˇe tento poˇcet na stole zanechala Alice. Pakliˇze Bob tedy odebere byt’ jedin´ y k´amen, coˇz podle pravidel udˇelat mus´ı, z˚ ustane na stole pozice nebezpeˇcn´a. Pˇredchoz´ı zd˚ uvodnˇen´ı bychom mohli zapsat ponˇekud form´alnˇeji, a to n´asleduj´ıc´ım zp˚ usobem [1]. Oznaˇcme x1 , x2 , . . . , xk velikosti hrom´adek po Alicinˇe tahu a y1 , y2 , . . . , yk analogick´e velikosti hrom´adek po tahu Boba. D´ale oznaˇcme Nimsouˇcty s = x1 ⊕ · · · ⊕ xk a t = y1 ⊕ · · · ⊕ yk . Pˇredpokl´adejme, ˇze Bob odebere kameny z j-t´e hrom´adky. Potom plat´ı xi = yi pro i 6= j a xj > yj . Udˇelejme nyn´ı pomocn´ y v´ ypoˇcet: t=0⊕t =s⊕s⊕t = s ⊕ (x1 ⊕ · · · ⊕ xj ) ⊕ (y1 ⊕ · · · ⊕ yj ) = s ⊕ (x1 ⊕ y1 ) ⊕ · · · ⊕ (xj ⊕ yj ) = s ⊕ 0 ⊕ · · · ⊕ (xj ⊕ yj ) ⊕ · · · ⊕ 0 = s ⊕ xj ⊕ y j Tedy t = s + xj + yj . Jelikoˇz Alice zanechala bezpeˇcnou pozici, znamen´a to, ˇze s = 0 a tedy t = xj + yj . Ale jeˇzto xj 6= yj , tak ani t 6= 0 a jsme hotovi. Tvrzen´ı 1.13. Pokud Bob nech´a na stole pozici nebezpeˇcnou, Alice m˚ uˇze sv´ ym tahem zanechat pozici opˇet bezpeˇcnou. D˚ ukaz. Idea (podle [13]). Na stole je nebezpeˇcn´a pozice, coˇz znamen´a, ˇze Nim-souˇcet hrom´adek je nenulov´ y. Jin´ ymi slovy, kdyˇz nap´ıˇseme poˇcty kamen˚ u v jednotliv´ ych hrom´adk´ach pod sebe, v alespoˇ n jednom sloupci bude lich´ y poˇcet jedniˇcek. Je- li takov´ ych sloupc˚ u v´ıc, vybereme ten nejv´ıce vlevo (reprezentuje nejvyˇsˇs´ı mocninu dvojky) a d´ale vybereme jednu hrom´adku, kter´a m´a jedniˇcku pr´avˇe v tomto sloupci. T´ım jsme naˇsli hrom´adku, ze kter´e budeme odeb´ırat kameny. D´ale uˇz je to jednoduch´e. V´ıme, ˇze chceme skonˇcit s nulov´ ym Nim-souˇctem, s ostatn´ımi hrom´adkami neh´ ybeme, a z´aroveˇ n v´ıme, ˇze ostatn´ı hrom´adky jednoznaˇcnˇe urˇcuj´ı kameny v hrom´adce zbyl´e. Zb´ yv´a vyˇreˇsit ot´azku, zda bude takov´ y tah pˇr´ıpustn´ y, totiˇz zda z naˇs´ı vybran´e hrom´adky opravdu odebereme alespoˇ n jeden k´amen. To je ale pravda, protoˇze jsme vyb´ırali sloupec co nejv´ıce vlevo, kde jsme n´aslednˇe museli zmˇenit 1 na 0, aby vyˇsel nulov´ y Nim-souˇcet. T´ım jsme ale dan´e ˇc´ıslo urˇcitˇe zmenˇsili a tah je pˇr´ıpustn´ y. Zapiˇsme pˇredchoz´ı u ´vahy form´alnˇe. Analogicky jako v pˇredchoz´ım tvrzen´ı, oznaˇcme x1 , x2 , . . . xk velikosti hrom´adek po Bobovˇe tahu a y1 , y2 , . . . yk velikosti hrom´adek po tahu Alice. D´ale oznaˇcme Nim-souˇcty s = x1 ⊕ · · · ⊕ xk a t = y1 ⊕ · · · ⊕ yk . Jelikoˇz pozice nen´ı bezpeˇcn´a, tak v´ıme, ˇze s 6= 0 a chceme naj´ıt tah, aby t = 0. Vybereme hrom´adku podle postupu v´ yˇse, tedy poloˇz´ıme d := max{i, si = 1}, m−1 kde s = sm sm−1 . . . s0 , a zafixujeme j tak, ˇze xdj = 1, kde xj = xm · · · x0j . j xj 7

M´ame tedy nalezenou hrom´adku a mus´ıme urˇcit, kolik kamen˚ u z n´ı odebereme. Poloˇz´ıme-li yj := xj ⊕ s, pak xj − yj je to spr´avn´e ˇc´ıslo, protoˇze yj < xj , tedy je to povolen´ y tah a z´aroveˇ n z v´ ypoˇctu t = s ⊕ xj ⊕ y j = s ⊕ xj ⊕ (s ⊕ xj ) =0 vid´ıme, ˇze jsme z´ıskali bezpeˇcnou pozici. V tuto chv´ıli jiˇz m´ame v´ıtˇeznou strategii. Zaˇc´ın´a-li Alice hru s nenulov´ ym Nim-souˇctem, staˇc´ı, kdyˇz po kaˇzd´em sv´em tahu zanech´a souˇcet nulov´ y. Jelikoˇz v kaˇzd´em kole kles´a poˇcet kamen˚ u na stole, dˇr´ıve ˇci pozdˇeji dojde k situaci 0-00. . . (povˇsimnˇeme si, ˇze je bezpeˇcn´a) a Alice vyhraje. Pokud Alice zaˇc´ın´a hru s nulov´ ym souˇctem, zv´ıtˇez´ı naopak Bob pˇresnˇe stejn´ ym postupem. Pˇ r´ıklad 1.14. ([6]). 1-2-3 1-4-5 1-6-7 1-8-9 1-10-11 1-12-13 1-14-15

Seznam bezpeˇcn´ ych pozic pro 3 hrom´adky o nejv´ yˇse 15 kamenech 2-4-6 2-5-7 2-8-10 2-9-11 2-12-14 2-13-15

3-4-7 3-5-6 3-8-11 3-9-10 3-12-15 3-13-14

4-8-12 4-9-13 4-10-14 4-11-15

8

5-8-13 5-9-12 5-10-15 5-11-14

6-8-14 6-9-15 6-10-12 6-11-13

7-8-15 7-9-14 7-10-13 7-11-12

Kapitola 2 Variace Z´akladn´ı variantu hry Nim vˇcetnˇe v´ıtˇezn´e strategie jsme jiˇz popsali. V t´eto kapitole budeme pokraˇcovat s jej´ımi variacemi a nav´aˇzeme s hrami, kter´e jako Nim na prvn´ı pohled nevypadaj´ı, ale pˇri vhodn´em n´ahledu u nich lze pouˇz´ıt stejnou v´ıtˇeznou strategii jako u Nimu.

2.1

Varianty Nimu

Zn´ame-li z´akladn´ı Nim a rozum´ıme-li v´ıtˇezn´e strategii, zaˇcne se vkr´adat ot´azka, zda lze pravidla Nimu nˇejak zmˇenit a s jak´ ymi d˚ usledky pro existenci v´ıtˇezn´e strategie. Setk´av´ame se pak s tzv. betlovou hrou nebo s moˇznost´ı odeb´ırat kameny z v´ıce hrom´adek z´aroveˇ n. I u tˇechto her pak hled´ame v´ıtˇeznou strategii. Ta stejnˇe jako u Nimu sest´av´a z hled´an´ı bezpeˇcn´ ych (v´ yhern´ıch) pozic, omez´ıme se tedy v dalˇs´ım textu na popis tˇechto pozic. V´ yhern´ı strategie se pak konstruuje analogicky z´akladn´ı variantˇe.

2.1.1

Mis` ere Nim

Zat´ımco v origin´aln´ı hˇre Nim bylo c´ılem vz´ıt posledn´ı k´amen, v tzv. betlov´e hˇre (zn´am´e t´eˇz jako mis`ere Nim) je c´ılem posledn´ı k´amen nevz´ıt a donutit k tomu protihr´aˇce. Existuje v´ıtˇezn´a strategie i tady? Ano, existuje, v jiˇz citovan´em ˇcl´anku [6] najdeme strategii nejen pro p˚ uvodn´ı Nim, ale i pro betlovou variantu. Hrajeme stejnˇe jako v z´akladn´ı variantˇe aˇz do okamˇziku, kdyˇz zb´ yv´a pouze jedna hrom´adka s v´ıce neˇz jedn´ım kamenem (napˇr. 2-1-1 nebo 14-1-1-1). V p˚ uvodn´ı strategii bychom vzali bud’ vˇsechny kameny z t´eto hrom´adky (a nechali 0) nebo vˇsechny aˇz na jeden (nechali 1) tak, aby zbyl sud´ y poˇcet hrom´adek (u pˇr´ıklad˚ u v´ yˇse tedy 1-1 nebo 1-1-1-1). U mis`ere hry staˇc´ı zvolit opaˇcnˇe (0 m´ısto 1 a naopak) a nechat lich´ y poˇcet hrom´adek (tedy 1-1-1 a 1-1-1). Z n´avodu v´ yˇse tedy plyne, ˇze i tady v´ıtˇezn´a strategie existuje, a to pro stejn´eho ˇ aˇr si na z´akladˇe tohoto n´avodu m˚ hr´aˇce jako u origin´aln´ı varianty. Cten´ uˇze zkusit rozmyslet, jak vypad´a v´ıtˇezn´a strategie pro mis´ere Nim; podrobnosti lze naj´ıt v [6]. Cviˇ cen´ı 2.1. Projdˇete si znovu strom hry 2-2 na obr. 2.1 a vyzkouˇsejte si v´ıtˇeznou strategii pro betlovou hru. 9

Obr. 2.1: Mis`ere Nim

2.1.2

Moore˚ uv Nim

Pˇri Mooreovˇe Nimu [7], zvan´em tak´e Nimk , mus´ı hr´aˇc ve sv´em tahu vz´ıt alespoˇ n jeden k´amen. Pak uˇz je omezen jedin´ ym pravidlem, sm´ı odeb´ırat kameny z maxim´alnˇe k hrom´adek. Zda bude br´at ze vˇsech hrom´adek stejnˇe, z kaˇzd´e jinak nebo z nˇekter´ ych v˚ ubec, uˇz je pak jen na nˇem. Vyhraje ten hr´aˇc, kter´ y vezme posledn´ı k´amen. Je zjevn´e, ˇze zbude-li k nebo m´enˇe hrom´adek, jedn´a se o pozici v´ yhern´ı, staˇc´ı vz´ıt vˇsechny zb´ yvaj´ıc´ı kameny. Abychom vyhr´ali, mus´ıme naj´ıt bezpeˇcn´e kombinace. Pˇredpokl´adejme tedy, ˇze m´ame n hrom´adek o x1 , x2 , . . . , xn kamenech. Kaˇzdou hrom´adku m˚ uˇzeme opˇet zapsat v bin´arn´ı soustavˇe, tedy xi = x0i + x1i · 21 + x2i · 22 + x3i · 23 + · · · Kdyˇz poˇcty kamen˚ u v dvojkov´e soustavˇe zap´ıˇseme pod sebe, tak bezpeˇcn´a pozice bude takov´a, kter´a m´a v kaˇzd´em sloupeˇcku poˇcet jedniˇcek dˇeliteln´ y k + 1, neboli n X

xji ≡ 0

mod (k + 1),

j = 0, 1, 2, . . .

i=1

Aplikujeme-li toto pravidlo na z´akladn´ı Nim - Nim1 , zjist´ıme, ˇze odpov´ıd´a pravidlu, kdy poˇcet jedniˇcek ve sloupci mus´ı b´ yt sud´ y. Cviˇ cen´ı 2.2. Jak m´ame t´ahnout, abychom dos´ahli bezpeˇcn´e pozice ve hˇre Nim5 , jsme-li v situaci 15 − 8 − 3 − 1?

2.1.3

Maticov´ y Nim

Matrix Nim[10] nebo tak´e Nimn spoˇc´ıv´a v rozm´ıstˇen´ı hrom´adek do obd´eln´ıkov´eho sch´ematu o m ˇra´dc´ıch a n sloupc´ıch. Lze si jej pˇredstavit jako rozm´ıstˇen´ı sloupeˇck˚ u s mincemi na ˇsachovnici, kter´a m´a m ˇra´dk˚ u a n sloupc˚ u. Hr´aˇc pak ve sv´em tahu sm´ı vz´ıt libovoln´e (nenulov´e) mnoˇzstv´ı kamen˚ u z libovoln´eho poˇctu 10

hrom´adek bud’ tak, ˇze hrom´adky budou ve stejn´em ˇra´dku, nebo tak, ˇze z˚ ustane jeden sloupeˇcek v obd´eln´ıku nedotˇcen. Bezpeˇcn´a pozice splˇ nuje dvˇe podm´ınky. Zaprv´e, pro kaˇzd´ y sloupeˇcek existuje jin´ y sloupeˇcek, kter´ y m´a stejn´ y poˇcet kamen˚ u. A zadruh´e, vezmeme-li nejmenˇs´ı hrom´adku z kaˇzd´eho ˇra´dku, tak tyto hrom´adky d´avaj´ı bezpeˇcnou pozici v bˇeˇzn´em Nimu. Jen doplˇ nme, ˇze pro Nim1 z´ısk´ame obvykl´ y Nim.

2.1.4

Shannon˚ uv Nim

Vrat’me se k z´akladn´ı variantˇe Nimu. Sm´ıme vz´ıt libovoln´ y poˇcet kamen˚ u z pr´avˇe jedn´e hrom´adky. Pˇrid´ame-li nav´ıc podm´ınku, ˇze tento poˇcet mus´ı b´ yt prvoˇc´ıslo nebo jedniˇcka, z´ısk´ame Shannon˚ uv Nim[7]. Zat´ımco v bˇeˇzn´em Nimu je bezpeˇcn´a pozice takov´a, kter´a m´a sud´ y poˇcet jedniˇcek v kaˇzd´em sloupci bin´arn´ıch rozvoj˚ u, u Shannonova Nimu jsou bezpeˇcn´e ty pozice, kter´e maj´ı sud´ y poˇcet jedniˇcek v posledn´ıch dvou sloupc´ıch. Napˇr´ıklad situace 11 − 13 − 14 je bezpeˇcn´a, aˇc v bˇeˇzn´em Nimu tomu tak nen´ı, nebot’ 10112 ⊕11012 ⊕11102 10002 .

2.1.5

Wythoff˚ uv Nim

V tomto Nimu zaˇc´ın´ame se dvˇema hrom´adkami[7]. Hr´aˇc odeb´ır´a kameny bud’ z jedn´e hrom´adky jako v klasick´em Nimu, nebo z hrom´adek obou. V tom pˇr´ıpadˇe ale bere z obou stejn´e mnoˇzstv´ı kamen˚ u. Opˇet v´ıtˇez´ı ten hr´aˇc, kter´ y odebere posledn´ı k´amen. Bezpeˇcn´e pozice jsou tzv. Wythoffovy dvojice: (1; 2), (3; 5), (4; 7), (6; 10), (8; 13), (9; 15). . . n-t´a dvojice odpov´ıd´a vzorci (bnϕc; bnϕ2 c), √ kde ϕ = (1 + 5)/2 (coˇz je mimochodem hodnota zlat´eho ˇrezu) a kde bxc znaˇc´ı doln´ı celou ˇc´ast ˇc´ısla x.

2.1.6

Tac Tix

A na z´avˇer uved’me jednu hru bez zn´am´e v´ıtˇezn´e strategie. Tac Tix [9] je podobn´ y maticov´emu Nimu. Tak´e zaˇc´ın´ame s polem m × n kamen˚ u (na kaˇzd´em poli pr´avˇe jeden k´amen). Hr´aˇc si vybere bud’ ˇra´dek nebo sloupec, z nˇej pak odebere libovoln´e mnoˇzstv´ı kamen˚ u s podm´ınkou, ˇze kameny budou sousedit. Hra se hraje v betlov´e verzi, tedy ten z nich, kter´ y odebere posledn´ı k´amen, prohr´al. Kdyby tomu bylo naopak, staˇcilo by opakovat tahy soupeˇre podle stˇredov´e symetrie. Pokud by vzal cel´ y horn´ı ˇr´adek, vzali bychom spodn´ı, pokud by vzal rohov´ y k´amen, vzali bychom roh naproti atd.

11

Obr. 2.2: Rozehran´ y Tac Tix

2.2

Hry pˇ revoditeln´ e na Nim

Dosud jsme hledali v´ıtˇeznou strategii her, kter´e z´akladn´ı Nim m´ırnˇe upravovaly. V n´asleduj´ıc´ı ˇc´asti se budeme zab´ yvat naopak hrami, kter´e s Nimem nemaj´ı na prvn´ı pohled nic spoleˇcn´eho. Naˇs´ım c´ılem bude pˇrev´est je na Nim, coˇz n´am zajist´ı existenci a pˇresn´ y popis v´ıtˇezn´e strategie. Jej´ı konkr´etn´ı aplikaci opˇet nech´ame na ˇcten´aˇri.

2.2.1

Mince na p´ asku

Na obr´azku 2.3 je zn´azornˇena hra s mincemi [7]. Leˇz´ı na (koneˇcn´em) p´asku s pol´ıˇcky a naˇs´ım c´ılem je dostat vˇsechny mince doleva na zaˇca´tek p´asku, tedy v tomto pˇr´ıpadˇe na prvn´ıch devˇet pol´ıˇcek. Hr´aˇc sm´ı h´ ybat vˇzdy jen s jednou minc´ı, sm´ı ji posouvat vlevo o libovoln´ y poˇcet pol´ıˇcek, ale nesm´ı mince pˇreskakovat, ani je stavˇet na sebe. Hr´aˇc, kter´ y sv´ ym tahem dos´ahl c´ılov´e pozice, vyhr´al.

Obr. 2.3: Mince na p´asku Hrom´adky Nimu jsou tu schov´any v mezer´ach mezi mincemi. Zaˇcnˇeme od prvn´ı mince u ´plnˇe vpravo, pak n´as zaj´ım´a vzd´alenost prvn´ı a druh´e, tˇret´ı a ˇctvrt´e, p´at´e a ˇsest´e, sedm´e a osm´e mince. Je-li minc´ı lich´ y poˇcet jako zde, jeˇstˇe pˇrid´ame vzd´alenost posledn´ı mince a poˇca´tku p´asku. Tyto vzd´alenosti pak interpretujeme jako velikosti hrom´adek v Nimu. V tomto konkr´etn´ım pˇr´ıpadˇe jsme tedy z´ıskali Nim 3 − 4 − 2 − 0 − 1. C´ılov´a pozice odpov´ıd´a Nimu 0 − 0 − 0 − 0 − 0. Povˇsimnˇeme si, ˇze pohyby minc´ı mohou mezery (tedy hrom´adky) zmenˇsovat i zvˇetˇsovat, ˇc´ımˇz se hra liˇs´ı od Nimu. Protoˇze n´as ale zaj´ımaj´ı jen lich´e mezery 12

(mezi prvn´ı a druhou, tˇret´ı a ˇctvrtou minc´ı atd.), tak lze kaˇzd´e takov´e zvˇetˇsen´ı n´aslednˇe opˇet zmenˇsit. Kupˇr´ıkladu, pokud by tedy soupeˇr t´ahl ˇctvrtou minc´ı zleva, zvˇetˇsil by mezeru ze 2 pol´ıˇcek na 3, a z´ıskali bychom pozici 3 − 4 − 3 − 0 − 1. Toto lze ale spravit, pokud bychom pak posunuli o jedno pol´ıˇcko doleva p´atou minci zleva, z´ıskali bychom p˚ uvodn´ı 3 − 4 − 2 − 0 − 1. Zvˇetˇsov´an´ı hrom´adek“ lze ” nav´ıc udˇelat pouze koneˇcnˇekr´at, ˇc´ımˇz dˇr´ıve ˇci pozdˇeji dojdeme k bˇeˇzn´emu Nimu.

2.2.2

Stepinova hra

N´asleduj´ıc´ı hra je podobn´a pˇredchoz´ı [7]. Opˇet m´ame p´asek s mincemi, kter´e posouv´ame doleva. Tentokr´at je ale m´ısto prvn´ıho pol´ıˇcka v´aˇcek na mince, do nˇejˇz mince padaj´ı. Druhou zmˇenou je, ˇze nehrajeme jen s mincemi, ale nav´ıc je mezi nimi jedna zlat´a medaile. Ten hr´aˇc, kter´ y ji dostane do v´aˇcku, vyhr´al.

Obr. 2.4: Stepinova hra Nim budeme hledat analogicky jako v´ yˇse, zaˇcneme od mince u ´plnˇe vpravo a budeme zjiˇst’ovat vzd´alenosti mezi p´ary minc´ı (opˇet prvn´ı a druh´a, tˇret´ı a ˇctvrt´a atd.). Na medaili se budeme d´ıvat stejnˇe jako na minci. M´ame-li lich´ y poˇcet minc´ı a medaile tvoˇr´ı levou“ ˇca´st p´aru, pˇrid´ame jeˇstˇe jednu hrom´adku odpov´ıdaj´ıc´ı ” poˇctu pol´ıˇcek mezi minc´ı a s´aˇckem. V pˇr´ıkladu na obr´azku 2.4 je tedy vlastnˇe Nim 7 − 1 − 4 − 3.

2.2.3

Zelen´ y Hackenbush

Oproti pˇredchoz´ım hr´am Hackenbush[8],[2] nepracuje s mincemi nebo kameny, ale s obr´azky. Obr´azky jsou to speci´aln´ı, sest´av´aj´ı z uzl˚ u (ˇcern´e teˇcky) a z hran, ˇcar mezi nimi. Kaˇzd´a hrana mus´ı spojovat 2 uzly nebo tvoˇrit smyˇcku u jednoho uzlu (napˇr. jablka na stromˇe na obr´azku 2.5). Dva uzly mohou b´ yt spojeny i v´ıce hranami (lampa vpravo, tamt´eˇz). Podm´ınkou tak´e je, ˇze vˇsechny uzly mus´ı b´ yt pomoc´ı hran spojeny se zem´ı. Rozd´ıl ilustruje obr´azek 2.6. Domek vlevo splˇ nuje podm´ınky, protoˇze okno je pˇripojeno k domeˇcku, obr´azek vpravo uˇz nikoli. Toto pravidlo lze interpretovat i za pomoci gravitace, okno by prostˇe spadlo a rozbilo se (a zmizelo). Hra je n´aslednˇe zaloˇzena na stˇr´ıdav´em odeb´ır´an´ı hran z obr´azku. Pokud se odebr´an´ım hrany poruˇs´ı spojen´ı nˇejak´e ˇca´sti obr´azku se zem´ı, zmiz´ı spolu s hranou i tato ˇca´st. Odebereme-li tedy hranu B z obr´azku 2.5, zmiz´ı i cel´a jabloˇ n. V´ıtˇez´ı ten hr´aˇc, kter´ y takto odebere posledn´ı hranu. Podobnost s Nimem najdeme, nahrad´ıme-li hrany kameny. Hrom´adky jsou pak tvoˇreny souvisl´ ymi objekty. V naˇsem pˇr´ıpadˇe tedy jedna hrom´adka odpov´ıd´a jabloni, druh´a lampˇe, tˇret´ı dveˇr´ım, ˇctvrt´a v´aze a p´at´a domku.

13

Obr. 2.5: Obr´azek ke hˇre Hackenbush

Obr. 2.6: Vhodn´ y (vlevo) a nevhodn´ y (vpravo) obr´azek ke hˇre Hackenbush

14

Bohuˇzel nejde nahrazovat jednu hranu za jeden k´amen, ale je tˇreba dodrˇzovat jist´a pravidla. Pod´ıvejme se na nˇe v nˇekolika kroc´ıch. (1) V pˇr´ıpadˇe, ˇze obr´azek neobsahuje cykly (kter´e m´a kupˇr´ıkladu kom´ın na obr´azku 2.5) ani vˇetven´ı (jako m´a pavouk v oknˇe), prostˇe spoˇc´ıt´ame hrany. Smyˇcky na konci ˇretˇezce obsahovat m˚ uˇze, ty prostˇe nahrad´ıme jedinou vˇetv´ı (viz obr´azek 2.7).

Obr. 2.7: Pˇrevod na Nim, obr´azek bez cykl˚ u a vˇetven´ı (2) Nyn´ı se soustˇred’me na vˇetven´ı (st´ale jeˇstˇe bez cykl˚ u). Pod´ıvejme se na kaˇzd´ y uzel, ve kter´em doch´az´ı k vˇetven´ı. Vezmˇeme d´elku jednotliv´ ych vˇetv´ı a udˇelejme jejich Nim-souˇcet. Trs pak nahrad´ıme jedinou vˇetv´ı o d´elce tohoto Nim-souˇctu. Pˇr´ıklad nab´ız´ı obr´azek 2.8. Postup opakujeme, dokud nez´ısk´ame jedinou vˇetev, kterou jiˇz na Nim pˇrev´est um´ıme.

Obr. 2.8: Vˇetven´ı (3) Zb´ yv´a n´am vypoˇr´adat se s cykly. Cykly uprav´ıme na vˇetve n´asledovnˇe. Uzly cyklu st´ahneme do jedin´eho uzlu. Z hran se tak stanou smyˇcky a obr´azek bude pˇripom´ınat kytiˇcku s l´ısteˇcky. Smyˇcky se n´aslednˇe stanou 15

hranami a z kytiˇcky vznikne trs vˇetv´ı, kter´ y uprav´ıme dle pˇredchoz´ıho bodu (obr´azek 2.9).

Obr. 2.9: Cykly Posledn´ım krokem je u ´prava obr´azk˚ u, kter´e se dot´ ykaj´ı zemˇe na v´ıce m´ıstech. V prvn´ı f´azi st´ahneme tyto body do jednoho m´ısta (Obr. 2.10). T´ım z´ısk´ame cykly, kter´e pˇrevedeme na smyˇcky a ty na vˇetve, ˇc´ımˇz jsme hotovi. T´ım, ˇze jsme seskupili body na zemi do jednoho, jsme sice zmˇenili obr´azek, ale Nim-souˇcet hry z˚ ustane neovlivnˇen, tedy je tato u ´prava zcela korektn´ı. Z´aroveˇ n jsme t´ım popsali vˇsechny moˇzn´e pˇr´ıpady a hra je pˇrevedena.

Obr. 2.10: Cykly pokraˇcov´an´ı

16

Kapitola 3 Hra jako metrick´ y prostor V prvn´ı kapitole jsme popsali v´ıtˇeznou strategii Nimu. Dok´azat, ˇze nˇejak´a hra m´a v´ıtˇeznou strategii, lze i nepˇr´ımo, aniˇz bychom tuto strategii zkonstruovali. C´ılem t´eto kapitoly bude uk´azat, ˇze Nim m´a v´ıtˇeznou strategii, a to jin´ ymi prostˇredky neˇz v kapitole prvn´ı. Naˇs´ım n´astrojem bude Galeova-Stewartova vˇeta. Abychom ji mohli zformulovat a dok´azat, mus´ıme zav´est z´aklady teorie metrick´ ych prostor˚ u a jejich konkr´etn´ı aplikace na stromech.

3.1

Metrick´ e prostory

N´asleduj´ıc´ı definice se snaˇz´ı zobecnit pojem vzd´alenosti. Jako pˇr´ıklad si ˇ e republice. Chtˇeli bychom umˇet pˇredstavme vˇsechna mˇesta a vesnice v Cesk´ urˇcit, jak jsou od sebe daleko. Nab´ız´ı se r˚ uzn´e moˇznosti, nˇekter´e z tˇechto vzd´alenost´ı“ jsou ovˇsem vhodnˇejˇs´ı ” neˇz jin´e. Napˇr´ıklad cena vlakov´e j´ızdenky by selhala u vesnic, do kter´ ych nevedou koleje. Doba j´ızdy na kole d´a jin´e v´ ysledky pro cestu tam a pro cestu zp´atky. Na definici metrick´eho prostoru klademe tedy jist´e n´aroky. Vzd´alenost, neboli metrika, mus´ı b´ yt dobˇre definov´ana pro vˇsechny prvky (pˇr´ıklad s kolejemi), mus´ı b´ yt symetrick´a (pˇr´ıklad s kolem), splˇ novat takzvanou troj´ uheln´ıkovou nerovnost (cesta by mˇela b´ yt kratˇs´ı, kdyˇz pojedeme pˇr´ımo, neˇz kdyˇz se budeme stavovat u babiˇcky). D´ale poˇzadujeme, aby vzd´alenost z mˇesta x do mˇesta x byla 0. A aby to byla 0 pr´avˇe jen tehdy. (Aby se nestalo, ˇze se do nˇekter´ ych mˇest lze teleportovat v nulov´em ˇcase.) Definice 3.1. Necht’ X je mnoˇzina a ρ : X ×X → [0; ∞) je funkce. Dvojici (X, ρ) budeme naz´ yva metrick´ym prostorem, jestliˇze pro ∀x, y, z ∈ X plat´ı n´asleduj´ıc´ı podm´ınky: (1) ρ(x, y) = 0 ⇔ x = y. (Identita) (2) ρ(x, y) = ρ(y, x). (Symetrie) (3) ρ(x, z) ≤ ρ(x, y) + ρ(x, z). (Troj´ uheln´ıkov´a nerovnost) Funkci ρ budeme naz´ yvat metrikou. Nˇekolik pˇr´ıklad˚ u metrick´ ych prostor˚ u:

17

ˇ metrikou je vzd´alenost Pˇ r´ıklady 3.2. (1) Mnoˇzina vˇsech vlakov´ ych n´adraˇz´ı v CR, po kolej´ıch“. ” (2) Mnoˇzina re´aln´ ych ˇc´ısel s metrikou danou absolutn´ı hodnotou ρ(x, y) = |x − y|. (3) Jednotkov´a kruˇznice v R2 , tedy kruˇznice s polomˇerem 1, metrikou je vzd´alenost bod˚ u po kruˇznici“. Dva protilehl´e body tedy maj´ı vzd´alenost π. ” (4) Prostor Rn , n ∈ N, s metrikou definovanou jako (a) ρ1 (x, y) := |x1 − y1 | + |x2 − y2 | + · · · + |xn − yn |, p (b) ρ2 (x, y) := |x1 − y1 |2 + |x2 − y2 |2 + · · · + |xn − yn |2 , p (c) ρm (x, y) := m |x1 − y1 |m + |x2 − y2 |m + · · · + |xn − yn |m , m ∈ N, (d) ρ∞ (x, y) := maxi=1,...,n {|xi − yi |}. (5) Takzvan´a diskr´etn´ı metrika, definovan´a na libovoln´e mnoˇzinˇe, kde vˇsechny body jsou od sebe vzd´aleny 1, jen vzd´alenost bodu od sebe sam´eho je 0, neboli ρ(x, x) = 0 a ρ(x, y) = 1, kde x 6= y. Cviˇ cen´ı 3.3. Urˇcete, zda jsou n´asleduj´ıc´ı struktury metrick´ ym prostorem. (1) Prostor R2 s funkc´ı ρ(x, y) = ρ2 (x, x0 ) + ρ2 (x0 , y), kde x0 znaˇc´ı poˇca´tek (0, 0). Jedn´a se tedy o strukturu, kde pˇri mˇeˇren´ı vzd´alenosti dvou bod˚ u mus´ıme vˇzdy proj´ıt poˇca´tkem. (2) Mnoˇzina X = {x, y, z} o tˇrech prvc´ıch se vzd´alenost´ı pˇredepsanou funkc´ı ρ(x, y) = 1, ρ(y, z) = 6 a ρ(z, x) = 20. (3) Mnoˇzina R3 s funkc´ı ρ(x, y) = |x1 − y1 |. (4) Libovoln´a mnoˇzina X s funkc´ı ρ(x, y) = 0. (5) Mnoˇzina R s funkc´ı ρ(x, y) = | arctan(x) − arctan(y)|. Pokud jiˇz m´ame metrick´ y prostor, lze s metrikou d´ale pracovat a opˇet dostaneme metrick´ y prostor: Cviˇ cen´ı 3.4. Ukaˇzte, ˇze jsou-li ρ a ρ0 metriky na mnoˇzinˇe X, tak i n´asleduj´ıc´ı funkce σ tvoˇr´ı metriku na X: (1) σ(x, y) = min{1; ρ(x, y)},

(3) σ(x, y) = ρ(x, y) + ρ0 (x, y),

(2) σ(x, y) = ln(1 + ρ(x, y)),

(4) σ(x, y) = max{ρ(x, y); ρ0 (x, y)}.

Kdyˇz uˇz m´ame vzd´alenost, m˚ uˇzeme zobecnit i nˇekter´e dalˇs´ı pojmy. Napˇr´ıklad kruh v rovinˇe je definov´an jako mnoˇzina vˇsech bod˚ u, jejichˇz vzd´alenost (metrika) od stˇredu S je menˇs´ı nebo rovna polomˇeru r > 0. Analogicky je definov´ana koule. Definice 3.5. Otevˇrenou koul´ı se stˇredem x ∈ X a polomˇerem r > 0 rozum´ıme mnoˇzinu B(x, r) = {y ∈ X; ρ(x, y) < r}. 18

Pˇ r´ıklady 3.6. (1) V prostoru R3 s metrikou ρ2 , takzvanou eukleidovskou, vypad´a koule B(0, 1) tak, jak jsme zvykl´ı. (2) Na pˇr´ımce, tedy v R1 s metrikou ρ1 , z´ısk´ame otevˇren´ y interval (−1, 1). (3) V prostoru R2 bude koule zaj´ımavˇejˇs´ı. V metrice ρ2 dostaneme kruh o stˇredu 0 a polomˇeru 1. Ale s metrikou ρ∞ dostaneme ˇctverec a ρ1 ˇctverec ” postaven´ y na ˇspiˇcku“. Ilustruje obr´azek 3.1.

Obr. 3.1: Koule v R2 v metrik´ach ρ2 , ρ∞ , ρ1 (4) V diskr´etn´ı metrice z´avis´ı koule na polomˇeru. Je-li r ≤ 1, splyne koule se sv´ ym stˇredem: B(x, r) = {x}. Pro r > 1 se koule bude rovnat cel´emu prostoru: B(x, r) = X. M´ame-li pojem (otevˇren´e) koule, m˚ uˇzeme zav´est koncept otevˇren´ ych a uzavˇren´ ych mnoˇzin. Stejnˇe jako koule zobecˇ nuje pojem kruhu, tak otevˇren´a (resp. uzavˇren´a) mnoˇzina nˇejak´ ym zp˚ usobem zobecˇ nuje pojem otevˇren´eho (resp. uzavˇren´eho) intervalu na re´aln´e ose. ˇ Definice 3.7. Rekneme, ˇze podmnoˇzina G metrick´eho prostoru X je otevˇren´ a, jestliˇze pro kaˇzd´e x ∈ G existuje ε > 0 tak, ˇze B(x, ε) ⊂ G. D´ale ˇrekneme, ˇze podmnoˇzina F metrick´eho prostoru X je uzavˇren´a, jestliˇze X \ F je otevˇren´a. Pˇ r´ıklady 3.8. (1) V kaˇzd´em metrick´em prostoru (X, ρ) plat´ı, ˇze cel´ y prostor X a pr´azdn´a mnoˇzina ∅ jsou uzavˇren´e i otevˇren´e z´aroveˇ n. (2) V metrick´em prostoru (R, ρ1 ), tedy na re´aln´e ose s absolutn´ı hodnotou, je uzavˇrenou mnoˇzinou tˇreba bod {2}, uzavˇren´ y interval [−3; 1] ale tak´e interval [11; ∞). Otevˇrenou mnoˇzinou pak je otevˇren´ y interval (−5; −3), (−∞, e) nebo sjednocen´ı interval˚ u (2; π) ∪ (11; 18, 7). (3) V rovinˇe, tedy v metrick´em prostoru (R2 , ρ2 ) je otevˇren´a mnoˇzina napˇr´ıklad kruh o stˇredu [0, 0] a polomˇeru 2, ovˇsem bez hraniˇcn´ı kruˇznice. Kruh s hraniˇcn´ı kruˇznic´ı je mnoˇzina uzavˇren´a. Stejnˇe tak bˇeˇzn´e geometrick´e objekty (ˇctverec, lichobˇeˇzn´ık, deltoid) bez hranice jsou otevˇren´e a s hranic´ı uzavˇren´e.

19

Obr. 3.2: Otevˇren´e (horn´ı ˇr´adek) a uzavˇren´e (doln´ı ˇr´adek) mnoˇziny v R2 (4) V diskr´etn´ım metrick´em prostoru je otevˇren´a i uzavˇren´a kaˇzd´a jeho podmnoˇzina. (5) V metrick´em prostoru X = (0, 1] ∪ [2, 3) s metrikou ρ1 je mnoˇzina (0, 1] otevˇren´a i uzavˇren´a z´aroveˇ n. Mnoˇzina [2, 3) zrovna tak. Povˇsimnˇeme si, ˇze definice otevˇren´e i uzavˇren´e mnoˇziny z´avis´ı na metrick´em prostoru, ve kter´em se pohybujeme. Cviˇ cen´ı 3.9. Urˇcete, zda je interval (0, 1) otevˇren´a ˇci uzavˇren´a mnoˇzin v metrick´em prostoru (X, ρ), jestliˇze (1) X = (0, 1), ρ = ρ1 ,

(3) X = [0, 1] s diskr´etn´ı metrikou,

(2) X = R, ρ = ρ1 ,

(4) X = (0, 1) ∪ (3, 4), ρ = 3ρ1 .

Uzavˇrenou mnoˇzinu lze charakterizovat i za pomoci kovnergence posloupnosti [14]. ˇ Definice 3.10. Necht’ x je prvkem metrick´eho prostoru X. Rekneme, ˇze posloup∞ nost (xn )n=1 ⊂ X konverguje k x, jestliˇze pro kaˇzd´e ε > 0 existuje n0 ∈ N takov´e, ˇze pro kaˇzd´e n ≥ n0 plat´ı, ˇze ρ(x, xn ) < ε. Znaˇc´ıme xn → x. Vˇ eta 3.11. V metrick´em prostoru pak plat´ı, ˇze podmnoˇzina F metrick´eho prostoru je uzavˇren´a pr´avˇe tehdy, jestliˇze pro kaˇzdou posloupnost (xn )∞ n=1 ⊂ F , xn → x, plat´ı x ∈ F . Pˇ r´ıklady 3.12. (1) V metrick´em prostoru [0, 1] nen´ı mnoˇzina {1/n, n ∈ N} otevˇren´a ani uzavˇren´a. 20

(2) Racion´aln´ı ˇc´ısla Q nejsou v metrick´em prostoru (R, ρ1 ) otevˇren´a ani uzavˇren´a mnoˇzina. Tedy ani iracion´aln´ı ˇc´ısla R \ Q nejsou ani otevˇren´a ani uzavˇren´a. Cviˇ cen´ı 3.13. Urˇcete, zda jsou dan´e mnoˇziny otevˇren´e ˇci uzavˇren´e v dan´em metrick´em prostoru. (1) Mnoˇzina N vˇsech pˇrirozen´ ych ˇc´ısel v (R, ρ1 ). (2) Mnoˇzina M = {(x, y) ∈ R2 ; x < y} v prostoru (R2 , ρ2 ). (3) Osa x v prostoru (R3 , ρ2 ). (4) Mnoˇzina M = {(x, y) ∈ R2 ; x 6= 0, y = 1/x} v prostoru (R2 , ρ2 ). (5) Mnoˇzina M = {(x, y) ∈ R2 ; x2 + y 2 /4 = 1} v prostoru (R2 , ρ2 ). Neˇz pˇrikroˇc´ıme k dalˇs´ı ˇca´sti, uved’me jeˇstˇe jednu pozn´amku. M´ame-li metrick´ y prostor, lze se na jeho podmnoˇziny d´ıvat tak´e jako na metrick´e (pod)prostory. ˇ s metrikou danou vzd´alenost´ı Kupˇr´ıkladu jsou-li metrick´ ym prostorem obce CR vzduˇsnou ˇcarou, budou metrick´ ym prostorem i mˇesta a vesnice na Moravˇe s tout´eˇz vzd´alenost´ı. Jen je nutn´e d´at pozor na otevˇren´e a uzavˇren´e mnoˇziny, kter´e je pak potˇreba vztahovat k nov´emu podprostoru. Pˇ r´ıklad 3.14. V metrick´em prostoru (R, ρ1 ) nen´ı interval I := [0, 1) ani uzavˇren´a ani otevˇren´a mnoˇzina. V podprostoru (I, ρ1 ) uˇz je ale I i uzavˇren´ y i otevˇren´ y (cel´ y prostor je vˇzdy takov´ y).

3.2

Stromy

Ukaˇzme si, ˇze i hry lze ch´apat jako metrick´e prostory. Metrick´ y prostor lze vybudovat na libovoln´e mnoˇzinˇe, tˇreba s diskr´etn´ı metrikou, mus´ıme si tedy vybrat nˇejakou strukturu, kter´a bude vhodn´a pro naˇse u ´ˇcely. Ukazuje se, ˇze takovou strukturou jsou stromy. (Pˇripomeˇ nme, ˇze jiˇz v prvn´ı kapitole jsme pouˇz´ıvali jako pom˚ ucku strom hry. Nyn´ı to bude podobn´e.) V t´eto i n´asleduj´ıc´ı sekci budeme vych´azet z knihy A. Kechrise o deskriptivn´ı teorii mnoˇzin [11] a z pˇredn´aˇsky Deskriptivn´ı teorie mnoˇzin doc. Zelen´eho [15]. Abychom ale mohli definovat stromy, potˇrebujeme nˇekolik pomocn´ ych pojm˚ u. Zaˇcneme posloupnostmi. Motivac´ı je n´am fakt, ˇze na hru se d´a d´ıvat jako na posloupnost tah˚ u. Znaˇ cen´ı 3.15. Necht’ X je nepr´azdn´a mnoˇzina a n ∈ N. Symbolem X n budeme znaˇcit vˇsechny posloupnosti p = (x0 , x1 , . . . , xn−1 ) d´elky n, kde x0 , . . . xn−1 ∈ X. D´elku n t´eto posloupnosti, tedy poˇcet jej´ıch ˇclen˚ u, budeme znaˇcit |p|. Mnoˇzinu vˇsech posloupnost´ı z X libovoln´e d´elky oznaˇcme [ X
a mnoˇzinu vˇsech nekoneˇcn´ ych posloupnost´ı oznaˇcme X N . Spojen´ım dvou posloupnost´ı s = (s0 , s1 , . . . sj ) ∈ X
Necht’ k ∈ N. Restrikc´ı posloupnosti p na prvn´ıch k ˇclen˚ u, kde |p| ≥ k, rozum´ıme posloupnost p|k := (p0 , p1 , . . . , pk−1 ). Posloupnost t ∈ X
(3) aby a abba,

(2) kolo a kolobˇeˇzka,

(4) abaabaaabaaaa. . . a abacadaea. . . .

Jak ale vypadaj´ı otevˇren´e a uzavˇren´e mnoˇziny v X N ? Uved’me jeden pˇr´ıklad takov´ ych mnoˇzin. Zafixujme posloupnost s ∈ X
22

Definice 3.19. Mnoˇzina σ ⊂ X
Obr. 3.3: Strom

Obr. 3.4: Proˇrezan´ y strom, [σ] je zde rovno vˇsem nekoneˇcn´ ym posloupnostem 0 a1

23

Pˇ r´ıklad 3.20. Vr´at´ıme-li se k pˇr´ıkladu s ˇcesk´ ymi p´ısmeny a slovy, tak strom m˚ uˇzeme definovat jako syst´em vˇsech smyslupln´ ych ˇcesk´ ych slov a jejich ˇc´ast´ı. Nebude ovˇsem proˇrezan´ y. Pˇ r´ıklad 3.21. Stromem je i strom hry Nim na obr. 3.5. Posloupnosti jsou zde tvoˇreny dvojicemi ˇc´ısel, kter´e odpov´ıdaj´ı poˇctu kamen˚ u v hrom´adk´ach.

Obr. 3.5: Strom Nimu 2 − 2 Protoˇze (proˇrezan´ y) strom σ je podmnoˇzina prostoru vˇsech posloupnost´ı, tak zdˇed´ı metriku popsanou v´ yˇse. Tedy bude platit, ˇze mnoˇzina N (s) = {t ∈ X N ; s ≺ t, t ⊂ [σ]}, kde s ∈ σ, je otevˇren´a i uzavˇren´a v [σ].

3.3

Teorie her

Nyn´ı m´ame vˇsechny potˇrebn´e ingredience, abychom uk´azali, kdy obecnˇe maj´ı hry v´ıtˇeznou strategii. Celou teorii vyslov´ıme pro hry nekoneˇcn´e, protoˇze hry koneˇcn´e (jako Nim nebo ˇsachy) na nˇe lze snadno pˇrev´est, jak uvid´ıme n´ıˇze. Zaˇcnˇeme definic´ı hry. Definice 3.22. Necht’ X je nepr´azdn´a mnoˇzina, T ⊂ X
x0

x2 x1

... x3

...

• Hr´aˇc A vyhraje, jestliˇze x ∈ V , jinak vyhraje hr´aˇc B.

24

Z tohoto pohledu je hra stromem, kter´ y pˇredstavuje vˇsechny moˇzn´e sehran´e partie hry, vˇsechny moˇzn´e tahy obou hr´aˇc˚ u. Konkr´etn´ı partie pak spoˇc´ıv´a ve v´ ybˇeru jedn´e vˇetve. Ukaˇzme si pˇr´ıklady matematick´ ych her (v´ıtˇeznou strategii nalezne ˇcten´aˇr v [3] a [4]): Pˇ r´ıklady 3.23. (1) Alice a Bob hraj´ı hru na intervalu [0, 1] a s mnoˇzinou S ⊂ [0, 1]. Alice vybere ˇc´ıslo x0 ∈ [0, 1]. N´aslednˇe Bob vybere ˇc´ıslo x1 leˇz´ıc´ı striktnˇe mezi x0 a 1. Pak Alice zvol´ı ˇc´ıslo x2 mezi x0 a x1 atd. Jestliˇze limita posloupnosti xn bude leˇzet v S, vyhr´ala Alice. Jinak vyhr´al Bob. (2) Alice a Bob hraj´ı na metrick´em prostoru (X, ρ). Alice zvol´ı (nepr´azdnou) mnoˇzinu A0 . Bob pak T vybere mnoˇzinu A1 ⊂ A0 . Alice zvol´ı A2 ⊂ A1 atd. Alice vyhraje, jestliˇze ∞ azdn´a mnoˇzina, jinak vyhraje Bob. i=1 Ai bude pr´ Jeˇzto je naˇs´ım c´ılem uk´azat existenci v´ıtˇezn´e strategie pro Nim, je tˇreba jej popsat v ˇreˇci Definice 3.22. V podstatˇe to znamen´a popsat obr´azek stromu matematick´ ym jazykem. K tomu potˇrebujeme naj´ıt mnoˇziny X, T a V . Pˇ r´ıklad 3.24. Zvolme jako pˇr´ıklad u ´vodn´ı hru 5-4-3. Mnoˇzinou X pak budou uspoˇr´adan´e trojice nez´apor´ ych ˇc´ısel x − y − z, kde x ≤ 5, y ≤ 4, z ≤ 3. Tahem hr´aˇce pak nebudeme rozumˇet, kolik kamen˚ u kde odebral, ale do jak´e pozice se dostal. Tedy x0 m˚ uˇze b´ yt 5 − 4 − 2, 0 − 4 − 3 nebo tˇreba 5 − 1 − 3. T´ımto postupem bychom ale z´ıskali i nedovolen´e tahy, kupˇr´ıkladu x0 = 5 − 2 − 2. Tomu zabr´an´ıme vhodnou volbou T , staˇc´ı jej definovat jako povolen´e pozice. T´ım sice z´ısk´ame strom, ale nebude proˇrezan´ y. Budeme muset kaˇzdou vˇetev prodlouˇzit a to sam´ ymi prvky 0 − 0 − 0. N´aˇs strom tedy bude sest´avat ze vˇsech moˇzn´ ych povolen´ ych tah˚ u a jakmile se dostaneme do pozice 0 − 0 − 0, uˇz v n´ı setrv´ame. Takovou vˇetv´ı m˚ uˇze b´ yt napˇr´ıklad (5 − 4 − 0, 0 − 4 − 0, 0 − 0 − 0, 0 − 0 − 0, 0 − 0 − 0, . . .). Ale hra Nim je koneˇcn´a, do stavu 0 − 0 − 0 se dostane nejpozdˇeji po 12 kroc´ıch, kaˇzd´a vˇetev je tedy nejpozdˇeji ve 13. prvku pozicemi 0 − 0 − 0. Zb´ yv´a naj´ıt mnoˇzinu V ⊂ [T ]. Poloˇzme si tedy ot´azku, kdy vyhr´av´a Alice. Je to tehdy, kdyˇz vezme posledn´ı k´amen a dostane se do pozice 0-0-0. Jin´ ymi slovy, pro nˇejak´e n ∈ N je x2n = 0 − 0 − 0 a pˇritom xi 6= 0 − 0 − 0 pro vˇsechna i < 2n. (Naopak Bob by vyhr´al, kdyby tato situace nastala pro nˇejak´e x2n+1 , kde n ∈ N). Hra Nim jako takov´a v tu chv´ıli konˇc´ı, ale i V mus´ıme dodefinovat na nekoneˇcnou stukturu. V bude tedy mnoˇzina posloupnost´ı, kter´e od jist´eho sud´eho tahu uˇz nab´ yvaj´ı jen nulov´ ych pozic, neboli V = {a ∈ T, ∃n ∈ N, xi = 0 − 0 − 0 ⇔ i ≥ 2n}. Cviˇ cen´ı 3.25. Popiˇste jako strom hru Nim (2-2) ve verzi Mis`ere. Definovali jsme hru. Naˇs´ım koneˇcn´ ym c´ılem je nalezen´ı strategie, coˇz je vlastnˇe n´avod, kter´ y ˇr´ık´a, jak hr´at v jak´em okamˇziku. I strategii mus´ıme definovat a ukazuje se jako vhodn´e pouˇz´ıt strom. Definice 3.26. Strategie pro A je strom σ, kter´ y je proˇrezan´ y a splˇ nuje:

25

(1) jestliˇze (x0 , x1 , . . . x2n ) ∈ σ, pak pro kaˇzd´e x2n+1 tak´e (x0 , x1 , . . . x2n , x2n+1 ) ∈ σ (2) jestliˇze (x0 , x1 , . . . x2n−1 ) ∈ σ, pak existuje pr´avˇe jedno x2n takov´e, ˇze (x0 , x1 , . . . x2n−1 , x2n ) ∈ σ. Strategie je tedy v´ ybˇer podstromu“ ze stromu hry tak, aby ˇr´ıkala hr´aˇci A ” jak hr´at (druh´a podm´ınka), at’ uˇz Bob bude hr´at jakkoli (prvn´ı podm´ınka). Pak stejnˇe jako v prvn´ı kapitole ˇrekneme, ˇze strategie pro A je v´ıtˇezn´a, jestliˇze s n´ı A vyhraje, at’ uˇz B bude hr´at libovoln´ ym zp˚ usobem. V ˇreˇci strom˚ u to znamen´a, ˇze posloupnosti stromu vznikl´eho vˇsemi moˇzn´ ymi aplikacemi strategie σ budou v mnoˇzinˇe V , neboli σ ⊂ V . D´ale, pozici p = (x0 , x1 , . . . , x2n−1 ) nazveme vyhr´avaj´ıc´ı pro A (kter´ y je na tahu), jestliˇze B nem´a v´ıtˇeznou strategii ve hˇre s t´ımto poˇca´tkem, neboli B nem´a v´ıtˇeznou strategii ve hˇre G(Tp , Vp ), kde Tp = {s : p+s ∈ T } a Vp = {v : p+v ∈ V }. Nyn´ı m´ame definov´anu hru i v´ıtˇeznou strategii. Zb´ yv´a dok´azat, ˇze hry jako Nim v´ıtˇeznou strategii maj´ı. Tuto problematiku ˇreˇs´ı n´asleduj´ıc´ı vˇeta. Neˇz ji vyslov´ıme, jeˇstˇe pˇripomeˇ nme, ˇze na strom se d´ıv´ame jako na metrick´ y prostor, tedy v nˇem lze hovoˇrit o uzavˇren´ ych mnoˇzin´ach. Vˇ eta 3.27 (Gale-Stewart). Necht’ V je uzavˇren´a. Potom ve hˇre G(T, V ) existuje v´ıtˇezn´a strategie bud’ pro A, nebo pro B. D˚ ukaz. V pˇr´ıpadˇe, ˇze by Bob mˇel v´ıtˇeznou strategii, je d˚ ukaz hotov. Pˇredpokl´adejme tedy, ˇze Bob v´ıtˇeznou strategii nem´a. Budeme cht´ıt uk´azat, ˇze ji m´a Alice. Nejprve p´ar pozorov´an´ı. Jeˇzto jsme pˇredpokl´adali, ˇze Bob nem´a v´ıtˇeznou strategii, tak u ´vodn´ı pozice ∅ je vyhr´avaj´ıc´ı pro Alici. D´ale, je-li pozice p = (x0 , x1 , . . . , x2n−1 ) ∈ T vyhr´avaj´ıc´ı pro Alici, pak existuje x2n takov´e, ˇze pro libovoln´e x2n+1 je pozice p = (x0 , x1 , . . . , x2n−1 , x2n , x2n+1 ) ∈ T opˇet vyhr´avaj´ıc´ı pro Alici. Nyn´ı m˚ uˇzeme Alici sestrojit v´ıtˇeznou strategii. Zaˇcnˇeme volbou takov´eho x0 , ˇze (x0 ) ∈ T a pro kaˇzd´e x1 takov´e, ˇze (x0 , x1 ) ∈ T , je pozice (x0 , x1 ) vyhr´avaj´ıc´ı pro Alici. D´ale pokraˇcujeme analogicky, Alice zvol´ı x2 tak, aby pro libovoln´e x3 , kter´e zvol´ı Bob byla pozice (x0 , x1 , x2 , x3 ) ∈ T vyhr´avaj´ıc´ı pro Alici atd. Z´ıskan´a strategie uˇz je v´ıtˇezn´a pro Alici. Kdyby nebyla, tak bude existovat partie sehran´a dle t´eto strategie takov´a, ˇze vznikl´a posloupnost (x0 , x1 , x2 , . . .) 6∈ V . Mnoˇzina [T ] \ V je ale otevˇren´a v [T ] a tedy existuje n ∈ N takov´e, ˇze N (x0 , x1 , . . . , x2n−1 ) ∩ [T ] ⊂ [T ] \ V . To je ale spor, protoˇze pak by pozice (x0 , x1 , . . . , x2n−1 ) nebyla vyhr´avaj´ıc´ı pro Alici a Bob m˚ uˇze hr´at libovolnˇe a vyhraje. Pozn´ amka 3.28. Pr´avˇe jsme uk´azali, ˇze je-li V uzavˇren´a mnoˇzina, existuje v´ıtˇezn´a strategie. Vkr´ad´a se ot´azka, zda obdobn´e vˇety neplat´ı i pro nˇejak´e dalˇs´ı typy mnoˇzin. Odpovˇed’ je kladn´a. Vˇeta se d´a dok´azat i za podm´ınky, ˇze V je otevˇren´a, a lze zformulovat analogick´e vˇety i pro sloˇzitˇejˇs´ı syst´emy mnoˇzin, jako jsou napˇr´ıklad nekoneˇcn´e pr˚ uniky otevˇren´ ych mnoˇzin ˇci sjednocen´ı uzavˇren´ ych mnoˇzin. Vˇse je jiˇz pˇripraveno, abychom uk´azali, ˇze Nim m´a v´ıtˇeznou strategii (aniˇz bychom ji zkonstruovali), staˇc´ı aplikovat Vˇetu 3.27. Ukaˇzme si to na hˇre z pˇr´ıkladu 3.24. 26

Pˇ r´ıklad 3.29. Mus´ıme uk´azat, ˇze V je uzavˇren´a v metrick´em prostoru dan´em stromem T . To dok´aˇzeme z Vˇety 3.11. Zvolme tedy posloupnost (xk ) ⊂ V , xk → x, k ∈ N. Chceme uk´azat, ˇze i x ∈ V . Jak vypad´a posloupnost (xk )? Jej´ı samotn´e prvky xk jsou vlastnˇe posloupnostmi uspoˇra´dan´ ych trojic, kter´e vznikly pˇr´ıpustn´ ymi tahy a kter´e se vynulovaly“ ” v sud´em prvku, tedy napˇr. x1 = (5 − 4 − 2, 0 − 4 − 2, 0 − 2 − 2, 0 − 1 − 2, 0 − 0 − 2, 0 − 0 − 1, 0 − 0 − 0, 0 − 0 − 0, . . .), x2 = (5 − 3 − 3, 5 − 0 − 3, 0 − 0 − 3, 0 − 0 − 2, 0 − 0 − 0, 0 − 0 − 0, 0 − 0 − 0, 0 − 0 − 0, . . .), x3 = (3 − 4 − 3, 3 − 4 − 2, 3 − 2 − 2, 0 − 2 − 2, 0 − 1 − 2, 0 − 1 − 0, 0 − 0 − 0, 0 − 0 − 0, . . .). Z´aroveˇ n tato posloupnost posloupnost´ı konverguje k nˇejak´emu x. Jin´ ymi slovy to znamen´a, ˇze prvky xk jsou od jist´eho k bl´ızko“ k x. V ˇreˇci naˇs´ı metriky tedy ” pro kaˇzd´e ε > 0 existuje k0 takov´e, ˇze pro kaˇzd´e k ≥ k0 m´ame ρ(xk , x) < ε. Aby toto ale platilo v metrice definovan´e na posloupnostech, tak pro ε < 2114 uˇz se mus´ı vˇsechny ˇcleny xk a x rovnat (Nezapomeˇ nte, ˇze vˇsechny posloupnosti v T jsou nejpozdˇeji od 13. prvku nulov´e). Tedy existuje k0 ∈ N takov´e, ˇze pro vˇsechna i, j ≥ k0 je xi = xj = x a posloupnost je od urˇcit´eho ˇclenu konstantn´ı (a tedy vynulovan´a v sud´em kroku). Odtud ale trivi´alnˇe plyne, ˇze i limita x ∈ V , coˇz jsme chtˇeli. M´ame nyn´ı tedy vˇse, abychom mohli aplikovat Galeovu-Stewartovu vˇetu, z n´ıˇz uˇz plyne, ˇze hra Nim 5 − 4 − 3 m´a v´ıtˇeznou strategii. ´ Uvahy popsan´e v pˇredchoz´ım pˇr´ıkladˇe lze samozˇrejmˇe aplikovat i na hry s jinou v´ ychoz´ı situac´ı neˇz 5 − 4 − 3, ˇc´ımˇz lze snadno uk´azat, ˇze hra Nim m´a v´ıtˇeznou strategii i v ˇreˇci strom˚ u a metrick´ ych prostor˚ u, coˇz jsme chtˇeli. Na z´avˇer pozn´amku k hr´am obecnˇe. Pˇri aplikaci Galeovy-Stewartovy vˇety jsme vyuˇzili faktu, ˇze hra Nim je od jist´eho tahu prodlouˇzena sam´ ymi nulami, d´ıky ˇcemuˇz jsme snadno uk´azali, ˇze V je uzavˇren´a. Tento postup lze ale snadno zopakovat i u jin´ ych koneˇcn´ ych her, napˇr. u Mis`ere Nimu, Tac Tix nebo (oˇsetˇr´ımeli patov´e situace) u ˇsach˚ u. Vˇsechny tyto hry tedy maj´ı v´ıtˇeznou strategii, pˇrestoˇze nemus´ıme vˇedˇet, jak pˇresnˇe vypad´a. Pouˇzit´ı t´eto vˇety na hru Nim bylo tak trochu pouˇzit´ım kan´onu na vrabce. Vyloˇzen´a teorie pˇresto nen´ı zbyteˇcn´a, jej´ı s´ıla spoˇc´ıv´a pr´avˇe v nekoneˇcn´ ych hr´ach, kter´ ym se existence v´ıtˇezn´e strategie dokazuje obt´ıˇznˇeji. Pokud si uvˇedom´ıme, ˇze nˇekter´e matematick´e vˇety lze na teorii her pˇrev´est, jev´ı se tato teorie jako velmi uˇziteˇcn´a.

27

Z´ avˇ er Hry jsou vdˇeˇcn´e matematick´e t´ema a hra Nim nen´ı v tomto smˇeru v´ yjimkou. Jej´ı v´ıtˇezn´a strategie pˇr´ımo zaloˇzen´a na bin´arn´ıch ˇc´ıslech a souˇctu xor je prvn´ım krokem do ˇr´ıˇse informatiky, strom hry je ochutn´avka teorie graf˚ u. Pˇri hled´an´ı strategie jsme nav´ıc konfrontov´ani s potˇrebou d˚ ukaz˚ u a jejich r˚ uzn´ ych typ˚ u. Pˇresto nebylo c´ılem zahltit ˇcten´aˇre pˇrem´ırou definic a vydˇesit jej pˇrem´ırou matematick´eho jazyka. P˚ uvodn´ım z´amˇerem nav´ıc bylo dov´est ˇcten´aˇre, aby strategii odvodil a pochopil s´am. Toto bohuˇzel nebylo naplnˇeno, neb aˇc je strategie jednoduch´a a snadno aplikovateln´a, m´alokdo by hledal v odeb´ır´an´ı kamen˚ u dvojkovou soustavu. V urˇcit´e chv´ıli tedy bylo tˇreba ustoupit a strategii ˇcten´aˇri vˇenovat. Ve druh´e kapitole jsme si uk´azali varianty hry Nim a jej´ı skryt´e verze. Kapitola by se dala rozˇsiˇrovat prakticky do nekoneˇcna, u ´prav hry je zn´amo skuteˇcnˇe mnoho, nˇekter´e maj´ı a nˇekter´e nemaj´ı zn´amou v´ıtˇeznou strategii, coˇz se projevilo i ve v´ ybˇeru her. V druh´e ˇca´sti byla zvl´aˇstn´ı pozornost vˇenov´ana hˇre Hackenbush, kter´a m´a stejnˇe jako Nim mnoho variant, kter´e uˇz nebylo moˇzno zahrnout kv˚ uli pl´anovan´emu rozsahu pr´ace. Odkazujeme proto ˇcten´aˇre k dalˇs´ımu studiu. Tˇret´ı kapitola pˇredstavuje u ´vod do teorie metrick´ ych prostor˚ u. Zavedli jsme abstraktn´ı strukturu prostoru a metriky a u ´spˇeˇsnˇe ji aplikovali na stromy. Tento pˇr´ıklad se snad neuv´ad´ı v z´akladn´ıch kurzech matematiky, pˇresto jsme v teorii her docenili jeho uˇziteˇcnost, kdyˇz jsme sestavovali strom hry Nim a pomoc´ı hlubok´ ych vˇet dokazovali existenci v´ıtˇezn´e strategie. C´ıl definovan´ yvu ´vodu pr´ace je moˇzno oznaˇcit za splnˇen´ y, ˇcten´aˇr se sezn´amil s hrou a na jej´ım z´akladˇe s r˚ uzn´ ymi partiemi matematiky.

28

Literatura [1] Nim. http://en.wikipedia.org/wiki/Nim, July 2014. [2] M. Antol. Combinatorial games. Bachelor’s thesis, Masaryk University, 2011. [3] M. Baker. Real numbers and infinite games, http://mattbakerblog.wordpress.com/2014/07/01/ real-numbers-and-infinite-games-part-i/, July 2014.

part

i.

[4] M. Baker. Real numbers and infinite games, http://mattbakerblog.wordpress.com/2014/07/07/ real-numbers-and-infinite-games-part-ii/, July 2014.

part

ii.

[5] E. R. Berlekamp, J. H. Conway, and R. K. Guy. Winning ways for your mathematical plays. Vol. 1. A K Peters, Ltd., Natick, MA, second edition, 2001. [6] C. L. Bouton. Nim, a game with a complete mathematical theory. Ann. of Math. (2), 3(1-4):35–39, 1901/02. [7] R. A. Epstein. The theory of gambling and statistical logic. vier/Academic Press, Amsterdam, second edition, 2009.

Else-

[8] M. Gardner. Wheels, life and other mathematical amusements. W. H. Freeman and Co., San Francisco, CA, 1983. [9] M. Gardner. Hexaflexagons and other mathematical diversions. The University of Chicago Press, Ltd., London, 1988. [10] J. C. Holladay. Matrix Nim. Amer. Math. Monthly, 65:107–109, 1958. [11] A. S. Kechris. Classical descriptive set theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. [12] R. J. Nowakowski, editor. Games of no chance, volume 29 of Mathematical Sciences Research Institute Publications. Cambridge University Press, Cambridge, 1996. Papers from the Combinatorial Games Workshop held in Berkeley, CA, July 11–21, 1994. [13] A. Sk´alov´a. Teorie her pro nadan´e ˇza´ky stˇredn´ıch ˇskol. Master’s thesis, Univerzita Karlova v Praze, 2014. [14] L. Zaj´ıˇcek. Vybran´e partie z matematick´e anal´yzy pro 1. a 2. roˇcn´ık. Matfyzpress, vydavatelstv´ı Matematicko-fyzik´aln´ı fakulty Univerzity Karlovy, 2003. 29

[15] M. Zelen´ y. Deskriptivn´ı teorie mnoˇzin i. http://www.karlin.mff.cuni. cz/~zeleny/mff/DST.php, July 2014.

30

Seznam obr´ azk˚ u 1.1 1.2 1.3

Nim; http://www.mathematische-basteleien.de/nimgame.html . . Strom Nimu 2 − 2; http://ljkrakauer.com/LJK/60s/chess2.htm . . Pˇrevod ˇc´ısel do bin´arn´ı soustavy . . . . . . . . . . . . . . . . . . .

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10

Mis`ere Nim; jako Obr.3.5, upraveno . . . Tac Tix; http://kruzno.com/TacTix.html Mince na p´asku; [12] . . . . . . . . . . . Stepinova hra; [7] . . . . . . . . . . . . . Hackenbush; [8] . . . . . . . . . . . . . . Hackenbush vhodn´ y a nevhodn´ y [5] . . . Hackenbush bez cykl˚ u a vˇetven´ı; [2] . . . Vˇetven´ı, tamt´eˇz . . . . . . . . . . . . . . Cykly, tamt´eˇz . . . . . . . . . . . . . . . Cykly II, tamt´eˇz . . . . . . . . . . . . .

3.1

Koule v R2 ; http://simomaths.wordpress.com/2013/01/18/topologybasic-definitions/ . . . . . . . . . . . . . . . . . . . . . . . . . . . Otevˇren´e a uzavˇren´e mnoˇziny v R2 . . . . . . . . . . . . . . . . . Strom; [11] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Proˇrezan´ y strom; [11] . . . . . . . . . . . . . . . . . . . . . . . . . Strom Nimu 2−2; http://upload.wikimedia.org/wikipedia/commons/ thumb/b/b1/TeorieHer-nim.jpg/600px-TeorieHer-nim.jpg . . . . .

3.2 3.3 3.4 3.5

31

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

2 3 5 10 12 12 13 14 14 15 15 16 16 19 20 23 23 24