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

* 'Ce este jocul NIM?':numerele-sprague-grundy#nim
* 'Probleme care folosesc strategia NIM':numerele-sprague-grundy#probleme-nim

* 'Ce este jocul NIM?':numerele-sprague-grundy#jocul-nim
* 'Aplicatii ale strategiei NIM':numerele-sprague-grundy#aplicatii-nim

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

* 'Probleme care se rezolvă cu numerele Sprague Grundy':numerele-sprague-grundy#probleme-sg

* 'Probleme care se rezolvă cu numerele Sprague Grundy':numerele-sprague-grundy#aplicatii-sg
* 'Concluzii':numerele-sprague-grundy#concluzii
* 'Probleme propuse':numerele-sprague-grundy#probleme-propuse

* 'Bibliografie':numerele-sprague-grundy#bibliografie
h2(#introducere). Introducere
Domeniu relativ nou şi încă necercetat în adâncime, $teoria jocurilor$ este o ramură a matematicii în care de multe ori primează inventivitatea şi nu cunoştinţele. Tocmai din acest motiv, în cadrul acestui articol vom introduce câteva noţiuni teoretice care ne vor ajuta în rezolvarea unor probleme din teoria jocurilor. Ingeniozitatea celor pasionaţi poate fi testată prin introducerea unor probleme de teoria jocurilor la concursurile de matematică şi informatică. Deoarece în România teoria jocurilor nu este studiată în şcoli, problemele din acest domeniu pot pune în dificultate concurenţii.

h2(#nim). Ce este jocul NIM?

h2(#jocul-nim). Ce este jocul NIM?

Pentru început ne vom familiariza cu jocul clasic $NIM$:

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(#probleme-nim). Probleme care folosesc strategia NIM

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

h3. Problema 1

Exemplificăm în continuare câteva probleme în care se foloseste 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
 

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).

h3. Problema 2 (Baraj, ONI 1997)

h3(#problema-2). Problema 2 (Baraj, ONI 1997)

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
 

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$.

h3. Problema 3 (El Judge MIPT online programming contest Nim Game Give Away!)

h3(#problema-3). Problema 3 ('Nim Game - Give Away!':http://acm.mipt.ru/judge/problems.pl?problem=103&CGISESSID=b4a5b84bd176d84796a209dc7c8002b8, El Judge)

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
 

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.
h2(#sprague-grundy). Numerele Sprague Grundy

Vom introduce funcţia *$mex$* cu semnificaţia: $mex(S)$ este elementul minimal natural care nu aparţine mulţimii $S$. Pentru fiecare nod $x$ al grafului aciclic considerat, vom calcula valoarea funcţiei $gx = mex(gx{~1~}, gx{~2~}, …, gx{~k~})$, unde $x{~1~}$, $x{~2~}$, …, $x{~k~}$ sunt urmaşii nodului $x$ în graf. Pentru nodurile fără urmaşi $gx = 0$.

Analog jocului cu un singur pion, graful poate fi etichetat din aproape în aproape, pornind de la nodurile fără urmaşi. Observăm că, dacă $gx = 0$ în jocul cu un singur pion situat în nodul $x$ nu avem strategie de câştig, iar dacă $gx$ este diferit de $0$ avem strategie de câştig. Restul informaţiei ne ajută la determinarea unei strategii pentru jocul cu $n$ pioni. Observăm că putem reduce acest joc la jocul $NIM$ în care grămada virtuală asociată pionului $i$ are un număr de pietre egal cu valoarea $g$ a nodului în care este situat pionul $i$.

Analog jocului cu un singur pion, graful poate fi etichetat din aproape în aproape, pornind de la nodurile fără urmaşi. Observăm că, dacă $gx = 0$ în jocul cu un singur pion situat în nodul $x$ nu avem strategie de câştig, iar dacă $gx$ este diferit de $0$ avem strategie de câştig. Restul informaţiei ne ajută la determinarea unei strategii pentru jocul cu $N$ pioni. Observăm că putem reduce acest joc la jocul $NIM$ în care grămada virtuală asociată pionului $i$ are un număr de pietre egal cu valoarea $g$ a nodului în care este situat pionul $i$.

h4. _De ce este acest joc echivalent cu jocul NIM?_

_De ce este acest joc echivalent cu jocul NIM?_

Aşa cum la $NIM$ puteam lua oricâte pietre dintr-o grămadă, aici putem muta pionul dintr-un nod cu valoarea $g$ într-un nod astfel încât noua valoare pentru pionul $i$ poate fi orice număr de la $0$ la $g - 1$. Prin urmare, pentru a verifica dacă suntem într-o poziţie de câştig în jocul cu pionii, putem aplica strategia jocului $NIM$ şi obţinem că suntem într-o poziţie de câştig dacă suma $XOR$ a numerelor din nodurile ocupate de cei $n$ pioni este diferită de $0$. Această sumă se numeşte funcţia _Sprague Grundy,_ <tex>SG(i_{1}, ..., i_{n}) = g_{i_1} \verb|^| g_{i_2} \verb|^| g_{i_3} \verb|^| ... \verb|^| g_{i_n}</tex>.

Aşa cum la $NIM$ puteam lua oricâte pietre dintr-o grămadă, aici putem muta pionul dintr-un nod cu valoarea $g$ într-un nod astfel încât noua valoare pentru pionul $i$ poate fi orice număr de la $0$ la $g - 1$. Prin urmare, pentru a verifica dacă suntem într-o poziţie de câştig în jocul cu pionii, putem aplica strategia jocului $NIM$ şi obţinem că suntem într-o poziţie de câştig dacă suma $XOR$ a numerelor din nodurile ocupate de cei $N$ pioni este diferită de $0$. Această sumă se numeşte funcţia _Sprague Grundy_: <tex>SG(i_{1}, ..., i_{n}) = g_{i_1} \verb|^| g_{i_2} \verb|^| g_{i_3} \verb|^| ... \verb|^| g_{i_n}</tex>.

Problema de la runda 47 ({_Pioni_}) 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(#probleme-sg). Probleme care se pot rezolva folosind numerele Sprague Grundy

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

h3. Problema 4

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

Problema Joc a rundei 13 a concursului de programare Bursele Agora putea fi rezolvatã în acest mod.
În acea problemă se cerea să verificăm existenţa unei strategii de câştig pentru un joc similar cu $NIM$ în care se putea lua dintr-o grămadă o piatră sau un număr prim de pietre.

În acestă problemă se cere să verificăm existenţa unei strategii de câştig pentru un joc similar cu $NIM$ în care se putea lua dintr-o grămadă o piatră sau un număr prim de pietre.

Dacă determinăm valorile $Sprague Grundy$ pentru grămezi de dimensiuni mici putem observa că se repeta o succesiune de numere: $0 1 2 3 0 1 2 3 ...$
Putem demonstra prin inducţie că această secvenţă se va repeta la nesfărşit.

Pentru o grămadă de dimensiune $n$ valoarea asociată va fi $n modulo 4$. Pentru $0 ≤ n ≤ 3$ afirmaţia este adevărată. Vom presupune afirmaţia adevărată pentru toate valorile $m < n$. Să demonstrăm acum că este adevărată şi pentru $n$. Deoarece putem lua din $n$ pietre una, două sau trei pietre, mai rămâne valoarea $n modulo 4$ care nu este eliminată încă din valorile potenţiale asociate grămezii de dimensiune $n$. Vom arăta în continuare că această valoare nici nu va fi eliminată. Eliminarea ei ar însemna că putem lua din $n$ un număr $p$ de pietre şi atunci din $(n - p) modulo 4 = n modulo 4$, am avea: $p modulo 4 = 0$, dar $p$ este un număr prim, deci valoarea _Sprague Grundy_ asociată unei grămezi de dimensiune $n$ este $n modulo 4$.

Pentru o grămadă de dimensiune $n$ valoarea asociată va fi $n modulo 4$. Pentru $0 ≤ n ≤ 3$ afirmaţia este adevărată. Vom presupune afirmaţia adevărată pentru toate valorile $m < n$. Să demonstrăm acum că este adevărată şi pentru $n$. Deoarece putem lua din $n$ pietre una, două sau trei pietre, mai rămâne valoarea $n modulo 4$ care nu este eliminată încă din valorile potenţiale asociate grămezii de dimensiune $n$. Vom arăta în continuare că această valoare nici nu va fi eliminată. Eliminarea ei ar însemna că putem lua din $n$ un număr $p$ de pietre şi atunci din $(n - p) modulo 4 = n modulo 4$, am avea: $p modulo 4 = 0$, dar $p$ este un număr prim, deci valoarea $Sprague Grundy$ asociată unei grămezi de dimensiune $n$ este $n modulo 4$.

h3. Problema 5 (El Judge MIPT online programming contest, Stone game)

h3(#problema-5). Problema 5 ('Stone game':http://acm.mipt.ru/judge/problems.pl?problem=101&CGISESSID=b4a5b84bd176d84796a209dc7c8002b8, El Judge)

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~} ≤ 10200.

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^$.

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

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

$0 : 0;    1 : 1;    2 : 2;    3 : 0;    4 : 1;    5 : 2;    6 : 0$

Observăm şi aici secvenţa repetitivă $0 1 2 0 1 2$, deci am putea trage concluzia că valoarea _Sprague Grundy_ asociată unei grămezi de dimensiune $n$ este $n modulo 3$. Această afirmaţie este adevarată şi urmează aceeaşi demonstraţie ca în cazul problemei anterioare, iar restul $modulo 3$ pentru $n$ număr cu 200 de cifre este simplu de găsit determinând suma cifrelor numărului.

Observăm şi aici secvenţa repetitivă $0 1 2 0 1 2$, deci am putea trage concluzia că valoarea $Sprague Grundy$ asociată unei grămezi de dimensiune $n$ este $n modulo 3$. Această afirmaţie este adevarată şi urmează aceeaşi demonstraţie ca în cazul problemei anterioare, iar restul $modulo 3$ pentru $n$ număr cu $200$ de cifre este simplu de găsit determinând suma cifrelor numărului.
 
h3(#problema-6). Problema 6 ('Stone game II':http://acm.mipt.ru/judge/problems.pl?problem=102&CGISESSID=b4a5b84bd176d84796a209dc7c8002b8, El Judge)

h3. Problema 6 (El Judge MIPT online programming contest, Stone game II)

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$.

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

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$:

Pentru $n$ impar valoarea asociată este aceeaşi cu valoarea asociată lui $n/2$, şi pentru $n$ par valoarea asociată este $n/2$. Acest lucru se poate demonstra prin inducţie matematică.

h3. Problema 7 (CEOI 2000, problema Sticks)
 
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(#problema-7). Problema 7 (Sticks, CEOI 2000)

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$.

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. Problema 8

h3. Solutie

Această problemă a fost propusă spre rezolvare la concursul Internet Problem Solving Contest (cel mai prestigios concurs online) şi o puteţi găsi la 'această adresă':http://ipsc.ksp.sk/xxproblems/ipsc2003/g.php. Ea a fost folosită şi la concursul organizat de '.campion':http://campion.edu.ro la o rundă online. Rezolvarea ei, complicată, folosind numerele _Sprague Grundy_ prezentate în acest articol, se poate găsi în '[3]':numerele-sprague-grundy#bibliografie, pe site-ul '[7]':numerele-sprague-grundy#bibliografie, sau pe siteul concursului '.campion':http://campion.edu.ro.

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$.

h3. Problema 9
 
Această problemă a fost propusă spre rezolvare la ediţia din acest an a Olimpiadei Naţionale de Informatică din Ucraina.

h3(#problema-8). Problema 8 ('Joc':problema/joc2, Bursele Agora 2006)

bq. Doi participanţi mănâncă alternant din nişte tablete de ciocolată după următoarele reguli:
{*} taie o tabletă în două, tăietura trebuie să fie paralelă cu una din laturile tabletei şi trebuie să nu taie pătrăţelele de ciocolată;

{*} poate să rupă şi să mănânce orice linie sau coloană de pătrăţele care nu se aflã pe marginea tabletei;
{*} 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×1.
Nici una dintre aceste trei mutări nu poate fi efectuată asupra unei tablete de dimensiune 1×1. Pierde jucătorul care nu mai poate efectua nici o mutare.
În fişierul de intrare se va afla numărul N (1 ≤ N ≤ 100) de tablete, iar pe următoarea linie sunt N perechi de numere întregi care reprezintă dimensiunile tabletelor.
În fişierul de ieşire se va afla un singur număr întreg reprezentând numărul mutărilor câştigătoare pentru primul jucător.
 
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$:
 
<tex>SG_{i,j} = mex(SG_{i,k} \verb|^| SG_{i,j-k}, (1 \leq k < j)</tex> mutarea întâi
<tex>\hspace{20mm}SG_{k,j} \verb|^| SG_{i-k,j}, (1 \leq k < i)</tex>
<tex>SG_{i,k} \verb|^| SG_{i,j-k-1}, (1 \leq k < j - 1)</tex> mutarea a doua
<tex>SG_{k,j} \verb|^| SG_{i-k-1,j}, (1 \leq k < i - 1)</tex>
<tex>SG_{i-2,j-2}) (i > 2 , j > 2)</tex> mutarea a treia

{*} poate să rupă şi să mănânce orice linie sau coloană de pătrăţele care nu se află pe marginea tabletei;
{*} 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
 
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$:
 
<tex> SG_{i,j} = mex(SG_{i,k} \verb|^| SG_{i,j-k}, (1 \leq k < j) </tex> mutarea întâi
<tex> SG_{k,j} \verb|^| SG_{i-k,j}, \hspace{21 mm}(1 \leq k < i) </tex>
<tex> SG_{i,k} \verb|^| SG_{i,j-k-1}, \hspace{17.5 mm} (1 \leq k < j - 1) </tex> mutarea a doua
<tex> SG_{k,j} \verb|^| SG_{i-k-1,j}, \hspace{17 mm} (1 \leq k < i - 1) </tex>
<tex> SG_{i-2,j-2}) \hspace{28 mm} (i > 2 , j > 2 )</tex> mutarea a treia

Acum, pentru a calcula numărul de mutări câştigătoare efectuăm asupra fiecărei tablete din fişierul de intrare toate mutările posibile care sunt cel mult de $4 • 100 + 1$ şi facem suma $XOR$ a valorilor Sprague Grundy pentru restul tabletelor neimplicate în mutare şi a tabletelor rezultate din mutare. Pentru a calcula $SG{~i,j~}$ trebuie sã parcurgem cel mult $2 • i + 2 • j + 1$ valori obţinute. Astfel, algoritmul de determinare al valorilor matricei $SG$ are ordinul de complexitatea $O(N^3^)$.
Complexitatea algoritmului care determină numărul de mutări câştigătoare este $O(N^2^)$.

Acum, pentru a calcula numărul de mutări câştigătoare efectuăm asupra fiecărei tablete din fişierul de intrare toate mutările posibile care sunt cel mult de $4 x 100 + 1$ şi facem suma $XOR$ a valorilor $Sprague Grundy$ pentru restul tabletelor neimplicate în mutare şi a tabletelor rezultate din mutare. Pentru a calcula $SG{~i,j~}$ trebuie sã parcurgem cel mult $2 x i + 2 x j + 1$ valori obţinute. Astfel, algoritmul de determinare al valorilor matricei $SG$ are ordinul de complexitatea $O(N^3^)$. Complexitatea algoritmului care determină numărul de mutări câştigătoare este $O(N^2^)$.
 
h2(#concluzii). Concluzii

Am văzut că aceste numere sunt folositoare pentru rezolvarea unor probleme de jocuri combinatorice. Chiar dacă numărul stărilor grafului nostru aciclic poate să fie foarte mare, putem să ne dăm seama, câteodată, din valorile mici de o regulă pe care o urmează numerele, sau măcar putem determina mai uşor configuraţii pentru care jocul are sau nu strategie de câştig, fapt care ne poate ajuta în descoperirea rezolvării generale.

h2(#probleme-propuse). Probleme suplimentare
 
* 'Got Root?':http://ipsc.ksp.sk/contests/ipsc2003/real/problems/g.php, _IPSC 2003_
 

h2(#bibliografie). Bibliografie

1. ***, colecţia GInfo
2. Mihai Oltean, Programarea Jocurilor Matematice, Editura Albastră, Cluj-Napoca, 1996
3. 'Thomas S. Ferguson, Game Theory Text (online)':http://www.math.ucla.edu/~tom/gamescourse.html
4. 'http://www.ams.org/new-in-math/cover/games1.html':http://www.ams.org/new-in-math/cover/games1.html
5. 'http://www.cut-the-knot.com':http://www.cut-the-knot.com
6. 'http://www.mathworld.wolfram.com':http://www.mathworld.wolfram.com
7. 'http://ipsc.ksp.sk/':http://ipsc.ksp.sk/

# 'Colecţia GInfo':http://www.ginfo.ro/
# Mihai Oltean, _Programarea Jocurilor Matematice_, Editura Albastră, Cluj-Napoca, 1996
# 'Thomas S. Ferguson, Game Theory Text (online)':http://www.math.ucla.edu/~tom/gamescourse.html
# 'Interactive Mathematics':http://www.cut-the-knot.com
# 'Wolfram MathWorld':http://www.mathworld.wolfram.com
# 'IPSC':http://ipsc.ksp.sk/