Nim Wythoff

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 23. lokakuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Wythoffin nim eli Wythoffin peli on strateginen matematiikkapeli kahdelle pelaajalle kahdella pelimerkkipinolla. Pelaajat ottavat vuorotellen pelimerkkejä yhdestä tai molemmista pinoista; jälkimmäisessä tapauksessa molemmista pinoista otetaan yhtä suuret lastut. Se, joka ottaa viimeisen tai viimeiset pelimerkit, voittaa.

Martin Gardner kirjassaan From Penrose Mosaics to Secure Ciphers (luku 8) toteaa, että peli tunnetaan Kiinassa nimellä 捡石子jianshizi [1] [2] ("kivien ottaminen"). [3] Hollantilainen matemaatikko Willem Wiethoff julkaisi matemaattisen analyysin pelistä vuonna 1907.

Optimaalinen strategia

Mitä tahansa pelin paikkaa voidaan kuvata numeroparilla ( n , m ), jossa n ≤, missä n ja m  ovat pinoissa olevien pelimerkkien lukumäärä. Pelin strategia perustuu hyvien ja huonojen asemien määrittelyyn : huono asema (eng.: cold position ) - häviävä asema siinäkin olevan pelaajan optimaalisilla toimilla; hyvä ( kuuma ) asema on sellainen, josta pelaaja voittaa optimaalisilla toimilla. Hyvässä asemassa olevan pelaajan optimaalinen strategia on siirtää peli mihin tahansa huonoista paikoista, jolloin siirtymisoikeus annetaan vastustajalle, joka puolestaan ​​siirtää pelin ensimmäiselle pelaajalle hyvään paikkaan.

Asemien luokittelu hyviin ja huonoihin voidaan tehdä rekursiivisesti seuraavien kolmen säännön avulla:

  1. (0,0) - huono sijoitus (tappio).
  2. Mikä tahansa asento, josta huono asento voidaan saavuttaa yhdellä liikkeellä, on hyvä asento.
  3. Asento, josta jokainen liike johtaa hyvään asentoon, on huono asento.

Esimerkiksi kaikki muodon (0, m ) ja ( m , m ) asemat arvolle m > 0 ovat hyviä (säännön 2 mukaan). Samaan aikaan sijainti (1,2) on huono, koska siitä pääsee vain paikkoihin (0,1), (0,2) ja (1,1), ja ne ovat kaikki hyviä, kuten osoitettu edellisessä lauseessa. Ensimmäiset muutamat huonot paikat ( n , m ), joiden arvot n ja m ovat pienimmät,  ovat (0, 0), (1, 2), (3, 5), (4, 7), (6,10) ja (8, 13).

Kaava huonoille sijoille

Wythoff osoitti, että huonot asemat noudattavat kultaisen leikkauksen määrittelemää kaavaa . Erityisesti, jos k  on mielivaltainen luonnollinen luku, ja

,

missä φ on kultainen suhde, niin ( n k , m k ) on k : s huono asema. Näitä kahta sekvenssiä kutsutaan alemmiksi ja ylemmiksi Wythoff-sekvensseiksi ja ne on numeroitu A000201 ja A001950 vastaavasti Encyclopedia of Integer Sequences -julkaisussa.OEISicon light.svg OEISicon light.svg

Kaksi sekvenssiä n k ja m k ovat yhtälöön liittyvät Beatty-sekvenssit

Nämä kaksi sekvenssiä täydentävät toisiaan : jokainen positiivinen kokonaisluku esiintyy tarkalleen kerran missä tahansa sekvenssissä.

Katso myös

Viitteet

  1. ↑ Nikolai Nikolajevitš Vorobjov. Fibonaccin numerot. M.: Nauka, 1978
  2. ↑ Matulis A., Savukinas A., Queen - nurkkaan, "jianshizi" ja Fibonacci numerot, Kvant, 1984
  3. ↑ Wythofin peli Cut-the-knotissa Arkistoitu 9. helmikuuta 2021 Wayback Machinessa , lainaten Martin Gardnerin kirjaa Penrose Tiles to Trapdoor Ciphers

Linkit