Nim Wythoff

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 23 octombrie 2017; verificările necesită 2 modificări .

Wythoff 's nim , sau jocul lui Wythoff , este un joc strategic de matematică pentru doi jucători cu două grămezi de jetoane. Jucătorii iau pe rând jetoanele dintr-una sau ambele grămezi; în acest din urmă caz, jetoanele egale sunt luate din ambele grămezi. Câștigă cel care ia ultimele sau ultimele jetoane.

Martin Gardner , în From Penrose Mosaics to Secure Ciphers (Capitolul 8), afirmă că jocul este cunoscut în China sub numele de 捡石子jianshizi [1] [2] („luarea de pietre”). [3] Matematicianul olandez Willem Wiethoff a publicat o analiză matematică a jocului în 1907.

Strategia optimă

Orice poziție în joc poate fi descrisă printr-o pereche de numere ( n , m ), cu n ≤, unde n și m  sunt numărul de jetoane din grămezi. Strategia jocului se bazează pe definirea pozițiilor bune și rele : poziție proastă (ing.: poziție rece ) - o poziție pierzătoare chiar și cu acțiuni optime ale jucătorului care se află în ea; o poziție bună ( fierbinte ) este una din care jucătorul câștigă cu acțiuni optime. Strategia optimă pentru un jucător într-o poziție bună este de a muta jocul în oricare dintre pozițiile proaste, dând dreptul de a muta adversarului, care, la rândul său, va muta jocul într-o poziție bună pentru primul jucător.

Clasificarea pozițiilor în bune și rele se poate face recursiv folosind următoarele trei reguli:

  1. (0,0) - poziție proastă (pierdere).
  2. Orice poziție din care se poate ajunge la o poziție proastă într-o singură mișcare este o poziție bună.
  3. O poziție din care fiecare mișcare duce la o poziție bună este o poziție proastă.

De exemplu, toate pozițiile de forma (0, m ) și ( m , m ) pentru m > 0 sunt bune (după regula 2). În același timp, poziția (1,2) este proastă, deoarece din ea nu poți ajunge decât la pozițiile (0,1), (0,2) și (1,1) și toate sunt bune, așa cum este indicat. în propoziţia anterioară. Primele poziții proaste ( n , m ) cu cele mai mici valori ale lui n și m  sunt (0, 0), (1, 2), (3, 5), (4, 7), (6,10) și (8, 13).

Formula pentru poziții proaste

Wythoff a demonstrat că pozițiile proaste urmează un model definit de raportul de aur . În special, dacă k  este un număr natural arbitrar și

,

unde φ este raportul de aur, atunci ( n k , m k ) este k --a poziție proastă. Aceste două secvențe sunt numite secvențe Wythoff inferioare și superioare și sunt numerotate A000201 și , respectiv, A001950 în Encyclopedia of Integer Sequences .OEISicon light.svg OEISicon light.svg

Cele două secvențe n k și m k sunt secvențele Beatty asociate cu ecuația

Cele două secvențe sunt complementare : fiecare număr întreg pozitiv apare exact o dată în orice secvență.

Vezi și

Referințe

  1. ↑ Nikolai Nikolaevici Vorobyov. numerele Fibonacci. M.: Nauka, 1978
  2. ↑ Matulis A., Savukinas A., Queen - into the corner, „jianshizi” și numerele Fibonacci, Kvant, 1984
  3. ↑ Jocul lui Wythoff la Cut-the-knot Arhivat la 9 februarie 2021 la Wayback Machine , citând cartea lui Martin Gardner Penrose Tiles la Trapdoor Ciphers

Link -uri