Nim Wythoff

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2017. október 23-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A Wythoff nim vagy Wythoff játéka egy stratégiai matematikai játék két játékos számára, két halom zsetonnal. A játékosok felváltva vesznek zsetonokat az egyik vagy mindkét pakliból; az utóbbi esetben mindkét kupacból egyenlő zsetont vesznek. Az nyer, aki elveszi az utolsó vagy utolsó zsetont.

Martin Gardner a From Penrose Mosaics to Secure Ciphers (8. fejezet) című könyvében kijelenti, hogy a játék Kínában 捡石子jianshizi [1] [2] ("kövek szedése") néven ismert. [3] Willem Wiethoff holland matematikus 1907-ben matematikai elemzést közölt a játékról.

Optimális stratégia

A játék bármely pozíciója leírható egy számpárral ( n , m ), ahol n ≤, ahol n és m  a kupacokban lévő zsetonok száma. A játék stratégiája a jó és rossz pozíciók meghatározásán alapul : rossz pozíció (magyar: hideg pozíció ) - vesztes pozíció még a benne lévő játékos optimális akcióival is; a jó ( forró ) pozíció az, ahonnan a játékos optimális akciókkal nyer. A jó pozícióban lévő játékos optimális stratégiája az, hogy a játékot bármelyik rossz pozícióba mozgatja, így az ellenfélnek joga van a lépéshez, aki viszont az első játékos számára jó pozícióba helyezi a játékot.

A pozíciók jó és rossz csoportba sorolása rekurzív módon történhet a következő három szabály segítségével:

  1. (0,0) - rossz pozíció (vesztés).
  2. Minden olyan pozíció jó, ahonnan egy mozdulattal rossz pozíciót lehet elérni.
  3. Az a pozíció, ahonnan minden mozdulat jó pozícióba vezet, rossz pozíció.

Például minden (0, m ) és ( m , m ) alakú pozíció m > 0 esetén jó (a 2. szabály szerint). Ugyanakkor az (1,2) pozíció rossz, mert onnan csak a (0,1), (0,2) és (1,1) pozíciókra lehet eljutni, és ezek mind jók, ahogy jeleztük. az előző mondatban. Az első néhány rossz pozíció ( n , m ) a legkisebb n és m értékkel  : (0, 0), (1, 2), (3, 5), (4, 7), (6,10) és (8, 13).

A rossz pozíciók képlete

Wythoff bebizonyította, hogy a rossz pozíciók az aranymetszés által meghatározott mintát követnek . Különösen, ha k  egy tetszőleges természetes szám, és

,

ahol φ az aranymetszés, akkor ( n k , m k ) a k -edik rossz pozíció. Ezt a két sorozatot alsó és felső Wythoff-szekvenciának nevezik, és az Encyclopedia of Integer Sequences - ben A000201 , illetve A001950 számozást kapnak.OEISicon light.svg OEISicon light.svg

A két n k és m k sorozat az egyenlethez társított Beatty-sorozat

A két sorozat kiegészíti egymást : minden pozitív egész szám pontosan egyszer jelenik meg bármely sorozatban.

Lásd még

Hivatkozások

  1. ↑ Nyikolaj Nyikolajevics Vorobjov. Fibonacci számok. M.: Nauka, 1978
  2. ↑ Matulis A., Savukinas A., Queen - a sarokba, "jianshizi" és Fibonacci számok, Kvant, 1984
  3. ↑ Wythoff játéka a Cut-the-knotnál Archiválva 2021. február 9-én a Wayback Machine -nél, Martin Gardner Penrose Tiles to Trapdoor Ciphers című könyvét idézve

Linkek