Nim Wythoff

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 23. října 2017; kontroly vyžadují 2 úpravy .

Wythoff 's nim neboli Wythoff's game je strategická matematická hra pro dva hráče se dvěma hromádkami žetonů. Hráči se střídají v odebírání žetonů z jedné nebo obou hromádek; v druhém případě se z obou hromádek odeberou stejné žetony. Vyhrává ten, kdo vezme poslední nebo poslední žetony.

Martin Gardner v Od mozaiky Penrose k bezpečným šifrám (kapitola 8) uvádí, že hra je v Číně známá jako 捡石子jianshizi [1] [2] ("brát kameny"). [3] Nizozemský matematik Willem Wiethoff publikoval v roce 1907 matematickou analýzu hry.

Optimální strategie

Jakákoli pozice ve hře může být popsána dvojicí čísel ( n , m ), přičemž n ≤, kde n a m  jsou počet žetonů v hromádkách. Strategie hry je založena na definici dobrých a špatných pozic : špatná pozice (angl . cold position ) - prohrávající pozice i při optimálních akcích hráče, který se v ní nachází; dobrá ( horká ) pozice je taková, ze které hráč vyhrává optimálními akcemi. Optimální strategií pro hráče v dobré pozici je přesunout hru na kteroukoli ze špatných pozic a dát tak právo přesunout soupeři, který zase posune hru do dobré pozice pro prvního hráče.

Klasifikace pozic na dobré a špatné lze provést rekurzivně pomocí následujících tří pravidel:

  1. (0,0) - špatná pozice (ztráta).
  2. Každá pozice, ze které lze dosáhnout špatné pozice jedním tahem, je dobrá pozice.
  3. Pozice, ze které každý pohyb vede k dobré pozici, je špatná pozice.

Například všechny pozice tvaru (0, m ) a ( m , m ) pro m > 0 jsou dobré (podle pravidla 2). Zároveň je pozice (1,2) špatná, protože se z ní dostanete pouze na pozice (0,1), (0,2) a (1,1) a všechny jsou dobré, jak je naznačeno v předchozí větě. Prvních několik špatných pozic ( n , m ) s nejmenšími hodnotami n a m  jsou (0, 0), (1, 2), (3, 5), (4, 7), (6,10) a (8, 13).

Vzorec pro špatné pozice

Wythoff dokázal, že špatné pozice se řídí vzorem definovaným zlatým řezem . Zejména, je-li k  libovolné přirozené číslo a

,

kde φ je zlatý řez, pak ( n k , m k ) je k -tá špatná pozice. Tyto dvě sekvence se nazývají nižší a horní Wythoffovy sekvence a jsou očíslovány A000201 a A001950 v Encyclopedia of Integer Sequences .OEISicon light.svg OEISicon light.svg

Dvě sekvence nk a m ​​k jsou Beattyho sekvence spojené s rovnicí

Tyto dvě sekvence jsou komplementární : každé kladné celé číslo se v jakékoli sekvenci objeví právě jednou.

Viz také

Reference

  1. ↑ Nikolaj Nikolajevič Vorobjov. Fibonacciho čísla. M.: Nauka, 1978
  2. ↑ Matulis A., Savukinas A., Královna - do rohu, "jianshizi" a Fibonacciho čísla, Kvant, 1984
  3. ↑ Wythoffova hra na Cut-the-knot Archivována 9. února 2021 na Wayback Machine s citací z knihy Martina Gardnera Penrose Tiles to Trapdoor Ciphers

Odkazy