Wythoffova hra - Wythoffs game - Wikipedia

Wythoffova hra se hraje se dvěma hromadami žetonů

Wythoffova hra je matematická hra pro dva hráče odečítací hra, hrál se dvěma hromadami pultů. Hráči se střídavě odebírají čítače z jedné nebo obou hromádek; při odebírání čítačů z obou hromádek musí být počet čítačů odstraněných z každé hromádky stejný. Hra končí, když jedna osoba odstraní poslední počítadlo nebo čítače, čímž vyhraje.

Ekvivalentní popis hry je, že singl šachová královna je umístěn někde na velké mřížce čtverců a každý hráč může pohybovat královnou směrem k levému dolnímu rohu mřížky: na jih, západ nebo jihozápad, libovolný počet kroků. Vítězem je hráč, který přesune královnu do rohu.

Martin Gardner v jeho březnu 1977 "Sloupec Matematické hry " v Scientific American tvrdí, že hra se hrála v Číně pod názvem 捡石子 jiǎn shízǐ („trhání kamenů“).^[1] Nizozemský matematik W. A. Wythoff zveřejnil matematickou analýzu hry v roce 1907.^[2]

Optimální strategie

Vizualizace Wythoffovy hry Nim. Dolní levý čtverec je pozice (1,1) a červené čtverce jsou studené pozice. Všimněte si, že vítězný čtverec není na obrázku.

Jakoukoli pozici ve hře lze popsat dvojicí celá čísla (n, m) s n ≤ m, popisující velikost obou pilot v poloze nebo souřadnice královny. Strategie hry se točí kolem studené pozice a horké pozice: v chladné pozici hráč, jehož tah je na řadě, s nejlepší hrou prohraje, zatímco v horké pozici vyhraje hráč, jehož tah je na tahu, s nejlepší hrou. The optimální strategie z horké polohy je přejít do jakékoli dosažitelné studené polohy.

Lze provést klasifikaci pozic na teplou a studenou rekurzivně s následujícími třemi pravidly:

(0,0) je studená pozice.
Jakákoli poloha, ze které lze dosáhnout studené polohy jediným pohybem, je horká pozice.
Pokud každý pohyb vede do horké polohy, je pozice studená.

Například všechny pozice formuláře (0, m) a (m, m) s m > 0 je podle pravidla 2. žhavá, poloha (1,2) je však studená, protože z ní lze dosáhnout pouze poloh (0,1), (0,2), (1,0) a (1,1), jsou všechny horké. Studené pozice (n, m) s nejmenšími hodnotami n a m jsou (0, 0), (1, 2), (3, 5), (4, 7), (6, 10) a (8, 13). (sekvence A066096 a A090909 v OEIS ) (Viz také OEIS: A072061)

Pro misere hra této hry jsou (0, 1) a (2, 2) studené pozice a pozice (n, m) s m, n > 2 je studená právě tehdy, když (n, m) v normální hře je zima.

Vzorec pro chladné pozice

Wythoff zjistil, že studené polohy se řídí pravidelným vzorem určeným Zlatý řez. Konkrétně pokud k je jakékoli přirozené číslo a

{ displaystyle n_ {k} = lfloor k phi rfloor = lfloor m_ {k} phi rfloor -m_ {k} ,}

{ displaystyle m_ {k} = lfloor k phi ^ {2} rfloor = lceil n_ {k} phi rceil = n_ {k} + k ,}

kde φ je zlatý řez a my používáme funkce podlahy, pak (n_k, m_k) je k^th studená poloha. Tyto dvě řady čísel jsou zaznamenány v Online encyklopedie celočíselných sekvencí tak jako OEIS: A000201 a OEIS: A001950, resp.

Tyto dvě sekvence n_k a m_k jsou Beatty sekvence spojené s rovnicí

{ displaystyle { frac {1} { phi}} + { frac {1} { phi ^ {2}}} = 1 ,.}

Jak obecně platí pro páry sekvencí Beatty, tyto dvě sekvence jsou komplementární: každé kladné celé číslo se v každé sekvenci objeví přesně jednou.

Viz také

Reference

^ Wythoffova hra na Cut-the-uzlu, cituji Martin Gardner kniha Penroseovy dlaždice na šifry padacích dveří
^ Wythoff, W. A. (1907), „Modifikace hry nim“, Nieuw Archief voor Wiskunde, 7 (2): 199–202

externí odkazy

Weisstein, Eric W. „Wythoffova hra“. MathWorld.
Špína, James. „Wythoffova hra (dostat se domů)“ (video). Youtube. Brady Haran. Citováno 21. srpna 2017.

[1] Wythoffova hra na Cut-the-uzlu, cituji Martin Gardner kniha Penroseovy dlaždice na šifry padacích dveří

[2] Wythoff, W. A. (1907), „Modifikace hry nim“, Nieuw Archief voor Wiskunde, 7 (2): 199–202

[1]

[2]