Kombinatorick´e hry Michal Bulant Masarykova univerzita Pˇr´ırodovˇ edeck´ a fakulta ´ Ustav matematiky a statistiky
2. 9. 2008
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
1 / 51
Obsah pˇredn´aˇsky
1
Hry na odeb´ır´an´ı kamen˚ u
2
Nim
3
Hry na grafech
4
Souˇcty her
5
Dalˇs´ı hry ˇreˇsiteln´e pomoc´ı SG-funkce Hry Take-and-Break Ot´aˇcen´ı minc´ı Dvourozmˇern´e ot´aˇcen´ı minc´ı a nim-souˇcin
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
2 / 51
O ˇcem je ˇreˇc?
Kombinatorick´ a hra je hra dvou hr´aˇc˚ usu ´plnou informac´ı (ˇz´adn´e skryt´e ani simult´ann´ı tahy ), bez n´ahody (tj. nikoliv k´amen-n˚ uˇzky-pap´ır, vrhc´aby, poker apod.). Hra je urˇcena moˇzn´ymi stavy (pozicemi), ve kter´ych se m˚ uˇze nach´azet, a t´ım, kter´y hr´aˇc je zrovna na tahu. Hr´aˇci se obvykle v taz´ıch stˇr´ıdaj´ı do t´e doby, neˇz je dosaˇzen koncov´y stav – pak je jeden z hr´aˇc˚ u prohl´aˇsen za v´ıtˇeze a druh´y za poraˇzen´eho.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
3 / 51
O ˇcem je ˇreˇc?
Kombinatorick´ a hra je hra dvou hr´aˇc˚ usu ´plnou informac´ı (ˇz´adn´e skryt´e ani simult´ann´ı tahy ), bez n´ahody (tj. nikoliv k´amen-n˚ uˇzky-pap´ır, vrhc´aby, poker apod.). Hra je urˇcena moˇzn´ymi stavy (pozicemi), ve kter´ych se m˚ uˇze nach´azet, a t´ım, kter´y hr´aˇc je zrovna na tahu. Hr´aˇci se obvykle v taz´ıch stˇr´ıdaj´ı do t´e doby, neˇz je dosaˇzen koncov´y stav – pak je jeden z hr´aˇc˚ u prohl´aˇsen za v´ıtˇeze a druh´y za poraˇzen´eho. My se nav´ıc budeme zab´yvat pouze hrami nestrann´ ymi (angl. impartial), kde maj´ı oba hr´aˇci k dispozici stejn´e tahy (t´ım jsou vylouˇceny napˇr. ˇsachy nebo d´ama).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
3 / 51
Pl´an pˇredn´aˇsky
1
Hry na odeb´ır´an´ı kamen˚ u
2
Nim
3
Hry na grafech
4
Souˇcty her
5
Dalˇs´ı hry ˇreˇsiteln´e pomoc´ı SG-funkce Hry Take-and-Break Ot´aˇcen´ı minc´ı Dvourozmˇern´e ot´aˇcen´ı minc´ı a nim-souˇcin
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
4 / 51
Jednoduch´a hra na u´vod
1
Hraje se s 21 kameny.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
5 / 51
Jednoduch´a hra na u´vod
1
Hraje se s 21 kameny.
2
Tah spoˇc´ıv´a v odebr´an´ı jednoho, dvou nebo tˇr´ı kamen˚ u.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
5 / 51
Jednoduch´a hra na u´vod
1
Hraje se s 21 kameny.
2
Tah spoˇc´ıv´a v odebr´an´ı jednoho, dvou nebo tˇr´ı kamen˚ u.
3
Hr´aˇc, kter´y odebere posledn´ı k´amen, vyhr´av´a ( tj. hr´aˇc, kter´y nem˚ uˇze t´ahnout, prohr´al).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
5 / 51
Jednoduch´a hra na u´vod
1
Hraje se s 21 kameny.
2
Tah spoˇc´ıv´a v odebr´an´ı jednoho, dvou nebo tˇr´ı kamen˚ u.
3
Hr´aˇc, kter´y odebere posledn´ı k´amen, vyhr´av´a ( tj. hr´aˇc, kter´y nem˚ uˇze t´ahnout, prohr´al).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
5 / 51
Jednoduch´a hra na u´vod
1
Hraje se s 21 kameny.
2
Tah spoˇc´ıv´a v odebr´an´ı jednoho, dvou nebo tˇr´ı kamen˚ u.
3
Hr´aˇc, kter´y odebere posledn´ı k´amen, vyhr´av´a ( tj. hr´aˇc, kter´y nem˚ uˇze t´ahnout, prohr´al).
Naˇs´ım c´ılem je zjistit, jestli si nˇekter´y z hr´aˇc˚ u m˚ uˇze vynutit v´ıtˇezstv´ı.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
5 / 51
Anal´yza jednoduch´e hry Pˇri anal´yze budeme postupovat zpˇetnou indukc´ı (odvozen´ım): jsou-li na stole 1-3 kameny, pak hr´aˇc na tahu vyhr´ av´ a jsou-li na stole 4 kameny, pak hr´aˇc na tahu pror´ av´ a (nem´a jinou moˇznost, neˇz dalˇs´ım tahem uv´est hru do stavu, kdy jsou na stole 1-3 kameny a vyhr´av´a tedy jeho soupeˇr) je-li na stole 5-7 kamen˚ u, hr´aˇc na tahu vyhr´av´a (m˚ uˇze odebrat tolik kamen˚ u, aby zbyly 4) atd.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
6 / 51
Anal´yza jednoduch´e hry Pˇri anal´yze budeme postupovat zpˇetnou indukc´ı (odvozen´ım): jsou-li na stole 1-3 kameny, pak hr´aˇc na tahu vyhr´ av´ a jsou-li na stole 4 kameny, pak hr´aˇc na tahu pror´ av´ a (nem´a jinou moˇznost, neˇz dalˇs´ım tahem uv´est hru do stavu, kdy jsou na stole 1-3 kameny a vyhr´av´a tedy jeho soupeˇr) je-li na stole 5-7 kamen˚ u, hr´aˇc na tahu vyhr´av´a (m˚ uˇze odebrat tolik kamen˚ u, aby zbyly 4) atd. U t´eto hry je tedy pomˇernˇe snadno vidˇet, ˇze stav s 0,4,8,12,. . . ,20 kameny jsou stav, kdy hr´aˇc na tahu prohr´av´a.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
6 / 51
Anal´yza jednoduch´e hry Pˇri anal´yze budeme postupovat zpˇetnou indukc´ı (odvozen´ım): jsou-li na stole 1-3 kameny, pak hr´aˇc na tahu vyhr´ av´ a jsou-li na stole 4 kameny, pak hr´aˇc na tahu pror´ av´ a (nem´a jinou moˇznost, neˇz dalˇs´ım tahem uv´est hru do stavu, kdy jsou na stole 1-3 kameny a vyhr´av´a tedy jeho soupeˇr) je-li na stole 5-7 kamen˚ u, hr´aˇc na tahu vyhr´av´a (m˚ uˇze odebrat tolik kamen˚ u, aby zbyly 4) atd. U t´eto hry je tedy pomˇernˇe snadno vidˇet, ˇze stav s 0,4,8,12,. . . ,20 kameny jsou stav, kdy hr´aˇc na tahu prohr´av´a. V naˇs´ı hˇre tedy v´ıtˇ ez´ı hr´ aˇ c, kter´ y zaˇ c´ın´ a – staˇc´ı v 1. tahu odebrat jeden k´amen a pot´e postupovat tak, aby po jeho tahu zbyl poˇcet kamen˚ u, kter´y je n´asobkem 4. Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
6 / 51
Definice kombinatorick´e hry Definice Kombinatorick´a hra splˇ nuje n´asleduj´ıc´ı podm´ınky: 1
Hraj´ı 2 hr´aˇci.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
7 / 51
Definice kombinatorick´e hry Definice Kombinatorick´a hra splˇ nuje n´asleduj´ıc´ı podm´ınky: 1
Hraj´ı 2 hr´aˇci.
2
Je d´ana mnoˇzina (obvykle koneˇcn´a) moˇzn´ych tah˚ u.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
7 / 51
Definice kombinatorick´e hry Definice Kombinatorick´a hra splˇ nuje n´asleduj´ıc´ı podm´ınky: 1
Hraj´ı 2 hr´aˇci.
2
Je d´ana mnoˇzina (obvykle koneˇcn´a) moˇzn´ych tah˚ u.
3
Pravidla hry urˇcuj´ı pro kaˇzd´eho hr´aˇce v kaˇzd´e pozici moˇzn´e dalˇs´ı tahy. Pokud pravidla nerozliˇsuj´ı hr´aˇce, naz´yv´a se hra nestrann´ a (impartial), v opaˇcn´em pˇr´ıpadˇe partyz´ ansk´ a (partizan).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
7 / 51
Definice kombinatorick´e hry Definice Kombinatorick´a hra splˇ nuje n´asleduj´ıc´ı podm´ınky: 1
Hraj´ı 2 hr´aˇci.
2
Je d´ana mnoˇzina (obvykle koneˇcn´a) moˇzn´ych tah˚ u.
3
Pravidla hry urˇcuj´ı pro kaˇzd´eho hr´aˇce v kaˇzd´e pozici moˇzn´e dalˇs´ı tahy. Pokud pravidla nerozliˇsuj´ı hr´aˇce, naz´yv´a se hra nestrann´ a (impartial), v opaˇcn´em pˇr´ıpadˇe partyz´ ansk´ a (partizan).
4
Hr´aˇci se ve sv´ych taz´ıch stˇr´ıdaj´ı.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
7 / 51
Definice kombinatorick´e hry Definice Kombinatorick´a hra splˇ nuje n´asleduj´ıc´ı podm´ınky: 1
Hraj´ı 2 hr´aˇci.
2
Je d´ana mnoˇzina (obvykle koneˇcn´a) moˇzn´ych tah˚ u.
3
Pravidla hry urˇcuj´ı pro kaˇzd´eho hr´aˇce v kaˇzd´e pozici moˇzn´e dalˇs´ı tahy. Pokud pravidla nerozliˇsuj´ı hr´aˇce, naz´yv´a se hra nestrann´ a (impartial), v opaˇcn´em pˇr´ıpadˇe partyz´ ansk´ a (partizan).
4
Hr´aˇci se ve sv´ych taz´ıch stˇr´ıdaj´ı.
5
Hra konˇc´ı ve chv´ıli, kdy je dosaˇzen stav, v nˇemˇz nen´ı moˇzn´y dalˇs´ı tah. Pˇri norm´ aln´ı hˇre (normal play rule) pak vyhr´av´a hr´aˇc, kter´y uˇcinil posledn´ı tah, pˇri nuzn´ e hˇre (mis`ere play rule) takov´y hr´aˇc prohr´av´a.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
7 / 51
Definice kombinatorick´e hry Definice Kombinatorick´a hra splˇ nuje n´asleduj´ıc´ı podm´ınky: 1
Hraj´ı 2 hr´aˇci.
2
Je d´ana mnoˇzina (obvykle koneˇcn´a) moˇzn´ych tah˚ u.
3
Pravidla hry urˇcuj´ı pro kaˇzd´eho hr´aˇce v kaˇzd´e pozici moˇzn´e dalˇs´ı tahy. Pokud pravidla nerozliˇsuj´ı hr´aˇce, naz´yv´a se hra nestrann´ a (impartial), v opaˇcn´em pˇr´ıpadˇe partyz´ ansk´ a (partizan).
4
Hr´aˇci se ve sv´ych taz´ıch stˇr´ıdaj´ı.
5
Hra konˇc´ı ve chv´ıli, kdy je dosaˇzen stav, v nˇemˇz nen´ı moˇzn´y dalˇs´ı tah. Pˇri norm´ aln´ı hˇre (normal play rule) pak vyhr´av´a hr´aˇc, kter´y uˇcinil posledn´ı tah, pˇri nuzn´ e hˇre (mis`ere play rule) takov´y hr´aˇc prohr´av´a.
6
(koneˇ cnost hry) Hra skonˇc´ı po koneˇcn´em poˇctu tah˚ u bez ohledu na zahr´av´an´e tahy. Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
7 / 51
P-stavy a N-stavy
V anal´yze naˇs´ı jednoduch´e hry na u ´vod jsem odvodili, ˇze 0,4,8,. . . ,20 jsou stavy, v nichˇz vyhr´av´a Pˇredchoz´ı hr´aˇc (tj. hr´aˇc, kter´y sv´ym tahem hru do tohoto stavu dovedl). V ostatn´ıch stavech vyhr´av´a N´asleduj´ıc´ı hr´aˇc.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
8 / 51
P-stavy a N-stavy
V anal´yze naˇs´ı jednoduch´e hry na u ´vod jsem odvodili, ˇze 0,4,8,. . . ,20 jsou stavy, v nichˇz vyhr´av´a Pˇredchoz´ı hr´aˇc (tj. hr´aˇc, kter´y sv´ym tahem hru do tohoto stavu dovedl). V ostatn´ıch stavech vyhr´av´a N´asleduj´ıc´ı hr´aˇc. P-stavy a N-stavy se daj´ı u n´ami studovan´ych kombinatorick´ych her odvodit podle n´asleduj´ıc´ıho (induktivn´ıho) postupu: Krok 1 Vˇsechny koncov´e stavy oznaˇc jako P-stavy (v pˇr´ıpadˇe mis`ere jako N-stavy).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
8 / 51
P-stavy a N-stavy
V anal´yze naˇs´ı jednoduch´e hry na u ´vod jsem odvodili, ˇze 0,4,8,. . . ,20 jsou stavy, v nichˇz vyhr´av´a Pˇredchoz´ı hr´aˇc (tj. hr´aˇc, kter´y sv´ym tahem hru do tohoto stavu dovedl). V ostatn´ıch stavech vyhr´av´a N´asleduj´ıc´ı hr´aˇc. P-stavy a N-stavy se daj´ı u n´ami studovan´ych kombinatorick´ych her odvodit podle n´asleduj´ıc´ıho (induktivn´ıho) postupu: Krok 1 Vˇsechny koncov´e stavy oznaˇc jako P-stavy (v pˇr´ıpadˇe mis`ere jako N-stavy). Krok 2 Vˇsechny stavy, z nichˇz existuje tah do P-stavu, oznaˇc jako N-stavy.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
8 / 51
P-stavy a N-stavy
V anal´yze naˇs´ı jednoduch´e hry na u ´vod jsem odvodili, ˇze 0,4,8,. . . ,20 jsou stavy, v nichˇz vyhr´av´a Pˇredchoz´ı hr´aˇc (tj. hr´aˇc, kter´y sv´ym tahem hru do tohoto stavu dovedl). V ostatn´ıch stavech vyhr´av´a N´asleduj´ıc´ı hr´aˇc. P-stavy a N-stavy se daj´ı u n´ami studovan´ych kombinatorick´ych her odvodit podle n´asleduj´ıc´ıho (induktivn´ıho) postupu: Krok 1 Vˇsechny koncov´e stavy oznaˇc jako P-stavy (v pˇr´ıpadˇe mis`ere jako N-stavy). Krok 2 Vˇsechny stavy, z nichˇz existuje tah do P-stavu, oznaˇc jako N-stavy. Krok 3 Oznaˇc jako P-stav takov´y stav, z nˇejˇz vˇsechny moˇzn´e tahy vedou do N-stav˚ u.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
8 / 51
Pl´an pˇredn´aˇsky
1
Hry na odeb´ır´an´ı kamen˚ u
2
Nim
3
Hry na grafech
4
Souˇcty her
5
Dalˇs´ı hry ˇreˇsiteln´e pomoc´ı SG-funkce Hry Take-and-Break Ot´aˇcen´ı minc´ı Dvourozmˇern´e ot´aˇcen´ı minc´ı a nim-souˇcin
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
9 / 51
Nejzn´amˇejˇs´ı odeb´ırac´ı hrou je Nim. V klasick´e variantˇe se hraje se tˇremi hrom´adkami kamen˚ u (napˇr. 5,7 a 9 kamen˚ u). Tah spoˇc´ıv´a ve v´ybˇeru hrom´adky a odebr´an´ı libovoln´eho (ale nenulov´eho) poˇctu kamen˚ u z t´eto hrom´adky. V´ıtˇez´ı hr´aˇc, kter´y odebere posledn´ı k´amen.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
10 / 51
Nejzn´amˇejˇs´ı odeb´ırac´ı hrou je Nim. V klasick´e variantˇe se hraje se tˇremi hrom´adkami kamen˚ u (napˇr. 5,7 a 9 kamen˚ u). Tah spoˇc´ıv´a ve v´ybˇeru hrom´adky a odebr´an´ı libovoln´eho (ale nenulov´eho) poˇctu kamen˚ u z t´eto hrom´adky. V´ıtˇez´ı hr´aˇc, kter´y odebere posledn´ı k´amen.
Pˇr´ıklad Hru je moˇzn´e si vyzkouˇset na adrese http://www.chlond.demon.co.uk/Nim.html (lok´alnˇe: zde)
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
10 / 51
Nejzn´amˇejˇs´ı odeb´ırac´ı hrou je Nim. V klasick´e variantˇe se hraje se tˇremi hrom´adkami kamen˚ u (napˇr. 5,7 a 9 kamen˚ u). Tah spoˇc´ıv´a ve v´ybˇeru hrom´adky a odebr´an´ı libovoln´eho (ale nenulov´eho) poˇctu kamen˚ u z t´eto hrom´adky. V´ıtˇez´ı hr´aˇc, kter´y odebere posledn´ı k´amen.
Pˇr´ıklad Hru je moˇzn´e si vyzkouˇset na adrese http://www.chlond.demon.co.uk/Nim.html (lok´alnˇe: zde)
Prvn´ı anal´yza Jedin´y koncov´y stav je (0,0,0). Stavy s jedinou nepr´azdnou hrom´adkou jsou zˇrejmˇe N-stavy. (Tweedledum-Tweedledee strategie) Pˇri dvou nepr´azdn´ych hrom´adk´ach jsou P-stavy pr´avˇe ty stavy, v nichˇz obˇe hrom´adky maj´ı stejn´y poˇcet kamen˚ u. N-stavy: (1,1,1), (1,1,2), (1,1,3), (1,2,2); P-stav: (1,2,3). Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
10 / 51
Jak poznat P- a N-stavy jednoduˇseji? Induktivn´ı metoda popsan´a dˇr´ıve sice vede k ˇreˇsen´ı, ale zjistit s jej´ı pomoc´ı, jestli je napˇr. stav (16,27,32) P-stavem je bez pomoci poˇc´ıtaˇce obt´ıˇzn´e. Existuje pˇritom velmi elegantn´ı zp˚ usob nejen pro to, jak urˇcit P- a N-stavy, ale z´aroveˇ n na urˇcen´ı v´ıtˇezn´e strategie (tj. n´avod na urˇcen´ı tahu, kter´y vede z dan´eho N-stavu do P-stavu).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
11 / 51
Jak poznat P- a N-stavy jednoduˇseji? Induktivn´ı metoda popsan´a dˇr´ıve sice vede k ˇreˇsen´ı, ale zjistit s jej´ı pomoc´ı, jestli je napˇr. stav (16,27,32) P-stavem je bez pomoci poˇc´ıtaˇce obt´ıˇzn´e. Existuje pˇritom velmi elegantn´ı zp˚ usob nejen pro to, jak urˇcit P- a N-stavy, ale z´aroveˇ n na urˇcen´ı v´ıtˇezn´e strategie (tj. n´avod na urˇcen´ı tahu, kter´y vede z dan´eho N-stavu do P-stavu). Tato metoda je zaloˇzena na z´apisu pˇrirozen´ych ˇc´ısel ve dvojkov´e soustavˇe (tzv. bin´arn´ım z´apisu) a na operaci XOR (sˇc´ıt´an´ı ve dvojkov´e soustavˇe bez pˇrenosu).
Definice (Nim-souˇcet) Nim-souˇctem ˇc´ısel x = (xm . . . x0 )2 a y = (ym . . . y0 )2 je ˇc´ıslo x ⊕ y = z = (zm . . . z0 )2 , kde zk = xk + yk mod 2, pro k = 0, . . . , m.
Pˇr´ıklad 16 ⊕ 27 = (10000)2 ⊕ (11011)2 = (01011)2 = 11.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
11 / 51
Pozn´amka (Algebraick´a) Nim-souˇcet je na mnoˇzinˇe nez´aporn´ych cel´ych ˇc´ısel komutativn´ı a asociativn´ı, 0 je vzhledem k t´eto operaci neutr´aln´ı prvek (0 ⊕ x = x) a kaˇzd´y prvek je s´am k sobˇe opaˇcn´y (x ⊕ x = 0). (N0 , ⊕) je tedy komutativn´ı grupa, kde plat´ı tzv. z´akony o kr´acen´ı: x ⊕ y = x ⊕ z =⇒ y = z.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
12 / 51
Pozn´amka (Algebraick´a) Nim-souˇcet je na mnoˇzinˇe nez´aporn´ych cel´ych ˇc´ısel komutativn´ı a asociativn´ı, 0 je vzhledem k t´eto operaci neutr´aln´ı prvek (0 ⊕ x = x) a kaˇzd´y prvek je s´am k sobˇe opaˇcn´y (x ⊕ x = 0). (N0 , ⊕) je tedy komutativn´ı grupa, kde plat´ı tzv. z´akony o kr´acen´ı: x ⊕ y = x ⊕ z =⇒ y = z.
Vˇeta (Bouton, 1902) Stav (x, y , z) v Nimu je P-stavem pr´avˇe tehdy, kdyˇz plat´ı x ⊕ y ⊕ z = 0.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
12 / 51
Pozn´amka (Algebraick´a) Nim-souˇcet je na mnoˇzinˇe nez´aporn´ych cel´ych ˇc´ısel komutativn´ı a asociativn´ı, 0 je vzhledem k t´eto operaci neutr´aln´ı prvek (0 ⊕ x = x) a kaˇzd´y prvek je s´am k sobˇe opaˇcn´y (x ⊕ x = 0). (N0 , ⊕) je tedy komutativn´ı grupa, kde plat´ı tzv. z´akony o kr´acen´ı: x ⊕ y = x ⊕ z =⇒ y = z.
Vˇeta (Bouton, 1902) Stav (x, y , z) v Nimu je P-stavem pr´avˇe tehdy, kdyˇz plat´ı x ⊕ y ⊕ z = 0.
Pˇr´ıklad Protoˇze je 16 ⊕ 27 ⊕ 32 = (10000)2 ⊕ (11011)2 ⊕ (100000)2 = (01011)2 ⊕ (100000)2 = (101011)2 = 43, je (16, 27, 32) N-pozic´ı.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
12 / 51
Jak naj´ıt v´ıtˇezn´y tah? To, ˇze v´ıme, ˇze je nˇejak´a pozice pro n´as v´ıtˇezn´a, je sice pˇekn´e, my bychom ale chtˇeli vˇedˇet, jak´y tah zahr´at, abychom se t´eto v´yhody nezbavili.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
13 / 51
Jak naj´ıt v´ıtˇezn´y tah? To, ˇze v´ıme, ˇze je nˇejak´a pozice pro n´as v´ıtˇezn´a, je sice pˇekn´e, my bychom ale chtˇeli vˇedˇet, jak´y tah zahr´at, abychom se t´eto v´yhody nezbavili. K tomu si staˇc´ı uvˇedomit, co vlastnˇe Boutonova vˇeta ˇr´ık´a – P-stav je takov´y stav, ˇze kdyˇz zap´ıˇseme poˇcty kamen˚ u bin´arnˇe pod sebe, tak v kaˇzd´em sloupci bude sud´y poˇcet jedniˇcek. Je pomˇernˇe snadno vidˇet, jak v takov´em z´apisu dospˇet z N-stavu do P-stavu: 16 = 27 = 32 =
Michal Bulant (PˇrF MU)
0 0 1 1
1 1 0 0
0 1 0 1
0 0 0 0
Kombinatorick´ e hry
0 1 0 1
0 1 0 1
2. 9. 2008
13 / 51
Jak naj´ıt v´ıtˇezn´y tah? To, ˇze v´ıme, ˇze je nˇejak´a pozice pro n´as v´ıtˇezn´a, je sice pˇekn´e, my bychom ale chtˇeli vˇedˇet, jak´y tah zahr´at, abychom se t´eto v´yhody nezbavili. K tomu si staˇc´ı uvˇedomit, co vlastnˇe Boutonova vˇeta ˇr´ık´a – P-stav je takov´y stav, ˇze kdyˇz zap´ıˇseme poˇcty kamen˚ u bin´arnˇe pod sebe, tak v kaˇzd´em sloupci bude sud´y poˇcet jedniˇcek. Je pomˇernˇe snadno vidˇet, jak v takov´em z´apisu dospˇet z N-stavu do P-stavu: 16 = 27 =
Michal Bulant (PˇrF MU)
0 0 0 0
1 1 0 0
0 1 1 0
0 0 0 0
Kombinatorick´ e hry
0 1 1 0
0 1 1 0
2. 9. 2008
13 / 51
Jak naj´ıt v´ıtˇezn´y tah? To, ˇze v´ıme, ˇze je nˇejak´a pozice pro n´as v´ıtˇezn´a, je sice pˇekn´e, my bychom ale chtˇeli vˇedˇet, jak´y tah zahr´at, abychom se t´eto v´yhody nezbavili. K tomu si staˇc´ı uvˇedomit, co vlastnˇe Boutonova vˇeta ˇr´ık´a – P-stav je takov´y stav, ˇze kdyˇz zap´ıˇseme poˇcty kamen˚ u bin´arnˇe pod sebe, tak v kaˇzd´em sloupci bude sud´y poˇcet jedniˇcek. Je pomˇernˇe snadno vidˇet, jak v takov´em z´apisu dospˇet z N-stavu do P-stavu: 16 = 27 = 11 =
0 0 0 0
1 1 0 0
0 1 1 0
0 0 0 0
0 1 1 0
0 1 1 0
Protoˇze odeb´ır´an´ım kamen˚ u ˇc´ısla zmenˇsujeme, je tˇreba uv´aˇzit nejlevˇejˇs´ı sloupec, kde je lich´y poˇcet jedniˇcek a zmenˇsit nˇekter´e z ˇc´ısel, maj´ıc´ıch v tomto sloupci jedniˇcku (v naˇsem pˇr´ıpadˇe nem´ame na v´ybˇer), a toto ˇc´ıslo zmenˇsit tak, aby poˇcty jedniˇcek ve vˇsech sloupc´ıch byly sud´e – to je zˇrejmˇe vˇzdy moˇzn´e (za pˇredpokladu, ˇze je nim-souˇcet nenulov´y). Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
13 / 51
D˚ ukaz Boutonovy vˇety
Nim s jednou hrom´adkou je trivi´aln´ı,
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
14 / 51
D˚ ukaz Boutonovy vˇety
Nim s jednou hrom´adkou je trivi´aln´ı, se dvˇema snadn´y (Tweedledum-Tweedledee),
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
14 / 51
D˚ ukaz Boutonovy vˇety
Nim s jednou hrom´adkou je trivi´aln´ı, se dvˇema snadn´y (Tweedledum-Tweedledee), se tˇremi uˇz mnohem obt´ıˇznˇejˇs´ı.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
14 / 51
D˚ ukaz Boutonovy vˇety
Nim s jednou hrom´adkou je trivi´aln´ı, se dvˇema snadn´y (Tweedledum-Tweedledee), se tˇremi uˇz mnohem obt´ıˇznˇejˇs´ı. Co kdyˇz pˇrid´ame jeˇstˇe dalˇs´ı hrom´adky? Moˇzn´a pˇrekvapivˇe je situace stejn´a jako v pˇr´ıpadˇe tˇr´ı hrom´adek (a vlastnˇe i v pˇr´ıpadˇe jedn´e a dvou hrom´adek) – dan´y stav je P-stavem, pr´avˇe kdyˇz je nim-souˇcet poˇctu kamen˚ u v jednotliv´ych hrom´adk´ach roven 0.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
14 / 51
D˚ ukaz tohoto tvrzen´ı je pomˇernˇe snadn´y a vych´az´ı z rekurz´ıvn´ı definice P-stav˚ u a N-stav˚ u.
D˚ ukaz obecn´e Boutonovy vˇety. Krok 1 Vˇsechny koncov´e stavy (z definice P-stavy) maj´ı nim-souˇcet roven 0 (vˇzdyt’ m´ame jedin´y koncov´y stav (0, 0, . . . , 0), kter´y splˇ nuje 0 ⊕ · · · ⊕ 0 = 0. Krok 2 Z kaˇzd´eho stavu s nenulov´ym nim-souˇctem existuje tah do stavu s nulov´ym nim-souˇctem (viz pˇredchoz´ı pˇr´ıklad). Krok 3 Kaˇzd´y tah ze stavu s nulov´ym nim-souˇctem vede do stavu s nenulov´ym nim-souˇctem: kdyby pro tah (x, y , z, ...) → (x 0 , y , z), kde x 0 < x, platilo x ⊕ y ⊕ z ⊕ · · · = 0 = x 0 ⊕ y ⊕ z ⊕ · · · , pak d´ıky pravidlu o kr´acen´ı dost´av´ame x = x 0 . Proto je mnoˇzina stav˚ u s nulov´ym nim-souˇctem pr´avˇe mnoˇzinou P-stav˚ u.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
15 / 51
D˚ ukaz tohoto tvrzen´ı je pomˇernˇe snadn´y a vych´az´ı z rekurz´ıvn´ı definice P-stav˚ u a N-stav˚ u.
D˚ ukaz obecn´e Boutonovy vˇety. Krok 1 Vˇsechny koncov´e stavy (z definice P-stavy) maj´ı nim-souˇcet roven 0 (vˇzdyt’ m´ame jedin´y koncov´y stav (0, 0, . . . , 0), kter´y splˇ nuje 0 ⊕ · · · ⊕ 0 = 0. Krok 2 Z kaˇzd´eho stavu s nenulov´ym nim-souˇctem existuje tah do stavu s nulov´ym nim-souˇctem (viz pˇredchoz´ı pˇr´ıklad). Krok 3 Kaˇzd´y tah ze stavu s nulov´ym nim-souˇctem vede do stavu s nenulov´ym nim-souˇctem: kdyby pro tah (x, y , z, ...) → (x 0 , y , z), kde x 0 < x, platilo x ⊕ y ⊕ z ⊕ · · · = 0 = x 0 ⊕ y ⊕ z ⊕ · · · , pak d´ıky pravidlu o kr´acen´ı dost´av´ame x = x 0 . Proto je mnoˇzina stav˚ u s nulov´ym nim-souˇctem pr´avˇe mnoˇzinou P-stav˚ u. Z´aroveˇ n je vidˇet, ˇze poˇcet v´ıtˇezn´ych tah˚ u z N-stavu do nˇekter´eho P-stavu je pˇresnˇe roven poˇctu jedniˇcek v nejlevˇejˇs´ım sloupci s lich´ym poˇctem jedniˇcek (speci´alnˇe, poˇcet v´ıtˇezn´ych tah˚ u je vˇzdy lich´y!). Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
15 / 51
Mis`ere Nim
Pokud hrajeme nuznou hru, kdy hr´aˇc, kter´y t´ahne naposled, prohr´av´a, je situace ˇcasto o dost obt´ıˇznˇejˇs´ı. [Wiki] pˇritom uv´ad´ı, ˇze Nim se obvykle hraje pr´avˇe ve sv´e mis`ere variantˇe. Zkuste si rozmyslet, jak´e jsou P-stavy a N-stavy v nuzn´e hˇre, kdy koneˇcn´y stav je N-stavem a jak hr´at v N-stavech, abyste si zaruˇcili v´yhru.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
16 / 51
Mis`ere Nim
Pokud hrajeme nuznou hru, kdy hr´aˇc, kter´y t´ahne naposled, prohr´av´a, je situace ˇcasto o dost obt´ıˇznˇejˇs´ı. [Wiki] pˇritom uv´ad´ı, ˇze Nim se obvykle hraje pr´avˇe ve sv´e mis`ere variantˇe. Zkuste si rozmyslet, jak´e jsou P-stavy a N-stavy v nuzn´e hˇre, kdy koneˇcn´y stav je N-stavem a jak hr´at v N-stavech, abyste si zaruˇcili v´yhru. Hraje se stejnˇe jako v pˇr´ıpadˇe norm´aln´ı hry, dokud je alespoˇ n na dvou hrom´adk´ach v´ıce neˇz jeden k´amen. V situaci, kdy soupeˇr˚ uv tah pˇrivede hru do stavu, kdy je pr´avˇe na jedn´e hrom´adce v´ıce neˇz jeden k´amen, vezmˇete z t´eto hrom´adky tolik kamen˚ u, aby poˇcet hrom´adek s pr´avˇe jedn´ım kamenem byl lich´y.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
16 / 51
Nimu podobn´e hry Nimble Hraje se na p´asu ˇctvereˇck˚ u, oˇcislovan´em 0,1,2,. . . . Na kaˇzd´em ˇctvereˇcku mohou b´yt poloˇzeny mince (ˇz´adn´a, jedna i v´ıce). Tah spoˇc´ıv´a v pˇresunut´ı jedn´e mince na nˇekter´y ˇcvereˇcek s niˇzˇs´ım ˇc´ıslem (lze i pokud jiˇz na nˇem nˇejak´e mince jsou). Koncov´y stav je ve chv´ıli, kdy jsou vˇsechny mince na ˇctvereˇcku s ˇc´ıselm 0, hr´aˇc, kter´y t´ahl posledn´ı, vyhr´av´a.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
17 / 51
Nimu podobn´e hry Nimble Hraje se na p´asu ˇctvereˇck˚ u, oˇcislovan´em 0,1,2,. . . . Na kaˇzd´em ˇctvereˇcku mohou b´yt poloˇzeny mince (ˇz´adn´a, jedna i v´ıce). Tah spoˇc´ıv´a v pˇresunut´ı jedn´e mince na nˇekter´y ˇcvereˇcek s niˇzˇs´ım ˇc´ıslem (lze i pokud jiˇz na nˇem nˇejak´e mince jsou). Koncov´y stav je ve chv´ıli, kdy jsou vˇsechny mince na ˇctvereˇcku s ˇc´ıselm 0, hr´aˇc, kter´y t´ahl posledn´ı, vyhr´av´a.
Pˇrevracen´ı ˇzelv (Turning turtles) Mince jsou n´ahodnˇe poskl´ad´any do ˇrady, nˇekter´e z nich vzh˚ uru l´ıcem, jin´e rubem. Tak spoˇc´ıv´a v otoˇcen´ı nˇekter´e mince z l´ıce na rub a volitelnˇe v otoˇcen´ı jin´e mince vlevo od prvn´ı (z l´ıce na rub nebo z rubu na l´ıc). Vyhr´av´a hr´aˇc, kter´y na konci sv´eho tahu dos´ahne stavu, ˇze jsou vˇsechny mince otoˇceny rubem vzh˚ uru. Hru si m˚ uˇzete zahr´at na http://www.chlond.demon.co.uk/Coins.html (lok´alnˇe zde).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
17 / 51
Nimu podobn´e hry Nimble Hraje se na p´asu ˇctvereˇck˚ u, oˇcislovan´em 0,1,2,. . . . Na kaˇzd´em ˇctvereˇcku mohou b´yt poloˇzeny mince (ˇz´adn´a, jedna i v´ıce). Tah spoˇc´ıv´a v pˇresunut´ı jedn´e mince na nˇekter´y ˇcvereˇcek s niˇzˇs´ım ˇc´ıslem (lze i pokud jiˇz na nˇem nˇejak´e mince jsou). Koncov´y stav je ve chv´ıli, kdy jsou vˇsechny mince na ˇctvereˇcku s ˇc´ıselm 0, hr´aˇc, kter´y t´ahl posledn´ı, vyhr´av´a.
Pˇrevracen´ı ˇzelv (Turning turtles) Mince jsou n´ahodnˇe poskl´ad´any do ˇrady, nˇekter´e z nich vzh˚ uru l´ıcem, jin´e rubem. Tak spoˇc´ıv´a v otoˇcen´ı nˇekter´e mince z l´ıce na rub a volitelnˇe v otoˇcen´ı jin´e mince vlevo od prvn´ı (z l´ıce na rub nebo z rubu na l´ıc). Vyhr´av´a hr´aˇc, kter´y na konci sv´eho tahu dos´ahne stavu, ˇze jsou vˇsechny mince otoˇceny rubem vzh˚ uru. Hru si m˚ uˇzete zahr´at na http://www.chlond.demon.co.uk/Coins.html (lok´alnˇe zde). Obˇe hry se snadno pˇrevedou na klasick´y Nim (promyslete!). Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
17 / 51
Nimu podobn´e hry Moore˚ uv Nim Nimk se hraje stejnˇe jako klasick´y Nim s t´ım rozd´ılem, ˇze hr´aˇc ve sv´em tahu odeb´ır´a kameny z libovoln´ych k hrom´adek (z kaˇzd´e hrom´adky m˚ uˇze odebrat jin´y poˇcet kamen˚ u, pˇr´ıpadnˇe neodebrat ˇz´adn´y), pˇritom mus´ı celkovˇe odebrat alespoˇ n jeden k´amen. Je vidˇet, ˇze Nim1 je klasick´y Nim.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
18 / 51
Nimu podobn´e hry Moore˚ uv Nim Nimk se hraje stejnˇe jako klasick´y Nim s t´ım rozd´ılem, ˇze hr´aˇc ve sv´em tahu odeb´ır´a kameny z libovoln´ych k hrom´adek (z kaˇzd´e hrom´adky m˚ uˇze odebrat jin´y poˇcet kamen˚ u, pˇr´ıpadnˇe neodebrat ˇz´adn´y), pˇritom mus´ı celkovˇe odebrat alespoˇ n jeden k´amen. Je vidˇet, ˇze Nim1 je klasick´y Nim.
Vˇeta (Moore, 1910) Stav (x, y , z, . . .) je v Nimk P-stav, pr´avˇe kdyˇz je poˇcet jedniˇcek na vˇsech m´ıstech bin´arn´ıho z´apisu ˇc´ısel x, y , z,. . . n´asobkem k + 1 (tj. x, y , z zap´ıˇseme bin´arnˇe a sˇc´ıt´ame bez pˇrenosu v v soustavˇe o z´akladu k + 1).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
18 / 51
Nimu podobn´e hry Moore˚ uv Nim Nimk se hraje stejnˇe jako klasick´y Nim s t´ım rozd´ılem, ˇze hr´aˇc ve sv´em tahu odeb´ır´a kameny z libovoln´ych k hrom´adek (z kaˇzd´e hrom´adky m˚ uˇze odebrat jin´y poˇcet kamen˚ u, pˇr´ıpadnˇe neodebrat ˇz´adn´y), pˇritom mus´ı celkovˇe odebrat alespoˇ n jeden k´amen. Je vidˇet, ˇze Nim1 je klasick´y Nim.
Vˇeta (Moore, 1910) Stav (x, y , z, . . .) je v Nimk P-stav, pr´avˇe kdyˇz je poˇcet jedniˇcek na vˇsech m´ıstech bin´arn´ıho z´apisu ˇc´ısel x, y , z,. . . n´asobkem k + 1 (tj. x, y , z zap´ıˇseme bin´arnˇe a sˇc´ıt´ame bez pˇrenosu v v soustavˇe o z´akladu k + 1).
Pˇr´ıklad (Northcottova hra) Hraje se na ˇsachovnici s b´ıl´ymi a ˇcern´ymi pˇeˇsci, kteˇr´ı t´ahnou ve sloupc´ıch vpˇred i vzad (bez pˇreskakov´an´ı). Kdo nem˚ uˇze t´ahnout prohr´av´a.a a
Vˇsimnˇete si, ˇze ze nejde o nestrannou hru!
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
18 / 51
Pl´an pˇredn´aˇsky
1
Hry na odeb´ır´an´ı kamen˚ u
2
Nim
3
Hry na grafech
4
Souˇcty her
5
Dalˇs´ı hry ˇreˇsiteln´e pomoc´ı SG-funkce Hry Take-and-Break Ot´aˇcen´ı minc´ı Dvourozmˇern´e ot´aˇcen´ı minc´ı a nim-souˇcin
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
19 / 51
Uˇz pˇri pˇredchoz´ım uvaˇzov´an´ı o kombinatorick´ych hr´ach bylo vidˇet, ˇze prov´adˇen´e myˇslenky se daj´ı docela dobˇre reprezentovat pomoc´ı tzv. orientovan´ ych graf˚ u, kde jednotliv´e stavy hry jsou reprezentov´any vrcholy a tahy mezi tˇemito stavy tvoˇr´ı (orientovan´e) hrany. Zkoum´an´ı her na orientovan´ych grafech n´am umoˇzn´ı o jednotliv´ych stavech hry ˇr´ıci v´ıce neˇz jen to, jestli jde o P-stav nebo N-stav.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
20 / 51
Uˇz pˇri pˇredchoz´ım uvaˇzov´an´ı o kombinatorick´ych hr´ach bylo vidˇet, ˇze prov´adˇen´e myˇslenky se daj´ı docela dobˇre reprezentovat pomoc´ı tzv. orientovan´ ych graf˚ u, kde jednotliv´e stavy hry jsou reprezentov´any vrcholy a tahy mezi tˇemito stavy tvoˇr´ı (orientovan´e) hrany. Zkoum´an´ı her na orientovan´ych grafech n´am umoˇzn´ı o jednotliv´ych stavech hry ˇr´ıci v´ıce neˇz jen to, jestli jde o P-stav nebo N-stav.
Definice Orientovan´ y graf je dvojice G = (V , F ), kde V je nepr´azdn´a mnoˇzina vrchol˚ u (stav˚ u) a F je zobrazen´ı, kter´e kaˇzd´emu vrcholu v ∈ V pˇriˇrad´ı podmnoˇzinu F (v ) ⊆ H. Pro dan´e v je F (v ) mnoˇzinou n´asledn´ık˚ u v , tj. vrchol˚ u, do nichˇz se lze dostat jedn´ım tahem z v . Je-li F (v ) = ∅, naz´yv´a se stav v koncov´y.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
20 / 51
Uˇz pˇri pˇredchoz´ım uvaˇzov´an´ı o kombinatorick´ych hr´ach bylo vidˇet, ˇze prov´adˇen´e myˇslenky se daj´ı docela dobˇre reprezentovat pomoc´ı tzv. orientovan´ ych graf˚ u, kde jednotliv´e stavy hry jsou reprezentov´any vrcholy a tahy mezi tˇemito stavy tvoˇr´ı (orientovan´e) hrany. Zkoum´an´ı her na orientovan´ych grafech n´am umoˇzn´ı o jednotliv´ych stavech hry ˇr´ıci v´ıce neˇz jen to, jestli jde o P-stav nebo N-stav.
Definice Orientovan´ y graf je dvojice G = (V , F ), kde V je nepr´azdn´a mnoˇzina vrchol˚ u (stav˚ u) a F je zobrazen´ı, kter´e kaˇzd´emu vrcholu v ∈ V pˇriˇrad´ı podmnoˇzinu F (v ) ⊆ H. Pro dan´e v je F (v ) mnoˇzinou n´asledn´ık˚ u v , tj. vrchol˚ u, do nichˇz se lze dostat jedn´ım tahem z v . Je-li F (v ) = ∅, naz´yv´a se stav v koncov´y. Hra na grafu G m´a n´asleduj´ıc´ı pravidla: 1. hr´aˇc zaˇc´ın´a v pˇredem urˇcen´em stavu v0 a hr´aˇci se ve sv´ych taz´ıch stˇr´ıdaj´ı. Ve stavu v vol´ı hr´aˇc, kter´y je na tahu, dalˇs´ı stav z mnoˇziny F (v ). Prohr´av´a hr´aˇc, kter´y je na tahu ve stavu v , kde F (v ) = ∅. Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
20 / 51
Sprague-Grundyho funkce Grafov´e hry mohou b´yt zkoum´any analogicky jako Nim prostˇrednictv´ım Pa N-stav˚ u. Uk´aˇzeme si ale i jin´y, obecnˇejˇs´ı postup pomoc´ı tzv. Sprague-Grundyho funkce.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
21 / 51
Sprague-Grundyho funkce Grafov´e hry mohou b´yt zkoum´any analogicky jako Nim prostˇrednictv´ım Pa N-stav˚ u. Uk´aˇzeme si ale i jin´y, obecnˇejˇs´ı postup pomoc´ı tzv. Sprague-Grundyho funkce.
Definice (SG-funkce, SG-hodnota) Sprague-Grundyho funkce grafu G = (V , F ) je funkce g : V → N0 definovan´a rekurz´ıvnˇe pˇredpisem g (v ) = min{n ∈ N0 : n 6= g (u) pro vˇsechna u ∈ F (v )}. Alternativnˇe, s vyuˇzit´ım funkce mex (minimal excludant=nejmenˇs´ı vylouˇcen´y; v´ysledkem je nejmenˇs´ı nez´aporn´e cel´e ˇc´ıslo neobsaˇzen´e v argumentu funkce) m˚ uˇzeme u ´spornˇeji ps´at g (v ) = mex{g (u) : u ∈ F (v )}.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
21 / 51
Anal´yza her pomoc´ı SG-funkce Uk´aˇzeme, ˇze P-stavy jsou pr´avˇe stavy s SG-hodnotou 0. Krok 1 Kaˇzd´y koncov´y stav hodnotu SG-funkce rovnou 0. Krok 2 Je-li g (v ) = 0, pak pro kaˇzd´e u ∈ F (v ) plat´ı g (u) > 0. Krok 3 Je-li g (v ) > 0, pak nutnˇe existuje u ∈ F (v ), pro nˇeˇz plat´ı g (u) = 0.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
22 / 51
Anal´yza her pomoc´ı SG-funkce Uk´aˇzeme, ˇze P-stavy jsou pr´avˇe stavy s SG-hodnotou 0. Krok 1 Kaˇzd´y koncov´y stav hodnotu SG-funkce rovnou 0. Krok 2 Je-li g (v ) = 0, pak pro kaˇzd´e u ∈ F (v ) plat´ı g (u) > 0. Krok 3 Je-li g (v ) > 0, pak nutnˇe existuje u ∈ F (v ), pro nˇeˇz plat´ı g (u) = 0. Zd´a se, ˇze pojem SG-funkce je ekvivalentn´ı anal´yze P- a N-stav˚ u, ale brzy si uk´aˇzeme, ˇze konkr´etn´ı hodnota SG-funkce je v´yznamnou pˇridanou informac´ı.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
22 / 51
Anal´yza her pomoc´ı SG-funkce Uk´aˇzeme, ˇze P-stavy jsou pr´avˇe stavy s SG-hodnotou 0. Krok 1 Kaˇzd´y koncov´y stav hodnotu SG-funkce rovnou 0. Krok 2 Je-li g (v ) = 0, pak pro kaˇzd´e u ∈ F (v ) plat´ı g (u) > 0. Krok 3 Je-li g (v ) > 0, pak nutnˇe existuje u ∈ F (v ), pro nˇeˇz plat´ı g (u) = 0. Zd´a se, ˇze pojem SG-funkce je ekvivalentn´ı anal´yze P- a N-stav˚ u, ale brzy si uk´aˇzeme, ˇze konkr´etn´ı hodnota SG-funkce je v´yznamnou pˇridanou informac´ı.
Pˇr´ıklad Urˇc´ıme SG-hodnotu stav˚ u v naˇs´ı jednoduch´e odeˇc´ıtac´ı hˇre (21 kamen˚ u, odeb´ır´ame 1,2 nebo 3).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
22 / 51
Anal´yza her pomoc´ı SG-funkce Uk´aˇzeme, ˇze P-stavy jsou pr´avˇe stavy s SG-hodnotou 0. Krok 1 Kaˇzd´y koncov´y stav hodnotu SG-funkce rovnou 0. Krok 2 Je-li g (v ) = 0, pak pro kaˇzd´e u ∈ F (v ) plat´ı g (u) > 0. Krok 3 Je-li g (v ) > 0, pak nutnˇe existuje u ∈ F (v ), pro nˇeˇz plat´ı g (u) = 0. Zd´a se, ˇze pojem SG-funkce je ekvivalentn´ı anal´yze P- a N-stav˚ u, ale brzy si uk´aˇzeme, ˇze konkr´etn´ı hodnota SG-funkce je v´yznamnou pˇridanou informac´ı.
Pˇr´ıklad Urˇc´ıme SG-hodnotu stav˚ u v naˇs´ı jednoduch´e odeˇc´ıtac´ı hˇre (21 kamen˚ u, odeb´ır´ame 1,2 nebo 3). x 0 1 2 3 4 5 6 7 8 9 g (x) 0 1 2 3 0 1 2 3 0 1 Tj. g (x) = x mod 4. Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
22 / 51
Dalˇs´ı pˇr´ıklady her Wythoffova hra Hr´aˇci sed´ıc´ı na stejn´e stranˇe ˇsachovnice stˇr´ıdavˇe t´ahnou s d´amou, t´ahnout mohou pouze ve sloupci dol˚ u, v ˇradˇe doleva nebo diagon´alnˇe ˇsikmo dol˚ u. Hr´aˇc, kter´y t´ahne posledn´ı vyhr´av´a. Hru si m˚ uˇzete zahr´at na http://www.chlond.demon.co.uk/Queen.html (lok´alnˇe zde).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
23 / 51
Dalˇs´ı pˇr´ıklady her Wythoffova hra Hr´aˇci sed´ıc´ı na stejn´e stranˇe ˇsachovnice stˇr´ıdavˇe t´ahnou s d´amou, t´ahnout mohou pouze ve sloupci dol˚ u, v ˇradˇe doleva nebo diagon´alnˇe ˇsikmo dol˚ u. Hr´aˇc, kter´y t´ahne posledn´ı vyhr´av´a. Hru si m˚ uˇzete zahr´at na http://www.chlond.demon.co.uk/Queen.html (lok´alnˇe zde).
Dvourozmˇern´y Nim Hraje se na ˇctvercov´e s´ıti v prvn´ım kvadrantu, kde je rozm´ıstˇen koneˇcn´y poˇcet kamen˚ u (i v´ıce na jednom poli). Tah spoˇc´ıv´a v pˇresunu jednoho ’ kamene bud vlevo ve stejn´em ˇr´adku nebo na libovoln´e pole v nˇekter´em niˇzˇs´ım ˇr´adku.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
23 / 51
Dalˇs´ı pˇr´ıklady her Wythoffova hra Hr´aˇci sed´ıc´ı na stejn´e stranˇe ˇsachovnice stˇr´ıdavˇe t´ahnou s d´amou, t´ahnout mohou pouze ve sloupci dol˚ u, v ˇradˇe doleva nebo diagon´alnˇe ˇsikmo dol˚ u. Hr´aˇc, kter´y t´ahne posledn´ı vyhr´av´a. Hru si m˚ uˇzete zahr´at na http://www.chlond.demon.co.uk/Queen.html (lok´alnˇe zde).
Dvourozmˇern´y Nim Hraje se na ˇctvercov´e s´ıti v prvn´ım kvadrantu, kde je rozm´ıstˇen koneˇcn´y poˇcet kamen˚ u (i v´ıce na jednom poli). Tah spoˇc´ıv´a v pˇresunu jednoho ’ kamene bud vlevo ve stejn´em ˇr´adku nebo na libovoln´e pole v nˇekter´em niˇzˇs´ım ˇr´adku. Zkuste si spoˇc´ıtat Sprague-Grundyho funkce pro tyto hry.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
23 / 51
Pl´an pˇredn´aˇsky
1
Hry na odeb´ır´an´ı kamen˚ u
2
Nim
3
Hry na grafech
4
Souˇcty her
5
Dalˇs´ı hry ˇreˇsiteln´e pomoc´ı SG-funkce Hry Take-and-Break Ot´aˇcen´ı minc´ı Dvourozmˇern´e ot´aˇcen´ı minc´ı a nim-souˇcin
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
24 / 51
Pˇrirozen´ym zp˚ usobem, jak z kombinatorick´ych her vytv´aˇret hry sloˇzitˇejˇs´ı, je tzv. (disjunktn´ı) sˇ c´ıt´ an´ı her. Tah hr´aˇce v souˇctu dan´ych her spoˇc´ıv´a v tom, ˇze zvol´ı jednu z dan´ych her a v n´ı uˇcin´ı sv˚ uj tah. Jako dobr´a ilustrace tohoto pojmu poslouˇz´ı klasick´y tˇr´ıhrom´adkov´y Nim, kter´y je souˇctem 3 (trivi´aln´ıch) jednohrom´adkov´ych Nim˚ u.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
25 / 51
Pˇrirozen´ym zp˚ usobem, jak z kombinatorick´ych her vytv´aˇret hry sloˇzitˇejˇs´ı, je tzv. (disjunktn´ı) sˇ c´ıt´ an´ı her. Tah hr´aˇce v souˇctu dan´ych her spoˇc´ıv´a v tom, ˇze zvol´ı jednu z dan´ych her a v n´ı uˇcin´ı sv˚ uj tah. Jako dobr´a ilustrace tohoto pojmu poslouˇz´ı klasick´y tˇr´ıhrom´adkov´y Nim, kter´y je souˇctem 3 (trivi´aln´ıch) jednohrom´adkov´ych Nim˚ u.
Definice (Souˇcet grafov´ych her) Mˇejme n graf˚ u G1 = (V1 , F1 ), . . . , Gn = (Vn , Fn ). Souˇ ctem G = G1 + · · · + Gn graf˚ u G1 , . . . , Gn nazveme graf G = (V , F ), kde V = V1 × V2 × · · · Vn je mnoˇzina vˇsech n-tic (v1 , . . . , vn ), kde vi ∈ Vi a pro vrchol v = (v1 , . . . , vn ) je mnoˇzina n´asledn´ık˚ u F (v ) =F1 (v1 ) × {v2 } × · · · × {vn }∪ ∪{v1 } × F (v2 ) × · · · × {vn }∪ ··· ∪{v1 } × {v2 } × · · · × F (vn )
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
25 / 51
N´asleduj´ıc´ı vˇeta je v´yznamn´ym zobecnˇen´ım Boutonovy vˇety – ukazuje, ˇze SG-hodnotu stavu v souˇctu graf˚ u dostaneme jako nim-souˇcet SG-hodnot jednotliv´ych komponent.
Vˇeta (Sprague, 1936; Grundy, 1939) Mˇejme grafy G1 , . . . , Gn s SG-funkcemi g1 , . . . , gn . Pak graf G = G1 + G2 + · · · + Gn m´a Sprague-Grundyho funkci g (v1 , . . . , vn ) = g1 (v1 ) ⊕ · · · ⊕ gn (vn ).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
26 / 51
N´asleduj´ıc´ı vˇeta je v´yznamn´ym zobecnˇen´ım Boutonovy vˇety – ukazuje, ˇze SG-hodnotu stavu v souˇctu graf˚ u dostaneme jako nim-souˇcet SG-hodnot jednotliv´ych komponent.
Vˇeta (Sprague, 1936; Grundy, 1939) Mˇejme grafy G1 , . . . , Gn s SG-funkcemi g1 , . . . , gn . Pak graf G = G1 + G2 + · · · + Gn m´a Sprague-Grundyho funkci g (v1 , . . . , vn ) = g1 (v1 ) ⊕ · · · ⊕ gn (vn ). D˚ ukaz t´eto vˇety je podobn´y d˚ ukazu Boutonovy vˇety (zkuste sami!).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
26 / 51
N´asleduj´ıc´ı vˇeta je v´yznamn´ym zobecnˇen´ım Boutonovy vˇety – ukazuje, ˇze SG-hodnotu stavu v souˇctu graf˚ u dostaneme jako nim-souˇcet SG-hodnot jednotliv´ych komponent.
Vˇeta (Sprague, 1936; Grundy, 1939) Mˇejme grafy G1 , . . . , Gn s SG-funkcemi g1 , . . . , gn . Pak graf G = G1 + G2 + · · · + Gn m´a Sprague-Grundyho funkci g (v1 , . . . , vn ) = g1 (v1 ) ⊕ · · · ⊕ gn (vn ). D˚ ukaz t´eto vˇety je podobn´y d˚ ukazu Boutonovy vˇety (zkuste sami!).
Pozn´amka D˚ uleˇzit´ym d˚ usledkem t´eto vˇety je skuteˇcnost, ˇze kaˇzd´a nestrann´a kombinatorick´a hra se jako sˇc´ıtanec v souˇctu her chov´a stejnˇe jako jako hra Nim s jednou hrom´adkou velikosti rovn´e SG-funkci t´eto hry. Jin´ymi slovy: kaˇzd´a nestrann´a hra je ekvivalentn´ı Nimu. Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
26 / 51
Aplikace na r˚ uzn´e hry
Pˇr´ıklad (Souˇcet odeˇc´ıtac´ıch her) Oznaˇcme G (m) tzv. odeˇc´ıtac´ı hru (zobecnˇen´ı naˇs´ı u ´vodn´ı jednoduch´e hry, kdy lze z hrom´adky odeb´ırat 1 aˇz m kamen˚ u).a Snadno je vidˇet, ˇze G (m) m´a SG-funkci rovnou gm (v ) = v mod m + 1. Uvaˇzme hru G = G (3) + G (5) + G (7) s poˇc´ateˇcn´ım stavem (9, 10, 14).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
27 / 51
Aplikace na r˚ uzn´e hry
Pˇr´ıklad (Souˇcet odeˇc´ıtac´ıch her) Oznaˇcme G (m) tzv. odeˇc´ıtac´ı hru (zobecnˇen´ı naˇs´ı u ´vodn´ı jednoduch´e hry, kdy lze z hrom´adky odeb´ırat 1 aˇz m kamen˚ u).a Snadno je vidˇet, ˇze G (m) m´a SG-funkci rovnou gm (v ) = v mod m + 1. Uvaˇzme hru G = G (3) + G (5) + G (7) s poˇc´ateˇcn´ım stavem (9, 10, 14). Snadno vypoˇcteme SG-funkci g ((9, 10, 14)) = g3 (9) ⊕ g5 (10) ⊕ g7 (14) = 1 ⊕ 4 ⊕ 6 = 3. Poˇc´ateˇcn´ı stav je tedy N-stavem. a
Obecnˇe lze v odeˇc´ıtac´ıch hr´ ach odeb´ırat poˇcet kamen˚ u, kter´y je prvkem mnoˇziny S; zde S = {1, . . . , m}.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
27 / 51
Pˇr´ıklad (Souˇcet odeˇc´ıtac´ıch her – pokr.) Podobnˇe jako v Nimu urˇc´ıme v´ıtˇezn´e tahy podle nejlevˇejˇs´ıch jedniˇcek v bin´arn´ım z´apisu, kter´ych je lich´y poˇcet: g3 (9) = 1 = g5 (10) = 4 = g7 (14) = 6 =
Michal Bulant (PˇrF MU)
0 1 1 0
Kombinatorick´ e hry
0 0 1 1
1 0 0 1
2. 9. 2008
28 / 51
Pˇr´ıklad (Souˇcet odeˇc´ıtac´ıch her – pokr.) Podobnˇe jako v Nimu urˇc´ıme v´ıtˇezn´e tahy podle nejlevˇejˇs´ıch jedniˇcek v bin´arn´ım z´apisu, kter´ych je lich´y poˇcet: g3 (9) = 1 = g5 (10) = 4 = 5=
0 1 1 0
0 0 0 0
1 0 1 0
Potˇrebnou hodnotu 5 dos´ahneme odebr´an´ım jednoho kamene ze tˇret´ı hrom´adky, nebot’ pak g7 (13) = 5.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
28 / 51
Pˇr´ıklad (Souˇcet odeˇc´ıtac´ıch her – pokr.) Podobnˇe jako v Nimu urˇc´ıme v´ıtˇezn´e tahy podle nejlevˇejˇs´ıch jedniˇcek v bin´arn´ım z´apisu, kter´ych je lich´y poˇcet: g3 (9) = 1 = g5 (10) = 4 = 5=
0 1 1 0
0 0 0 0
1 0 1 0
Potˇrebnou hodnotu 5 dos´ahneme odebr´an´ım jednoho kamene ze tˇret´ı hrom´adky, nebot’ pak g7 (13) = 5. Je zde ovˇsem oproti Nimu pˇrece jen jeden rozd´ıl – tento optim´aln´ı tah nen´ı jedin´y, protoˇze SG-funkce nemus´ı b´yt nutnˇe monot´ onn´ı (tj. se zmenˇsuj´ıc´ı hodnotou argumentu se nemus´ı nutnˇe zmenˇsovat hodnota SG-funkce) a m˚ uˇzeme tak generovat jedniˇcky i na vyˇsˇs´ıch m´ıstech.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
28 / 51
Pˇr´ıklad (Souˇcet odeˇc´ıtac´ıch her – pokr.) Podobnˇe jako v Nimu urˇc´ıme v´ıtˇezn´e tahy podle nejlevˇejˇs´ıch jedniˇcek v bin´arn´ım z´apisu, kter´ych je lich´y poˇcet: g3 (9) = 1 = g5 (10) = 4 = 5=
0 1 1 0
0 0 0 0
1 0 1 0
Potˇrebnou hodnotu 5 dos´ahneme odebr´an´ım jednoho kamene ze tˇret´ı hrom´adky, nebot’ pak g7 (13) = 5. Je zde ovˇsem oproti Nimu pˇrece jen jeden rozd´ıl – tento optim´aln´ı tah nen´ı jedin´y, protoˇze SG-funkce nemus´ı b´yt nutnˇe monot´ onn´ı (tj. se zmenˇsuj´ıc´ı hodnotou argumentu se nemus´ı nutnˇe zmenˇsovat hodnota SG-funkce) a m˚ uˇzeme tak generovat jedniˇcky i na vyˇsˇs´ıch m´ıstech. Napˇr. zde je dalˇs´ım v´ıtˇezn´ym tahem odebr´an´ı 3 kamen˚ u z prvn´ı hrom´adky, ˇ ’ nebot pak g3 (6) = 2 a 2 ⊕ 4 ⊕ 6 = 0. Z´adn´y tah v druh´e hrom´adce ovˇsem jiˇz v´ıtˇezn´y nen´ı. Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
28 / 51
Pl´an pˇredn´aˇsky
1
Hry na odeb´ır´an´ı kamen˚ u
2
Nim
3
Hry na grafech
4
Souˇcty her
5
Dalˇs´ı hry ˇreˇsiteln´e pomoc´ı SG-funkce Hry Take-and-Break Ot´aˇcen´ı minc´ı Dvourozmˇern´e ot´aˇcen´ı minc´ı a nim-souˇcin
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
29 / 51
Pl´an pˇredn´aˇsky
1
Hry na odeb´ır´an´ı kamen˚ u
2
Nim
3
Hry na grafech
4
Souˇcty her
5
Dalˇs´ı hry ˇreˇsiteln´e pomoc´ı SG-funkce Hry Take-and-Break Ot´aˇcen´ı minc´ı Dvourozmˇern´e ot´aˇcen´ı minc´ı a nim-souˇcin
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
30 / 51
Lasker˚ uv Nim ´ Uprava Nimu na hru typu Vezmi a rozdˇel je d´ılem E. Laskera, ˇsachov´eho mistra svˇeta v letech 1894–1921. V t´eto hˇre je moˇzn´e zahr´at nˇekter´y z tah˚ u: klasick´e odebr´an´ı libovoln´eho poˇctu kamen˚ u z nˇekter´e hrom´adky, rozdˇelen´ı hrom´adky s alespoˇ n dvˇema kameny na dvˇe nepr´azdn´e hrom´adky.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
31 / 51
Lasker˚ uv Nim ´ Uprava Nimu na hru typu Vezmi a rozdˇel je d´ılem E. Laskera, ˇsachov´eho mistra svˇeta v letech 1894–1921. V t´eto hˇre je moˇzn´e zahr´at nˇekter´y z tah˚ u: klasick´e odebr´an´ı libovoln´eho poˇctu kamen˚ u z nˇekter´e hrom´adky, rozdˇelen´ı hrom´adky s alespoˇ n dvˇema kameny na dvˇe nepr´azdn´e hrom´adky. Pomˇernˇe snadno lze indukc´ı dok´azat, ˇze SG-funkce pro Lasker˚ uv Nim s jednou hrom´adkou m´a tvar g (4k+1) = 4k+1, g (4k+2) = 4k+2, g (4k+3) = 4k+4, g (4k+4) = 4k+3 pro k ≥ 0.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
31 / 51
Lasker˚ uv Nim ´ Uprava Nimu na hru typu Vezmi a rozdˇel je d´ılem E. Laskera, ˇsachov´eho mistra svˇeta v letech 1894–1921. V t´eto hˇre je moˇzn´e zahr´at nˇekter´y z tah˚ u: klasick´e odebr´an´ı libovoln´eho poˇctu kamen˚ u z nˇekter´e hrom´adky, rozdˇelen´ı hrom´adky s alespoˇ n dvˇema kameny na dvˇe nepr´azdn´e hrom´adky. Pomˇernˇe snadno lze indukc´ı dok´azat, ˇze SG-funkce pro Lasker˚ uv Nim s jednou hrom´adkou m´a tvar g (4k+1) = 4k+1, g (4k+2) = 4k+2, g (4k+3) = 4k+4, g (4k+4) = 4k+3 pro k ≥ 0.
Pˇr´ıklad Vyzkouˇsejte si Lasker˚ uv Nim s u ´vodn´ım stavem (2, 5, 7).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
31 / 51
Kayles Hra Kayles byla zm´ınˇen H. E. Dudeneyem v The Canterbury puzzles (1958). Dva kuˇzelk´aˇri stoj´ı pˇred ˇradou 13 kuˇzelek, pˇriˇcemˇz druh´a kuˇzelka je jiˇz shozen´a. Oba jsou tak kvalitn´ı, ˇze sv´ym hodem mohou shodit kteroukoliv kuˇzelku nebo dvojici sousedn´ıch kuˇzelek. V´ıtˇezem je hr´aˇc, kter´y shod´ı posledn´ı kuˇzelku.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
32 / 51
Kayles Hra Kayles byla zm´ınˇen H. E. Dudeneyem v The Canterbury puzzles (1958). Dva kuˇzelk´aˇri stoj´ı pˇred ˇradou 13 kuˇzelek, pˇriˇcemˇz druh´a kuˇzelka je jiˇz shozen´a. Oba jsou tak kvalitn´ı, ˇze sv´ym hodem mohou shodit kteroukoliv kuˇzelku nebo dvojici sousedn´ıch kuˇzelek. V´ıtˇezem je hr´aˇc, kter´y shod´ı posledn´ı kuˇzelku. Tato hra se d´a popsat pomoc´ı odeb´ır´an´ı kamen˚ u n´asledovnˇe: tahem je odebr´an´ı jednoho nebo dvou kamen˚ u z jedn´e hrom´adky, kterou je pot´e moˇzno rozdˇelit na dvˇe nepr´azdn´e hrom´adky. Hru si m˚ uˇzete zahr´at na http://www.chlond.demon.co.uk/Kayles.html (lok´alnˇe zde).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
32 / 51
Kayles Hra Kayles byla zm´ınˇen H. E. Dudeneyem v The Canterbury puzzles (1958). Dva kuˇzelk´aˇri stoj´ı pˇred ˇradou 13 kuˇzelek, pˇriˇcemˇz druh´a kuˇzelka je jiˇz shozen´a. Oba jsou tak kvalitn´ı, ˇze sv´ym hodem mohou shodit kteroukoliv kuˇzelku nebo dvojici sousedn´ıch kuˇzelek. V´ıtˇezem je hr´aˇc, kter´y shod´ı posledn´ı kuˇzelku. Tato hra se d´a popsat pomoc´ı odeb´ır´an´ı kamen˚ u n´asledovnˇe: tahem je odebr´an´ı jednoho nebo dvou kamen˚ u z jedn´e hrom´adky, kterou je pot´e moˇzno rozdˇelit na dvˇe nepr´azdn´e hrom´adky. Hru si m˚ uˇzete zahr´at na http://www.chlond.demon.co.uk/Kayles.html (lok´alnˇe zde). Najdˇeme SG-funkci pro hru Kayles, kde u ´vodn´ı stav je hrom´adka s n kameny. Jedin´y koncov´y stav je pr´azdn´a hrom´adka, tedy g (0) = 0. Snadno g (1) = 1 a g (2) = 2. Z hrom´adky se tˇremi kameny m˚ uˇzeme odebrat bud’ 1 nebo 2 kameny (SG:1,2) nebo odebrat jeden k´amen a rozdˇelit na dvˇe hrom´adky (SG:0). Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
32 / 51
Kayles – ˇreˇsen´ı T´ımto postupem dopoˇc´ıt´ame tabulku (x je ˇc´ıslo ˇr´adku, y sloupce) g (12x + y ) 0 1 2 3 4 5 6
Michal Bulant (PˇrF MU)
0 0 4 4 4 4 4 4
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 7 8 3 8 8 8
4 1 1 5 1 1 1 1
5 4 4 4 4 4 4 4
Kombinatorick´ e hry
6 3 3 7 7 7 7 7
7 2 2 2 2 2 2 2
8 1 1 1 1 1 1 1
9 4 4 8 8 4 8 8
10 2 6 6 2 2 6 2
11 6 7 7 7 7 7 7
2. 9. 2008
33 / 51
Kayles – ˇreˇsen´ı T´ımto postupem dopoˇc´ıt´ame tabulku (x je ˇc´ıslo ˇr´adku, y sloupce) g (12x + y ) 0 1 2 3 4 5 6
0 0 4 4 4 4 4 4
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 7 8 3 8 8 8
4 1 1 5 1 1 1 1
5 4 4 4 4 4 4 4
6 3 3 7 7 7 7 7
7 2 2 2 2 2 2 2
8 1 1 1 1 1 1 1
9 4 4 8 8 4 8 8
10 2 6 6 2 2 6 2
11 6 7 7 7 7 7 7
Od hodnoty n = 72 je d´ale funkce g periodick´a s periodou 12, tuˇcnˇe jsou vyznaˇceny v´yjimky oproti hodnot´am v posledn´ım ˇr´adku.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
33 / 51
Kayles – ˇreˇsen´ı T´ımto postupem dopoˇc´ıt´ame tabulku (x je ˇc´ıslo ˇr´adku, y sloupce) g (12x + y ) 0 1 2 3 4 5 6
0 0 4 4 4 4 4 4
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 7 8 3 8 8 8
4 1 1 5 1 1 1 1
5 4 4 4 4 4 4 4
6 3 3 7 7 7 7 7
7 2 2 2 2 2 2 2
8 1 1 1 1 1 1 1
9 4 4 8 8 4 8 8
10 2 6 6 2 2 6 2
11 6 7 7 7 7 7 7
Od hodnoty n = 72 je d´ale funkce g periodick´a s periodou 12, tuˇcnˇe jsou vyznaˇceny v´yjimky oproti hodnot´am v posledn´ım ˇr´adku.
Pˇr´ıklad Vyˇreˇste u ´vodn´ı Dudeneyovu u ´lohu s dvˇema hrom´adkami (1, 11). Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
33 / 51
Pl´an pˇredn´aˇsky
1
Hry na odeb´ır´an´ı kamen˚ u
2
Nim
3
Hry na grafech
4
Souˇcty her
5
Dalˇs´ı hry ˇreˇsiteln´e pomoc´ı SG-funkce Hry Take-and-Break Ot´aˇcen´ı minc´ı Dvourozmˇern´e ot´aˇcen´ı minc´ı a nim-souˇcin
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
34 / 51
Hry s ot´aˇcen´ım minc´ı zobecˇ nuj´ı dˇr´ıve uvedenou hru Ot´aˇcen´ı ˇzelv. V ˇradˇe je koneˇcnˇe mnoho minc´ı otoˇcen´ych vzh˚ uru l´ıcovou ˇci rubovou stranou. Tah spoˇc´ıv´a v otoˇcen´ı minc´ı z nˇejak´e sady podle pravidel konkr´etn´ı hry. Vˇ zdy vˇsak mus´ı b´ yt nejpravˇ ejˇs´ı ot´ aˇ cen´ a mince otoˇ cena z l´ıcov´ e na rubovou stranu (podm´ınka koneˇcnosti hry). To, kter´e mince jsou ot´aˇceny, sm´ı z´aviset pouze na pozici nejpravˇejˇs´ı ot´aˇcen´e mince, nikoli jiˇz na jin´ych pozic´ıch, pˇredchoz´ıch taz´ıch apod.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
35 / 51
Hry s ot´aˇcen´ım minc´ı zobecˇ nuj´ı dˇr´ıve uvedenou hru Ot´aˇcen´ı ˇzelv. V ˇradˇe je koneˇcnˇe mnoho minc´ı otoˇcen´ych vzh˚ uru l´ıcovou ˇci rubovou stranou. Tah spoˇc´ıv´a v otoˇcen´ı minc´ı z nˇejak´e sady podle pravidel konkr´etn´ı hry. Vˇ zdy vˇsak mus´ı b´ yt nejpravˇ ejˇs´ı ot´ aˇ cen´ a mince otoˇ cena z l´ıcov´ e na rubovou stranu (podm´ınka koneˇcnosti hry). To, kter´e mince jsou ot´aˇceny, sm´ı z´aviset pouze na pozici nejpravˇejˇs´ı ot´aˇcen´e mince, nikoli jiˇz na jin´ych pozic´ıch, pˇredchoz´ıch taz´ıch apod. Pro vˇsechny takov´eto hry plat´ı zˇrejmˇe obdobn´y rozklad jako pro Ot´aˇcen´ı ˇzelv – stav s k l´ıci na pozic´ıch v1 , . . . , vk je souˇctem k her, kde v kaˇzd´e hˇre (ˇc´ıslo i) je pr´avˇe jeden l´ıc a to na pozici vi .
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
35 / 51
Hry s ot´aˇcen´ım minc´ı zobecˇ nuj´ı dˇr´ıve uvedenou hru Ot´aˇcen´ı ˇzelv. V ˇradˇe je koneˇcnˇe mnoho minc´ı otoˇcen´ych vzh˚ uru l´ıcovou ˇci rubovou stranou. Tah spoˇc´ıv´a v otoˇcen´ı minc´ı z nˇejak´e sady podle pravidel konkr´etn´ı hry. Vˇ zdy vˇsak mus´ı b´ yt nejpravˇ ejˇs´ı ot´ aˇ cen´ a mince otoˇ cena z l´ıcov´ e na rubovou stranu (podm´ınka koneˇcnosti hry). To, kter´e mince jsou ot´aˇceny, sm´ı z´aviset pouze na pozici nejpravˇejˇs´ı ot´aˇcen´e mince, nikoli jiˇz na jin´ych pozic´ıch, pˇredchoz´ıch taz´ıch apod. Pro vˇsechny takov´eto hry plat´ı zˇrejmˇe obdobn´y rozklad jako pro Ot´aˇcen´ı ˇzelv – stav s k l´ıci na pozic´ıch v1 , . . . , vk je souˇctem k her, kde v kaˇzd´e hˇre (ˇc´ıslo i) je pr´avˇe jeden l´ıc a to na pozici vi . Napˇr. hra RLRRLRL je souˇctem her RL, RRRRL a RRRRRRL, proto pro urˇcen´ı SG-hodnoty obecn´e hry staˇc´ı urˇcit SG-hodnoty her s pr´avˇe jedn´ım l´ıcem.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
35 / 51
Reprezentace her pomoc´ı ot´aˇcen´ı minc´ı Podobnˇe jako lze hry reprezentovat pomoc´ı Nimu, lze ˇcasto hry reprezentovat i pomoc´ı ot´aˇcen´ı minc´ı.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
36 / 51
Reprezentace her pomoc´ı ot´aˇcen´ı minc´ı Podobnˇe jako lze hry reprezentovat pomoc´ı Nimu, lze ˇcasto hry reprezentovat i pomoc´ı ot´aˇcen´ı minc´ı. U nˇekter´ych her je v´yhodnˇejˇs´ı reprezentace pomoc´ı Nimu, u jin´ych je tomu naopak.
Pˇr´ıklad (Jednoduch´a u´vodn´ı odeˇc´ıtac´ı hra) Mˇejme odeˇc´ıtac´ı hru s S = {1, 2, 3}. Hru reprezentujeme pomoc´ı n minc´ı oˇc´ıslovan´ych od 1 do n, v kaˇzd´em tahu mus´ı b´yt otoˇcena mince na pozici x z l´ıcov´e na rubovou stranu a d´ale otoˇcena mince na pozici x − 1, x − 2 nebo x − 3 (pokud x > 3). ˇ Zˇrejmˇe m´a l´ıc na pozici 1 SG-hodnotu 1, na pozici 2 hodnotu 2, atd. Rada minc´ı s nˇekolika hlavami pak odpov´ıd´a nˇekolika hrom´adk´am kamen˚ u.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
36 / 51
Reprezentace her pomoc´ı ot´aˇcen´ı minc´ı Podobnˇe jako lze hry reprezentovat pomoc´ı Nimu, lze ˇcasto hry reprezentovat i pomoc´ı ot´aˇcen´ı minc´ı. U nˇekter´ych her je v´yhodnˇejˇs´ı reprezentace pomoc´ı Nimu, u jin´ych je tomu naopak.
Pˇr´ıklad (Jednoduch´a u´vodn´ı odeˇc´ıtac´ı hra) Mˇejme odeˇc´ıtac´ı hru s S = {1, 2, 3}. Hru reprezentujeme pomoc´ı n minc´ı oˇc´ıslovan´ych od 1 do n, v kaˇzd´em tahu mus´ı b´yt otoˇcena mince na pozici x z l´ıcov´e na rubovou stranu a d´ale otoˇcena mince na pozici x − 1, x − 2 nebo x − 3 (pokud x > 3). ˇ Zˇrejmˇe m´a l´ıc na pozici 1 SG-hodnotu 1, na pozici 2 hodnotu 2, atd. Rada minc´ı s nˇekolika hlavami pak odpov´ıd´a nˇekolika hrom´adk´am kamen˚ u.
Pˇr´ıklad (Dvojˇcata) Dvojˇcata je velmi podobn´a hra pˇrevracen´ı ˇzelv, kdy mus´ıme otoˇcit pr´avˇe dvˇe mince (s obvyklou konvecn´ı). Zde je vhodn´e ˇc´ıslovat pozice minc´ı od 0 – dost´av´ame tak g (x) = x (tedy Twins jsou opˇet tot´eˇz, co Nim). Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
36 / 51
Pˇr´ıklad (Faleˇsn´e ˇzelvy) Tato hra m´a prostˇrednictv´ım minc´ı pˇrirozenˇejˇs´ı reprezantaci neˇz jako hra s hrom´adkami kamen˚ u. Je podobn´a hˇre Pˇrevracen´ı ˇzelv, m´ame ale povoleno otoˇcit 1, 2 nebo 3 mince (jako obvykle s nejpravˇejˇs´ı ve smˇeru l´ıc → rub).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
37 / 51
Pˇr´ıklad (Faleˇsn´e ˇzelvy) Tato hra m´a prostˇrednictv´ım minc´ı pˇrirozenˇejˇs´ı reprezantaci neˇz jako hra s hrom´adkami kamen˚ u. Je podobn´a hˇre Pˇrevracen´ı ˇzelv, m´ame ale povoleno otoˇcit 1, 2 nebo 3 mince (jako obvykle s nejpravˇejˇs´ı ve smˇeru l´ıc → rub). V tomto pˇr´ıpadˇe se ukazuje jako v´yhodnˇejˇs´ı pro v´ypoˇcet SG-funkce ˇc´ıslovat pozice minc´ı od 0 m´ısto od 1. Obvykl´ym zp˚ usobem vypoˇcteme pozice x : g (x):
0 1
1 2
2 4
3 7
4 8
5 11
6 13
7 14
8 16
9 19
10 21
Jestli jde funkci g (x) popsat jin´ym obvykl´ym zp˚ usobem, je asi obt´ıˇzn´e na prvn´ı pohled odhalit (kromˇe toho, ˇze g (x) je vˇzdy rovno bud’ 2x nebo 2x + 1).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
37 / 51
Pˇr´ıklad (Faleˇsn´e ˇzelvy) Tato hra m´a prostˇrednictv´ım minc´ı pˇrirozenˇejˇs´ı reprezantaci neˇz jako hra s hrom´adkami kamen˚ u. Je podobn´a hˇre Pˇrevracen´ı ˇzelv, m´ame ale povoleno otoˇcit 1, 2 nebo 3 mince (jako obvykle s nejpravˇejˇs´ı ve smˇeru l´ıc → rub). V tomto pˇr´ıpadˇe se ukazuje jako v´yhodnˇejˇs´ı pro v´ypoˇcet SG-funkce ˇc´ıslovat pozice minc´ı od 0 m´ısto od 1. Obvykl´ym zp˚ usobem vypoˇcteme pozice x : g (x):
0 1
1 2
2 4
3 7
4 8
5 11
6 13
7 14
8 16
9 19
10 21
Jestli jde funkci g (x) popsat jin´ym obvykl´ym zp˚ usobem, je asi obt´ıˇzn´e na prvn´ı pohled odhalit (kromˇe toho, ˇze g (x) je vˇzdy rovno bud’ 2x nebo 2x + 1). Odpovˇed’ (opˇet) z´avis´ı na bin´arn´ım z´apisu ˇc´ısel – ˇc´ıslo nazveme odious (hnusn´e), pokud je poˇcet 1 v jeho bin´arn´ım z´apisu lich´y, je-li poˇcet jedniˇcek sud´y nazveme ho evil (odporn´e). Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
37 / 51
Lze pomˇernˇe snadno (indukc´ı) dok´azat, ˇze g (x) = 2x + 1, pokud je 2x evil, a rovno 2x, pokud je odious. Jin´ymi slovy, posloupnost g (x) je tvoˇrena pr´avˇe vˇsemi odious ˇc´ısly. Samotn´y d˚ ukaz je zaloˇzen na faktu, ˇze evil ⊕ evil = odious ⊕ odious = evil odious ⊕ evil = evil ⊕ odious = odious.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
38 / 51
Lze pomˇernˇe snadno (indukc´ı) dok´azat, ˇze g (x) = 2x + 1, pokud je 2x evil, a rovno 2x, pokud je odious. Jin´ymi slovy, posloupnost g (x) je tvoˇrena pr´avˇe vˇsemi odious ˇc´ısly. Samotn´y d˚ ukaz je zaloˇzen na faktu, ˇze evil ⊕ evil = odious ⊕ odious = evil odious ⊕ evil = evil ⊕ odious = odious.
Pokud m´ame nyn´ı l´ıce na pozic´ıch x1 , . . . , xn , pak, jde-li o P-pozici, (tj. g (x1 ) ⊕ · · · ⊕ g (xn )), pak nutnˇe n mus´ı b´yt sud´e, a nav´ıc x1 ⊕ · · · ⊕ xn = 0 (nebot’ g (x) = 2x s obˇcasn´ym pˇrid´an´ım 1). P-pozice ve Faleˇsn´ych ˇzelv´ach jsou pr´avˇe P-pozice v Nimu, kter´e maj´ı sud´y poˇcet hrom´adek.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
38 / 51
Prav´ıtko
Tato hra m´a pomoc´ı velmi jednoduchou reprezentaci pomoc´ı ot´aˇcen´ı minc´ı. Tah spoˇc´ıv´a v tom, ˇze libovoln´y poˇcet soused´ıc´ıch minc´ı m˚ uˇze b´yt otoˇcen. Pokud ˇc´ıslujeme pozice od 1, splˇ nuje SG-funkce vztah g (n) = mex{0, g (n − 1), g (n − 1) ⊕ g (n − 2), . . . , g (n − 1) ⊕ · · · ⊕ g (1)}.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
39 / 51
Prav´ıtko
Tato hra m´a pomoc´ı velmi jednoduchou reprezentaci pomoc´ı ot´aˇcen´ı minc´ı. Tah spoˇc´ıv´a v tom, ˇze libovoln´y poˇcet soused´ıc´ıch minc´ı m˚ uˇze b´yt otoˇcen. Pokud ˇc´ıslujeme pozice od 1, splˇ nuje SG-funkce vztah g (n) = mex{0, g (n − 1), g (n − 1) ⊕ g (n − 2), . . . , g (n − 1) ⊕ · · · ⊕ g (1)}. Z tohoto vztahu lze snadno odvodit hodnoty SG-funkce: pozice x: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 g (x): 1 2 1 4 1 2 1 8 1 2 1 4 1 2, tj. g (x) je nejvyˇsˇs´ı mocnina 2 dˇel´ıc´ı n. N´azev hry vych´az´ı z dˇelky znaˇcek na prav´ıtku.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
39 / 51
Pl´an pˇredn´aˇsky
1
Hry na odeb´ır´an´ı kamen˚ u
2
Nim
3
Hry na grafech
4
Souˇcty her
5
Dalˇs´ı hry ˇreˇsiteln´e pomoc´ı SG-funkce Hry Take-and-Break Ot´aˇcen´ı minc´ı Dvourozmˇern´e ot´aˇcen´ı minc´ı a nim-souˇcin
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
40 / 51
Ot´aˇcen´ı roh˚ u
Zobecn´ıme nyn´ı ot´aˇcen´ı minc´ı pˇrid´an´ım dalˇs´ıho rozmˇeru. Souˇradnice minc´ı budeme ˇc´ıslovat od 0 a zn´azorˇ novat ve 4. kvadrantu, podm´ınku, ˇze nejpravˇejˇs´ı mince mus´ı b´yt otoˇcena z l´ıce na rub nahrad´ıme tout´eˇz podm´ınkou pro minci nejv´ıce na jihov´ychod – oznaˇc´ıme-li jej´ı souˇradnice (x, y ) pak kaˇz´ad ot´aˇcen´a mince mus´ı b´yt v obd´eln´ıku {(a, b) : 0 ≤ a ≤ x; 0 ≤ b ≤ y }
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
41 / 51
Ot´aˇcen´ı roh˚ u
Tah v t´eto hˇre spoˇc´ıv´a v otoˇcen´ı ˇctyˇr r˚ uzn´ ych minc´ı v rohu nˇejak´eho rovnobˇeˇzn´ıku. Rekurentn´ı vztah pro SG-funkci se uˇc´ı snadno:
g (x, y ) = mex{g (x, b) ⊕ g (a, y ) ⊕ g (a, b) : 0 ≤ a < x; 0 ≤ b < y }, s poˇc´ateˇcn´ımi podm´ınkami g (x, 0) = g (0, y ) = 0 pro vˇsechna x, y . Zˇrejmˇe rovnˇeˇz g (x, 1) = g (1, x) = 1 (dalˇs´ı reprezentace klasick´eho jednohrom´adkov´eho Nimu).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
42 / 51
N´asleduj´ıc´ı tabulka ud´av´a hodnoty SG-funkce pro hru vypoˇcten´e pomoc´ı uveden´eho rekurzivn´ıho vztahu: 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 2 3 1 8 10 11 9 12 14 2 0 3 0 3 1 2 12 15 13 14 4 7 4 0 4 8 12 6 2 14 10 11 15 5 0 5 10 15 2 7 8 13 3 6 6 0 6 11 13 14 8 5 3 7 1 7 9 14 10 13 3 4 15 8 7 0 8 0 8 12 4 11 3 7 15 13 5 9 0 9 14 7 15 6 1 8 5 12 10 0 10 15 5 3 9 12 6 1 11 11 0 11 13 6 7 12 10 1 9 2 12 0 12 4 8 13 1 9 5 6 10 13 0 13 6 11 9 4 15 2 14 3 14 0 14 7 9 5 11 2 12 10 4 15 0 15 5 10 1 14 4 11 2 13 Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
Ot´aˇcen´ı roh˚ u 10 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7
11 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8
12 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3
2. 9. 2008
13 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12
14 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6
43 / 51
Jako ilustraci spoˇc´ıtejme g (4, 4) prostˇrednictv´ım rekurentn´ıho vzorce – z t´eto pozice je 16 moˇzn´ych tah˚ u (10 aˇz na symetrii), po v´ypoˇctu jej´ıch SG-hodnot dostaneme g (4, 4) = mex{0, 4, 8, 12, 1, 14, 11, 3, 5, 2} = 6.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
44 / 51
Jako ilustraci spoˇc´ıtejme g (4, 4) prostˇrednictv´ım rekurentn´ıho vzorce – z t´eto pozice je 16 moˇzn´ych tah˚ u (10 aˇz na symetrii), po v´ypoˇctu jej´ıch SG-hodnot dostaneme g (4, 4) = mex{0, 4, 8, 12, 1, 14, 11, 3, 5, 2} = 6. Stav R R R R R
R R R R R
R R R L R
R L R R R
R R R R L
m´a SG-hodnotu 3 ⊕ 1 ⊕ 6 = 4 a je tedy N-stavem. V´ıtˇezn´y tah mus´ı ze 6 udˇelat 2 – jedinou moˇznost´ı je otoˇcit mince na pozic´ıch (3, 3), (3, 4), (4, 3) a (4, 4).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
44 / 51
Nim-souˇcin ˇ ısla v tabulce SG-funkce u hry Ot´aˇcen´ı roh˚ C´ u vypadala dosti n´ahodnˇe, ale ve skuteˇcnosti lze pomoc´ı nich velmi vhdonˇe definovat tzv. Nim-souˇ cin s velmi pˇekn´ymi vlastnostmi. Nad´ale budeme pro hodnotu g (x, y ) pouˇz´ıvat oznaˇcen´ı x ⊗ y .
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
45 / 51
Nim-souˇcin ˇ ısla v tabulce SG-funkce u hry Ot´aˇcen´ı roh˚ C´ u vypadala dosti n´ahodnˇe, ale ve skuteˇcnosti lze pomoc´ı nich velmi vhdonˇe definovat tzv. Nim-souˇ cin s velmi pˇekn´ymi vlastnostmi. Nad´ale budeme pro hodnotu g (x, y ) pouˇz´ıvat oznaˇcen´ı x ⊗ y . Ihned je vidˇet, ˇze 0 ⊗ x = 0 a x ⊗ 0 = 0 a d´ale, ˇze 1 ⊗ x = x a x ⊗ 1 = x (tedy 0 a 1 se chovaj´ı obdobnˇe jako u bˇeˇzn´eho n´asoben´ı). Zˇrejmˇe je rovnˇeˇz operace ⊕ komutativn´ı (tj. x ⊕ y = y ⊕ x).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
45 / 51
Nim-souˇcin ˇ ısla v tabulce SG-funkce u hry Ot´aˇcen´ı roh˚ C´ u vypadala dosti n´ahodnˇe, ale ve skuteˇcnosti lze pomoc´ı nich velmi vhdonˇe definovat tzv. Nim-souˇ cin s velmi pˇekn´ymi vlastnostmi. Nad´ale budeme pro hodnotu g (x, y ) pouˇz´ıvat oznaˇcen´ı x ⊗ y . Ihned je vidˇet, ˇze 0 ⊗ x = 0 a x ⊗ 0 = 0 a d´ale, ˇze 1 ⊗ x = x a x ⊗ 1 = x (tedy 0 a 1 se chovaj´ı obdobnˇe jako u bˇeˇzn´eho n´asoben´ı). Zˇrejmˇe je rovnˇeˇz operace ⊕ komutativn´ı (tj. x ⊕ y = y ⊕ x). M´enˇe zˇrejm´a je jiˇz asociativita Nim-souˇcinu x ⊗ (y ⊗ z) = (x ⊗ y ) ⊗ z).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
45 / 51
Nim-souˇcin ˇ ısla v tabulce SG-funkce u hry Ot´aˇcen´ı roh˚ C´ u vypadala dosti n´ahodnˇe, ale ve skuteˇcnosti lze pomoc´ı nich velmi vhdonˇe definovat tzv. Nim-souˇ cin s velmi pˇekn´ymi vlastnostmi. Nad´ale budeme pro hodnotu g (x, y ) pouˇz´ıvat oznaˇcen´ı x ⊗ y . Ihned je vidˇet, ˇze 0 ⊗ x = 0 a x ⊗ 0 = 0 a d´ale, ˇze 1 ⊗ x = x a x ⊗ 1 = x (tedy 0 a 1 se chovaj´ı obdobnˇe jako u bˇeˇzn´eho n´asoben´ı). Zˇrejmˇe je rovnˇeˇz operace ⊕ komutativn´ı (tj. x ⊕ y = y ⊕ x). M´enˇe zˇrejm´a je jiˇz asociativita Nim-souˇcinu x ⊗ (y ⊗ z) = (x ⊗ y ) ⊗ z). Plat´ı ale rovnˇeˇz i distributivita Nim-souˇcinu vzhledem k Nim-souˇctu: x ⊗ (y ⊕ z) = (x ⊗ y ) ⊕ (x ⊗ z).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
45 / 51
Nem´enˇe v´yznamn´ym faktem je, ˇze kaˇzd´e nenulov´e ˇc´ıslo m´a Nim-inverzi (tj. pro kaˇzd´e nenulov´e x existuje x 0 tak, ˇze x ⊗ x 0 = 1). Oznaˇc´ıme-li jako nim-dˇelen´ı, m˚ uˇzeme napˇr. ps´at 1 2 = 3 nebo 6 5 = 9.
Pozn´amka (Algebraick´a) Mnoˇzina nez´aporn´ych cel´ych ˇc´ısel N0 spolu s operacemi Nim-souˇctu a Nim-souˇcinu tvoˇr´ı tzv. tˇeleso (obdoba R, Q s klasick´ymi operacemi +, ·, pˇritom ale (Z, +, ·) tˇeleso netvoˇr´ı).
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
46 / 51
V´ypoˇcet Nim-souˇcinu Podobnˇe jako v nˇekter´ych pˇredchoz´ıch pˇr´ıpadech se ukazuje, ˇze rekurentn´ı zp˚ usob Nim-souˇcinu dvou ˇc´ısel lze nahradit v´ypoˇctem pˇr´ım´ym.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
47 / 51
V´ypoˇcet Nim-souˇcinu Podobnˇe jako v nˇekter´ych pˇredchoz´ıch pˇr´ıpadech se ukazuje, ˇze rekurentn´ı zp˚ usob Nim-souˇcinu dvou ˇc´ısel lze nahradit v´ypoˇctem pˇr´ım´ym. Ten vych´az´ı z n´asleduj´ıc´ıch pravidel (pojmem Fermatova mocnina n oznaˇcujeme ˇc´ıslo 22 pro n ≥ 1): 1 Nim-souˇ cin Fermatovy mocniny s libovoln´ym menˇs´ım ˇc´ıslem je roven jejich bˇeˇzn´emu souˇcinu
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
47 / 51
V´ypoˇcet Nim-souˇcinu Podobnˇe jako v nˇekter´ych pˇredchoz´ıch pˇr´ıpadech se ukazuje, ˇze rekurentn´ı zp˚ usob Nim-souˇcinu dvou ˇc´ısel lze nahradit v´ypoˇctem pˇr´ım´ym. Ten vych´az´ı z n´asleduj´ıc´ıch pravidel (pojmem Fermatova mocnina n oznaˇcujeme ˇc´ıslo 22 pro n ≥ 1): 1 Nim-souˇ cin Fermatovy mocniny s libovoln´ym menˇs´ım ˇc´ıslem je roven jejich bˇeˇzn´emu souˇcinu 2 Nim-souˇ cin Fermatovy mocniny se sebou samotnou je roven roven bˇeˇzn´emu souˇcinu Fermatovy mocniny a 3/2.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
47 / 51
V´ypoˇcet Nim-souˇcinu Podobnˇe jako v nˇekter´ych pˇredchoz´ıch pˇr´ıpadech se ukazuje, ˇze rekurentn´ı zp˚ usob Nim-souˇcinu dvou ˇc´ısel lze nahradit v´ypoˇctem pˇr´ım´ym. Ten vych´az´ı z n´asleduj´ıc´ıch pravidel (pojmem Fermatova mocnina n oznaˇcujeme ˇc´ıslo 22 pro n ≥ 1): 1 Nim-souˇ cin Fermatovy mocniny s libovoln´ym menˇs´ım ˇc´ıslem je roven jejich bˇeˇzn´emu souˇcinu 2 Nim-souˇ cin Fermatovy mocniny se sebou samotnou je roven roven bˇeˇzn´emu souˇcinu Fermatovy mocniny a 3/2.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
47 / 51
V´ypoˇcet Nim-souˇcinu Podobnˇe jako v nˇekter´ych pˇredchoz´ıch pˇr´ıpadech se ukazuje, ˇze rekurentn´ı zp˚ usob Nim-souˇcinu dvou ˇc´ısel lze nahradit v´ypoˇctem pˇr´ım´ym. Ten vych´az´ı z n´asleduj´ıc´ıch pravidel (pojmem Fermatova mocnina n oznaˇcujeme ˇc´ıslo 22 pro n ≥ 1): 1 Nim-souˇ cin Fermatovy mocniny s libovoln´ym menˇs´ım ˇc´ıslem je roven jejich bˇeˇzn´emu souˇcinu 2 Nim-souˇ cin Fermatovy mocniny se sebou samotnou je roven roven bˇeˇzn´emu souˇcinu Fermatovy mocniny a 3/2.
24 ⊗ 17 = (16 ⊕ 8) ⊗ (16 ⊕ 1) = (16 ⊗ 16) ⊕ (16 ⊗ 1) ⊕ (8 ⊗ 16) ⊕ (8 ⊗ 1) = = 24 ⊕ 16 ⊕ 126 ⊕ 8 = 128 V pˇr´ıpadˇe v´ypoˇctu 8 ⊗ 8 neum´ıme napsat 8 jako Nim-souˇcet dvou jednoduˇsˇs´ıch ˇc´ısel, pom˚ uˇzeme si proto z´apisem 8 = 2 ⊗ 4. 8 ⊗ 8 = (2 ⊗ 4) ⊗ (2 ⊗ 4) = (2 ⊗ 2 ⊗ 4 ⊗ 4) = 3 ⊗ 6 = (2 ⊕ 1) ⊗ (4 ⊕ 2) = = (2 ⊗ 4) ⊕ (2 ⊗ 2) ⊕ (1 ⊗ 4) ⊕ (1 ⊗ 2) = 8 ⊕ 3 ⊕ 4 ⊕ 2 = 13. Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
47 / 51
Tartanov´e hry Hra Ot´aˇcen´ı roh˚ u je pˇr´ıkladem her, jejichˇz ˇreˇsen´ı je moˇzn´e urˇcit pomoc´ı Nim-souˇcinu.
Definice Jsou-li G a H hry s obracen´ım minc´ı, pak tartanov´a hra G × H je dvourozmˇern´a hra s obracen´ım minc´ı, v n´ıˇz jsou povolen´e tahy pr´avˇe uspoˇr´adan´e dvojice povolen´ych tah˚ u z G a H. Tak dost´av´ame Ot´aˇcen´ı roh˚ u jako souˇcin Dvojˇcata× Dvojˇcata.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
48 / 51
Tartanov´e hry Hra Ot´aˇcen´ı roh˚ u je pˇr´ıkladem her, jejichˇz ˇreˇsen´ı je moˇzn´e urˇcit pomoc´ı Nim-souˇcinu.
Definice Jsou-li G a H hry s obracen´ım minc´ı, pak tartanov´a hra G × H je dvourozmˇern´a hra s obracen´ım minc´ı, v n´ıˇz jsou povolen´e tahy pr´avˇe uspoˇr´adan´e dvojice povolen´ych tah˚ u z G a H. Tak dost´av´ame Ot´aˇcen´ı roh˚ u jako souˇcin Dvojˇcata× Dvojˇcata. Pro anal´yzu tartanov´ych her je d˚ uleˇzit´a n´asleduj´ıc´ı vˇeta.
Vˇeta M´a-li hra G1 SG-funkci g1 a hra G2 SG-funkci g2 , pak m´a tartanov´a hra G1 × G2 SG-funkci g1 ⊗ h1 , tj. g (x, y ) = g1 (x) ⊗ g2 (y ). Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
48 / 51
Koberec (ot´aˇcen´ı bloku) Hra Koberec, kdy je pˇr´ıpustn´ym tahem otoˇcen´ı vˇsech minc´ı v nˇejak´em obd´eln´ıku (s obvyklou jihov´ychodn´ı konvenc´ı), je vlastnˇe souˇcinem Prav´ıtko×Prav´ıtko, odkud taky plyne v´ypoˇcet SG-funkce. Tabulka SG-funkce je tak d´ana hodnotami SG-funkce Prav´ıtka a Nim-souˇcinem jejich hodnot: 1 1 2 1 4 1 2 1 8
Michal Bulant (PˇrF MU)
1 1 2 1 4 1 2 1 8
2 2 3 2 8 2 3 2 12
1 1 2 1 4 1 2 1 8
4 4 8 4 6 4 8 4 11
1 1 2 1 4 1 2 1 8
Kombinatorick´ e hry
2 2 3 2 8 2 3 2 12
1 1 2 1 4 1 2 1 8
8 8 12 8 11 8 12 8 13
2. 9. 2008
49 / 51
Pˇr´ıklad Pod´ıvejme se na starou zn´amou pozici R R R R R
R R R R R
R R R L R
R L R R R
R R R R L
jako na pozici ve hˇre Koberec.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
50 / 51
Pˇr´ıklad Pod´ıvejme se na starou zn´amou pozici R R R R R
R R R R R
R R R L R
R L R R R
R R R R L
jako na pozici ve hˇre Koberec. Podle pˇredchoz´ıho spoˇc´ıt´ame jej´ı SG-hodnotu 8 ⊕ 4 ⊕ 1 = 13. V´ıtˇezn´y tah (otoˇcen´ı obd´eln´ıku (1, 1) − (2, 4)) zmˇen´ı hodnotu 8 na 5 a tedy celkov´y souˇcet na 0.
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
50 / 51
Pouˇzit´a literatura
WW Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy: Winning Ways for Your Mathematical Plays, Academic Press,1982. GT Thomas S. Ferguson: Game Theory, Impartial Combinatorial Games (UCLA lecture), http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf Wiki Wikipedia, The Free Encyclopedia, www.wikipedia.org. App Martin J. Chlond, Online Java Games, http://www.chlond.demon.co.uk/
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
51 / 51
Pouˇzit´a literatura
WW Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy: Winning Ways for Your Mathematical Plays, Academic Press,1982. GT Thomas S. Ferguson: Game Theory, Impartial Combinatorial Games (UCLA lecture), http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf Wiki Wikipedia, The Free Encyclopedia, www.wikipedia.org. App Martin J. Chlond, Online Java Games, http://www.chlond.demon.co.uk/
Michal Bulant (PˇrF MU)
Kombinatorick´ e hry
2. 9. 2008
51 / 51
