Hra a hry V´aclav Vopravil
´ Uvod 1
Kombinatorick´ e hry
Teorie kombinatorick´ych her se zab´yv´a abstraktn´ımi hrami dvou hr´aˇc˚ u. Hra je definov´ana pomoc´ı jednoduˇsˇs´ıch her, tj. jako uspoˇr´adan´a dvojice mnoˇzin her. Obvykle hra G se oznaˇcuje jako G ≡ GL GR , kde GL a GR jsou mnoˇzinami her a odpov´ıdaj´ı moˇzn´ym tah˚ um dvou hr´aˇc˚ u, kter´e jsou L R oznaˇcov´any jako lev´y L a prav´y R. Pokud obˇe mnoˇziny G a G jsou pr´azdn´e ∅, potom existuje jednoznaˇcnˇe urˇcen´a hra {∅ | ∅}, kter´a se jmenuje 0, tj. 0 ≡ {∅ | ∅}. Dvˇe hry se naz´yvaj´ı identick´e, pokud jejich lev´e a prav´e moˇznosti mnoˇziny tah˚ u spl´yvaj´ı, L L R R tj. x ≡ y ⇔ X = Y ∧ X = Y . To znamen´a,ˇze hry a y maj´ı stejn´y tvar (na prav´e x stranˇe m´ame mnoˇzinovou rovnost). Pokud x ≡ X L X R je hra, potom typick´y prvek mnoˇziny X L oznaˇcujeme xL (typick´y tah lev´eho hr´aˇce v x) a typick´y prvek mnoˇziny X R oznaˇcujeme xR (analogicky typick´y tah prav´eho hr´aˇce v x). Je-li ({x1 , x2 , . . .}, {y1 , y2 , . . .}), budeme ˇcasto ps´at jednoduˇse {x1 , x2 , . . . | y1 , y2 , . . .}, tj. zbyteˇcn´e z´avorky nebudeme ps´at. Oznaˇcov´an´ı se tak zpˇrehledn´ ı. M´ısto y ≡ ({z}, ∅) budeme ps´at y ≡ {z |}, etc. Pro hru x budeme tak´e ps´at x ≡ xL xR . Pˇ r´ıklad 1.1. 1. 0 ≡ {|} ≡ (∅, ∅) je nejjednoduˇsˇs´ı hra, ve kter´e ˇz´adn´y z hr´aˇc˚ u nem˚ uˇze t´ahnout. V t´eto hˇre prvn´ı hr´aˇc prohraje a druh´y hr´aˇc vyhraje. Hra se naz´yv´a nula. 2. 1 ≡ {0 |} ≡ ({0}, ∅) je hra, ve kter´e lev´y hr´aˇc si m˚ uˇze vybrat jedin´y tah do hry 0 a prav´y hr´aˇc nem˚ uˇze t´ahnout. 3. Naopak hra −1 ≡ {| 0} ≡ (∅, {0}). Minus jedniˇcka je nedˇeliteln´y symbol, znaˇcka. V t´eto hˇre m˚ uˇze prav´y hr´aˇc zahr´at do 0, ale lev´y hr´aˇc nem´a pravidly povolen´y tah. 4. ∗ ≡ {0 | 0} ≡ ({0}, {0}) je hra star. Oba hr´aˇci si sv´ym prvn´ım tahem mohou zahr´at do hry 0. Hra ∗ je z´akladem tzv. Nim her. ´ Umluva 1.2. Hr´aˇc, kter´y nem˚ uˇze ze sv´e pozice t´ahnout, prohr´al a soupeˇr vyhr´al. Hra nem˚ uˇze b´yt nekoneˇcn´a, kaˇzd´ym tahem se zjednoduˇs´ı. Klesaj´ıc´ı ˇretˇezec jednoduˇsˇs´ıch a jednoduˇsˇs´ıch her skonˇc´ı u hry 0.
1
Definice 1.3. Pro kaˇzdou hru x ≥ 0 ⇔ (∀xR ∈ X R ) xR 0 x 0 ⇔ (∃xL ∈ X L ) xL ≥ 0 x ≤ 0 ⇔ (∀xL ∈ X L ) xL 0 x 0 ⇔ (∃xR ∈ X R ) xR ≤ 0 x>0⇔x≥0∧x 0 x<0⇔x≤0∧x 0 x 0⇔ x 0∧x 0 x=0⇔x≥0∧x≤ 0
x≡ (R (L (L (R ( ( ( (
xL xR L; lev´y vyhraje, nebude-li zaˇc´ınat.) L; lev´y vyhraje, bude-li v x zaˇc´ınat.) R; prav´y vyhraje, nebude-li v x zaˇc´ınat.) R; prav´y vyhraje, bude-li v x zaˇc´ınat.) L; kladn´a hra, vyhraje lev´y hr´aˇc.) R; z´aporn´a hra, vyhraje prav´y hr´aˇc.) 1; fazy hra, vyhraje prvn´ı hr´aˇc.) 2; nulov´a hra, vyhraje druh´y hr´aˇc.)
Vyhraje hr´aˇc znamen´a, ˇze m´a vyhr´avaj´ıc´ı strategii, tj. takov´a vyhr´avaj´ıc´ı strategie existuje. Pˇri v´ıtˇezn´e strategii existuje takov´a posloupnost tah˚ u, kter´a zaruˇc´ı hr´aˇci v´ıtˇezstv´ı, bez ohledu na moˇzn´e soupeˇrovy tahy. Takˇze ve hˇre (x ≥ 0) zaˇcne-li prav´y hr´aˇc jakkoliv, lev´y nalezne v´ıtˇeznou pozici, kter´a mu zabezpeˇc´ı v´ıtˇezstv´ı bez ohledu na dalˇs´ı moˇzn´e tahy prav´eho hr´aˇce atd. Pˇ r´ıklad 1.4. 1. 0 ≡ {|} hra, ve kter´e ˇz´adn´y z hr´aˇc˚ u nem˚ uˇze t´ahnout, je nev´yhodn´e zaˇc´ınat, vyhraje druh´y hr´aˇc. 2. 1 ≡ {0 |} je hra kladn´a, vyhraje lev´y hr´aˇc. 3. Naopak hra −1 ≡ {| 0} z´aporn´a hra, vyhraje prav´y hr´aˇc. 4. ∗ ≡ {0 | 0} vyhraje prvn´ı hr´aˇc, tj. hr´aˇc na tahu. Vˇ eta 1.5. Pro kaˇzdou hru x plat´ı 1. ¬(x ≥ 0 ∧ x 0), 2. ¬(x ≤ 0 ∧ x 0). D˚ ukaz:
2
⊓ ⊔
Souˇ cet her
Sˇc´ıt´an´ı her se hraje ve dvou (nebo v´ıce) komponent´ach. Hr´aˇc na tahu si vybere jednu z nich a v n´ı udˇel´a pravidly povolen´y tah. Zbyl´e komponenty z˚ ustanou nezmˇenˇeny. Definice 2.1. x + y ≡ xL + y, x + y L xR + y, x + y R Pˇ r´ıklad 2.2. 1. 0 + 0 ≡ {|} + {|} ≡ {|} ≡ 0, 2. 1 + 0 ≡ {0 |} + {|} ≡ {0 + 0 |} ≡ 1, 3. 0 + (−1) ≡ {|} + {| 0}+ ≡ {| 0 + 0} ≡ −1, 4. 1 + (−1) ≡ {0 |} + {| 0} ≡ {−1 | 1}. Z´ avˇ er 2.3. (Monoid her) Hry tvoˇr´ı komutativn´ı monoid s nulov´ym prvkem 0. Vˇ eta 2.4. Pro libovoln´e hry x, y, z plat´ı: 1. x + 0 ≡ x, 2
2. x + y ≡ y + x, 3. x + (y + z) ≡ (x + y) + z. D˚ ukaz:
⊓ ⊔
Z´ avˇ er 2.5. (Grupa her) Hry tvoˇr´ı komutativn´ı grupu s nulov´ym prvkem 0. Vˇ eta 2.6. V´ysledek hry a sˇc´ıt´an´ı (strategick´ a hodnota): Pro libovoln´e hry x, y plat´ı: 1. 2. 3. 4. 5.
x ≥ 0 ∧ y ≥ 0 ⇒ x + y ≥ 0, x ≥ 0 ∧ y 0 ⇒ x + y 0, x + y ≥ 0 ∧ y ≤ 0 ⇒ x ≥ 0, x + y ≥ 0 ∧ y 0 ⇒ x 0, x + y 0 ∧ y ≤ 0 ⇒ x 0.
Pozn´amka: Jak se asi bude hr´at prvn´ı implikace? Zaˇcne-li prav´y ve hˇre x, bude druh´y hr´aˇc odpov´ıdat ve stejn´e komponentˇe (zde R L). A podobnˇe ve vˇsech dalˇs´ıch pˇr´ıpadech. D˚ ukaz:
3
⊓ ⊔
Rozd´ıl her
Definice 3.1. V opaˇcn´e hˇre −x vymˇen´ıme role lev´eho a prav´eho hr´aˇce. −x ≡ −xR −xL Rozd´ıl her x, y pˇrevedeme na souˇcet, tj. x − y ≡ x + (−y) ≡ xL − y, x − y R xR − y, x − y L . Pˇ r´ıklad 3.2. 1. −0 ≡ −{|} ≡ {|} ≡ 0, 2. −1 ≡ −{0 |} ≡ {| −0} ≡ {| 0} ≡ −1, (na lev´e stranˇe m´ame opaˇcnou hru ke hˇre 1, na prav´e stranˇe hru minus jedna), 3. −∗ ≡ −{0 | 0} ≡ {−0 | −0} ≡ {0 | 0} ≡ ∗, 4. 1 − 1 ≡ 1 + (−1) ≡ {−1 | 1}. Vˇ eta 3.3. Pro libovolnou hru x plat´ı: 1. x ≤ 0 ⇔ −x ≥ 0, 2. x 0 ⇔ −x 0, 3. x < 0 ⇔ −x > 0. D˚ ukaz:
⊓ ⊔
Vˇ eta 3.4. Pro libovoln´e hry x, y plat´ı: 1. −(−x) ≡ x, 2. −(x + y) ≡ (−x) + (−y), 3. −(x − y) ≡ y − x, 3
4. x − x = 0. Posledn´ı vlastnost je rovnost! D˚ ukaz:
4
⊓ ⊔
Uspoˇ r´ ad´ an´ı
Definice 4.1. Pro libovoln´e dvˇe hry x, y plat´ı x̺y ⇔ (x − y)̺0, pro vˇsechny ̺ ∈ {≥, ≤, , , >, <, =, }. Strategick´a interpretace slovy je napˇr. x ≥ y znamen´a, ˇze hra x je pro lev´eho nejm´enˇe tak dobr´a, jako hra y, a pod. v ostatn´ıch pˇr´ıpadech. Vˇ eta 4.2. Pro libovoln´e hry x, y plat´ı 1. x ≤ y ⇔ y ≥ x ⇔ −x ≥ −y, 2. x y ⇔ y x ⇔ −x −y, 3. x < y ⇔ y > x ⇔ −x > −y. D˚ ukaz:
⊓ ⊔
Vˇ eta 4.3. Pro libovoln´e dvˇe hry x, y plat´ı 1. 2. 3. 4. 5.
x ≤ y ⇔ (∀xL ∈ X L ) xL y a souˇcasnˇe (∀y R ∈ Y R ) x y R , x y ⇔ (∃xR ∈ X R ) xR ≤ y nebo (∃y L ∈ Y L ) x ≤ y L , x > y ⇔ x ≥ y ∧ x y, x = y ⇔ x ≥ y ∧ y ≥ x, x y ⇔ x y ∧ x y.
D˚ ukaz:
⊓ ⊔
Vˇ eta 4.4. (Vlastnosti uspoˇr´ad´an´ı) Pro libovoln´e tˇri hry x, y, z plat´ı: 1. 2. 3. 4. 5. 6.
x ≥ x, x ≥ y ∧ y ≥ z ⇒ x ≥ z, x ≥ y ∧ y z ⇒ x z, x ≥ y ⇔ x + z ≥ y + z, x y ⇔ x + z y + z, (∀xL ∈ X L )(∀xR ∈ X R ) xL x ∧ x xR .
D˚ ukaz:
⊓ ⊔
Vˇ eta 4.5. (Vlastnosti ostr´eho uspoˇr´ ad´ an´ı) Pro libovoln´e hry x, y, z plat´ı: 1. ¬(x > x), 2. x > y ⇒ ¬(y > x), 4
3. x > y ∧ y > z ⇒ x > z, 4. x > y ⇔ x + z > y + z. D˚ ukaz:
⊓ ⊔
Z´ avˇ er 4.6. Relace ≥ je uspoˇr´ad´an´ı (reflexivn´ı a tranzitivn´ı relace), kter´e generuje relaci ekvivalence = a relace > je ostr´e uspoˇr´ ad´ an´ı.
5
Kongruence
V´ıme, ˇze relace = je ekvivalence. Tato relace je v souladu se sˇc´ıt´an´ım a odˇc´ıt´an´ı: Vˇ eta 5.1. Pro libovoln´e tˇri hry plat´ı 1. x = y ⇒ x + z = y + z, 2. x = y ⇒ −x = −y. D˚ ukaz:
⊓ ⊔
Vˇ eta 5.2. Pro vˇsechny hry x, x1 , x2 , y, y1, y2 , z plat´ı: 1. 2. 3. 4.
x1 = x2 ∧ y1 = y2 ⇒ x1 + y1 = x2 + y2 , x1 = x2 ∧ y1 = y2 ⇒ x1 − y1 = x2 − y2 , x = y ∧ y̺z ⇒ x̺z pro vˇsechny ̺ ∈ {≥, , >, }, x̺y ∧ y = z ⇒ x̺z pro vˇsechny ̺ ∈ {≥, , >, }.
Z´ avˇ er 5.3. Hry tvoˇr´ı ˇc´asteˇcnˇe uspoˇr´ adanou Abelovu grupu modulo = . Vˇ eta 5.4. Je-li G ≡ A, B, GL \ {A, B} GR a A ≤ B, potom G = B, GL \ {A, B} GR . D˚ ukaz:
6
⊓ ⊔
Nadre´ aln´ aˇ c´ısla
Definice 6.1. Hru x nazveme (nadre´aln´ym) ˇc´ıslem, pr´avˇe tehdy a jen tehdy, plat´ı-li souˇcasnˇe: 1. (∀xL ∈ X L )(∀xR ∈ X R ) xL xR , 2. vˇsechny xL ∈ X L a vˇsechny xR ∈ X R jsou ˇc´ısla. Pˇ r´ıklad 6.2. 1. Hra 0 ≡ {|}, 2. 1 ≡ {0 |}, 3. −1 ≡ {| 0}, jsou ˇc´ısla, ∗ nen´ı ˇc´ıslo. Vˇ eta 6.3. Pro vˇsechna ˇc´ısla x, y plat´ı: 5
1. (∀xL ∈ X L )(∀xR ∈ X R ) xL < x < xR , 2. x y ⇔ x < y, 3. −x a x + y jsou ˇc´ısla. D˚ ukaz:
⊓ ⊔
Vˇ eta 6.4. (O redukci) Vˇeta o nejstarˇs´ım prvku ˇ ısla mnoˇziny Z[1/2], tj. racion´aln´ı ˇc´ısla tvaru m/2k pro m ∈ Z a k ∈ N, se Pozn´amka: C´ naz´yvaj´ı dyadick´a (racion´aln´ı) ˇc´ısla. Vˇ eta 6.5. (∀n ∈ N)(∀m ∈ Z) 1. 2. 3. 4. 5.
0 ≡ {|} je nulov´y prvek, n ≡ {n − 1 |}, −n ≡ {| −(n − 1)}, n + 1/2 ≡ {n | n + 1}, 2m+1 m m+1 ≡ . k k−1 k−1 2 2 2
Pˇ r´ıklad 6.6.
7
Re´ aln´ aˇ c´ısla
Definice 7.1. (Re´aln´a nadre´aln´a ˇc´ısla) Necht’ x je nadre´aln´e ˇc´ıslo. Toto ˇc´ıslo se naz´yv´a re´aln´e ˇc´ıslo, pokud plat´ı souˇcasnˇe tyto dvˇe podm´ınky: 1. Existuje takov´e n ∈ N, pro kter´e −n < x < n, 2. (∀xL ∈ X L )(∃m ∈ N) x−xL > 2−m a souˇcasnˇe (∀xR ∈ X R )(∃m ∈ N) xR −x > 2−m . ´ Uloha 7.2. 1. Vytvoˇrte ˇc´ısla 3/8 a 5/8 jako nadre´aln´a ˇc´ısla a ovˇeˇrte, ˇze 3/8+5/8 = 1. Definujte vˇsechna dalˇs´ı ˇc´ısla, kter´a vyuˇzijete. 2. Vytvoˇrte ˇc´ısla 2/5 a 5/8 jako nadre´aln´a ˇc´ısla a ovˇeˇrte, ˇze 2/5+3/5 = 1. Pˇredpokl´adejte, ˇze vˇsechna dyadick´a racion´aln´ı ˇc´ısla jsou jiˇz vytvoˇrena. ————————
[2hs03RMF actual rosemeier.tex, 09/01/14, 08:26]
6
