Nim (joc)

Nim este un joc în care doi jucători ridică pe rând obiectele care sunt împărțite în mai multe grămezi. Într-o singură mișcare, poate fi luat orice număr de obiecte (mai mare decât zero) dintr-o grămadă. Câștigă jucătorul care ia ultimul articol. În versiunea clasică a jocului, numărul de grămezi este de trei.

Un caz special în care există o singură grămadă, dar numărul maxim de obiecte care pot fi luate pe tură este limitat, este cunoscut sub numele de jocul lui Bache . Nim este un joc complet cu informații finite . Jocul clasic de la Nîmes este fundamental pentru teorema Sprague-Grundy . Această teoremă afirmă că jocul obișnuit al sumei jocurilor imparțiale este echivalent cu jocul obișnuit al lui Nim. În același timp, fiecărui termen de joc imparțial îi corespunde un morman de Nim, numărul de obiecte în care este egal cu valoarea funcției Sprague-Grundy pentru poziția de joc a acestui joc.

Istoricul jocului

Jocul chinezesc a fost menționat de europeni încă din secolul al XVI-lea. Numele „nim” a fost dat jocului de către matematicianul american Charles Bouton , care în 1901 a descris strategia câștigătoare a jocului . Există mai multe opțiuni pentru originea numelui jocului:

din verbul german nehmen sau din verbul englez veche Nim , care înseamnă „a lua”;
Anonim din verbul englez Win („a câștiga”).

Jucăria „Dr. Nim”, un mic computer cu minge inventat în anii 1960, a jucat nu în ea, ci în jocul lui Basche .

Strategia de joc

În cazul general, se ia în considerare o grămadă de articole cu articole. Jucătorii se fac pe rând. Mișcarea este că jucătorul ia dintr-o grămadă de articole. Fiecărei poziții a jocului i se atribuie o sumă minimă a acestei poziții - rezultatul adunării dimensiunilor tuturor grămezilor din sistemul de numere binar fără a lua în considerare transferul de biți, adică adăugarea cifrelor binare ale numerelor din câmp de reziduuri modulo 2 : $p$ $N_{1},N_{2},\cdots N_{p)$ $i\in [1,p]$ $n\in [1,N_{i}]$ $S=N_{1}\oplus N_{2}\oplus \cdots \oplus N_{p)$

O strategie câștigătoare este să părăsești o poziție cu el - suma egală cu zero după mutarea ta. Se bazează pe faptul că dintr-o poziție cu o sumă nim care nu este egală cu zero, se poate obține o poziție cu o sumă nim zero într-o singură mișcare, iar dintr-o poziție cu o sumă nim zero, orice mutare. conduce la o poziție cu o sumă nim diferită de zero.

Exemplu : să presupunem că există trei grămezi în joc, ele conțin 2 (0010 în reprezentare binară), 8 (1000) și, respectiv, 13 (1101) elemente. Suma minimă a acestei poziții este 7 (0111). Prin urmare, strategia câștigătoare este de a lua trei articole din a treia grămadă - vor rămâne 10 (1010) articole, iar suma minimă a poziției va deveni 0 (0000). Să presupunem că, după rândul tău, adversarul ia toate obiectele din prima grămadă - o strategie câștigătoare ar fi să ia două articole din a treia grămadă. În acest caz, după mutarea ta, grămezile vor conține 0 (0000), 8 (1000) și, respectiv, 8 (1000) elemente, suma minimă va fi în continuare 0.

Opțiuni

Inversați-l

Jucătorii completează grămezi până la un anumit . Disponibil ca misiune în jocul de calculator „ Space Rangers ”. Jocul este echivalent cu un nim stateful obișnuit . $N$ $\{N-N_{i}\}_{i=1}^{p)$

Nim-Bashe

Nu mai puteți lua obiecte. Jocul este echivalent cu un nim stateful obișnuit $k$ $\{N_{i}\operatorname {mod} (k+1)\}_{i=1}^{p)$

Ciocolata

Există un baton de ciocolată , o felie „otrăvită”. Jucătorul, singur, sparge ciocolata de-a lungul liniei și mănâncă partea neotrăvită. Cel care rămâne cu felia otrăvită pierde. Jocul este echivalent cu nim cu patru grămezi. $m\ori n$

Mier

În această variantă, jucătorul care a luat ultimul obiect pierde. Strategia câștigătoare este aceeași cu strategia câștigătoare a jocului obișnuit până în momentul în care, ca urmare a mișcării jucătorului, un anumit număr de grămezi cu un singur obiect în fiecare dintre ele ar trebui să rămână pe masă. În cazul unui avar, jucătorul trebuie să lase un număr impar de teancuri, în timp ce strategia câștigătoare a unui joc obișnuit necesită lăsarea unui număr par de teancuri, astfel încât suma neem să fie zero. Aceasta poate fi formulată după cum urmează: dacă există exact o grămadă care conține mai mult de un articol, atunci ia toate articolele din el sau toate, cu excepția unuia, astfel încât să rămână un număr impar de grămezi unice; în caz contrar, rămâneți la strategia câștigătoare a jocului obișnuit.

Multinim

Un caz mai general al jocului de la Nîmes a fost propus de Eliakim Moore . În joc , jucătorilor li se permite să ia obiecte dintr-un număr maxim de grămezi. Este ușor de observat că jocul obișnuit este el . Pentru a o rezolva, este necesar să notăm dimensiunile fiecărui heap în sistemul de numere binar și să însumăm aceste numere în sistemul de numere -ary fără silabe. Dacă numărul este 0, atunci poziția curentă este în pierdere, în caz contrar este câștigătoare și există o mutare de la acesta la o poziție cu valoare zero. $Nim_{i}$ $i$ $Nim_{1}$ $(i+1)$

Forked-nim

O altă versiune a jocului a fost propusă de Matvey Bernstein. În ea, puteți împărți în mod arbitrar orice grămada în două grămezi arbitrare în loc de o mișcare. În toate celelalte privințe, jocul se joacă conform regulilor obișnuite.

În film și televiziune

Acest joc servește ca metaforă a ceea ce se întâmplă în filmul „ Anul trecut în Marienbad ” [1] .

Vezi și

Note

↑ Oliver Knill. Matematică în filme : Anul trecut în Marienbad . Matematica în filme . Departamentul de Matematică Universitatea Harvard. Data accesului: 22 iunie 2009. Arhivat din original la 21 februarie 2012.

Literatură

Ball W., Coxeter G. Recreeri și eseuri matematice. - M . : Mir, 1986. - S. 47-51.
Fomin SV Sisteme numerice . - a 5-a ed. - M . : Nauka, 1987. - S. 48.
Gardner M. Tic-tac-toe. —M.: Mir, 1988. ISBN 5-03-001234-6 .
Jean-Paul Delahaye . Stratégies magiques au pays de Nim // Pour la science: Journal. - Paris: Belin, 2009. - T. 377 , nr. 3 . - S. 88-93 . Arhivat din original pe 10 iunie 2013.