(toc){width: 28em}*{text-align:center;} *Conţinut*
* 'Introducere':numerele-sprague-grundy#introducere
* 'Ce este jocul NIM?':numerele-sprague-grundy#jocul-nim

* 'Aplicatii ale strategiei NIM':numerele-sprague-grundy#aplicatii-nim

* 'Aplicaţii ale strategiei NIM':numerele-sprague-grundy#aplicatii-nim

* 'Numerele Sprague Grundy':numerele-sprague-grundy#sprague-grundy

* 'Aplicatii ale numerelor Sprague Grundy':numerele-sprague-grundy#aplicatii-sg

* 'Aplicaţii ale numerelor Sprague Grundy':numerele-sprague-grundy#aplicatii-sg

* 'Concluzii':numerele-sprague-grundy#concluzii
* 'Probleme suplimentare':numerele-sprague-grundy#probleme-suplimentare
* 'Bibliografie':numerele-sprague-grundy#bibliografie

După acest pas grămezile vor avea $4$, $8$, $12$ pietre. Ne aflăm astfel într-o stare cu suma $XOR$ egală cu $*0*$.

h2(#aplicatii-nim). Aplicatii ale strategiei NIM

h2(#aplicatii-nim). Aplicaţii ale strategiei NIM

Exemplificăm în continuare câteva probleme în care se foloseste strategia jocului $NIM$.

Exemplificăm în continuare câteva probleme în care se foloseşte strategia jocului $NIM$.

h3(#problema-1). Problema 1
bq. Pe o tablă de şah, care are $N x M$ căsuţe, sunt plasaţi pe prima linie $N$ pioni albi şi pe ultima linie $N$ pioni negri. Fiecare dintre cei doi jucători poate muta un singur pion, care îi aparţine, un număr strict pozitiv de căsuţe în sus sau în jos, astfel încât să nu ajungă vreun pion alb să fie mai jos decât pionul negru de pe aceeaşi coloană. Pierde jucătorul care nu mai poate muta.

h3. Solutie

h3. Soluţie

Această problemă este o deghizare a jocului $NIM$, numărul de pătrăţele libere între pionul alb şi pionul negru de pe coloana $i$ putând fi considerat numărul de pietre din grămada $i$. Singura diferenţă este că se pot adăuga pietre la grămadă (existând posibilitatea mutării înapoi). Această problemă se rezolvă uşor, jucătorul care are strategie de câştig putând evita asemenea mutări. O astfel de mutare poate fi utilă numai pentru jucătorul care este într-o poziţie de pierdere. Când jucătorul care nu are strategie de câştig mută înapoi $x$ căsuţe, celălalt jucător va muta pionul propriu de pe aceeaşi coloanã cu $x$ căsuţe în faţă, astfel ajungându-se la aceeaşi stare cu cea existentă cu două mutări anterior (considerând diferenţa poziţiilor).

bq. Pe o linie sunt plasate la coordonate întregi $2 x N$ piese roşii şi albastre. Fiecare piesă roşie poate fi mutată în dreapta oricâte poziţii astfel încât să nu sară peste o piesă albastră, iar piesele albastre pot fi mutate oricâte poziţii la stânga astfel încât să nu depăşească vreo piesă roşie. Piesele vor alterna: roşu, albastru, roşu, albastru etc. Pierde jucătorul care nu mai poate muta.

h3. Solutie

h3. Soluţie

Această problemă poate fi, de asemenea, redusă la jocul $NIM$. Diferenţele poziţiilor perechilor de piese roşii şi albastre consecutive constituie numărul de pietre al grămezilor din jocul $NIM$.

bq. Se consideră $N$ grămezi de pietre, jucătorii mută alternativ, fiecare jucător extrăgând oricâte pietre dintr-o singură grămadă. Cel care ia ultima piatră pierde jocul.

h3. Solutie

h3. Soluţie

Strategia acestui joc este similară cu cea aplicată în jocul $NIM$ cu câteva mici diferenţe. Jucătorul care are strategie de câştig în poziţia curentă în cadrul jocului $NIM$ face aceeaşi mutare pe care ar face-o în cazul jocului $NIM$, exceptând cazul în care această mutare lasă doar grămezi cu o singură piatră şi numărul acestor grămezi este par. În această situaţie, dacă ar trebui să ia $x$ pietre, jucătorul poate lua $x - 1$ pietre din grămada actuală, pentru ca numărul de grămezi să fie impar şi el să facă ultima mutare.

Afirmaţia anterioară constituie un rezultat al _Teoriei Sprague-Grundy_. _Roland Percival Sprague_ (1936) şi _Patrick Michael Grundy_ (1939) sunt doi matematicieni care s-au ocupat, independent, de teoria jocurilor imparţiale.

În continuare, considerăm următorul enunt:

În continuare, considerăm următorul enunţ:

bq. Se consideră un graf aciclic care conţine în noduri câţiva pioni, jucătorii alternează la mutare şi fiecare poate muta câte un pion pe un arc care iese din nodul în care este situat pionul. Pierde jucătorul care nu poate muta.

Problema se rezolvă acum uşor efectuând o sortare topologică a nodurilor grafului aciclic şi numerotând nodurile folosind funcţia $mex$.

h2(#aplicatii-sg). Aplicatii ale numerelor Sprague Grundy

h2(#aplicatii-sg). Aplicaţii ale numerelor Sprague Grundy

În continuare, sa studiem alte probleme ce se pot rezolva cu numerele $Sprague Grundy$.

În continuare, să studiem alte probleme ce se pot rezolva cu numerele $Sprague Grundy$.

h3(#problema-4). Problema 4 (Joc, Bursele Agora 2003/2004, Runda 13)

bq. Se consideră $K$ grămezi cu $n{~1~}, n{~2~}, …, n{~K~}$ pietre fiecare. Când este rândul său, un jucător poate lua dintr-o gramadă $2^m^$ pietre. Jucătorul care ia ultima piatră câştigă. Restricţii: $K ≤ 50, n{~i~} ≤ 10^200^$.

h3. Solutie

h3. Soluţie

Să determinăm valorile $Sprague Grundy$ pentru grămezi mici:

bq. Se consideră $K$ grămezi de pietre cu $n{~1~}, n,{~2~} …, n{~K~}$ pietre. Un jucător poate lua dintr-o grămadă la mutarea lui un număr pozitiv de pietre dar nu mai mult de jumătate din pietrele din grămadă. Jucătorul care nu mai poate muta pierde. Restricţii: $K ≤ 50, n{~i~} ≤ 100000$.

h3. Solutie

h3. Soluţie

Numărul $100000$ nu este foarte mare şi valorile $Sprague Grundy$ pot fi determinate _off-line_ şi incluse în programul nostru ca şi constante. Putem scrie pentru valori mici secvenţa $Sprague Grundy$:

bq. Se consideră $n (n ≤ 10)$ rânduri de beţe pe o masă, cu $S{~i~} (S{~i~} ≤ 10)$ beţe aliniate pe fiecare rând şi doi jucători. Beţele de pe rândul $i$ sunt numerotate secvenţial de la $1$ la $S{~i~}$. Cei doi jucători mută alternativ. Fiecare mişcare constă în eliminarea a unu, două sau trei beţe de pe acelaşi rând. Beţele trebuie sã fie numerotate secvenţial, adică să fie consecutive. De exemplu, un rând are $10$ beţe şi primul jucător elimină beţele $4$, $5$, $6$, deci vor rămâne numai beţele $1$, $2$, $3$, $4$, $8$, $9$, $10$. Al doilea jucător poate lua la rândul său beţele $1$, $2$, $3$, dar nu beţele $3$, $7$, $8$ pentru că acestea nu sunt numerotate consecutiv (bineînţeles că există şi alte mutări valide). Câştigă jucătorul care ia ultimul băţ de pe masă.

h3. Solutie

h3. Soluţie

Problema generală are o soluţie ingenioasă care ţine seama de parităţile rândurilor, dar la această problemă, datorită mărginirii lui $S{~i~} (S{~i~} ≤ 10)$ nu este necesar să fim ingenioşi. Restricţia $S{~i~} ≤ 10$, ne ajută prin faptul cã numărul total de poziţii (dacă jucăm pe o singură gramadă), este $2^10^$. Vom reprezenta o poziţie printr-un întreg, iar dacă acel întreg are în codificarea lui binară pe poziţia $i$ un bit de $1$ înseamnă că el reprezintă un rând de beţe care conţine în el băţul numerotat cu $i$. Este uşor de realizat un graf aciclic al mişcărilor pentru un rând (graful este aciclic pentru că la fiecare mutare luăm beţe din configuraţie). Numerotăm fiecare poziţie cu numerele $Sprague Grundy$, şi acum problema deciderii dacă suntem sau nu într-o poziţie câştigătoare devine banală. În problema iniţială trebuia să jucăm împotriva calculatorului şi să câştigăm. Putem realiza aceasta folosind mutarea câştigătoare prezentată la jocul $NIM$.

{*} poate să rupă şi să mănânce toate patrăţelele de pe marginea tabletei, cu condiţia ca tableta rămasă să aibă cel puţin dimensiunea $1 x 1$.
Nici una dintre aceste trei mutări nu poate fi efectuată asupra unei tablete de dimensiune $1 x 1$. Pierde jucătorul care nu mai poate efectua nici o mutare.

h3. Solutie

h3. Soluţie

Pentru această problemă vom calcula matricea $SG{~i,j~}$ care reprezintă valoarea $Sprague-Grundy$ asociată unei tablete de dimensiuni $(i, j)$. Să vedem care este recurenţa care va satisface elementele matricei $SG$: