Majoritatea jocurilor imparţiale se pot reduce la jocul prezentat în problema _Pioni_ de la runda 47 a concursului de programare Bursele Agora. Acolo se menţiona următorul joc:

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

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.

Cum graful este aciclic, jocul este finit şi are întotdeauna un câştigător. Practic, acest joc este suma unor jocuri, mai precis suma a mai multor jocuri cu un singur pion pe graful aciclic. Jocul cu un singur pion poate fi analizat destul de uşor, fiecare nod al grafului putând fi colorat cu alb sau negru după cum există sau nu strategie de câştig dacă în nodul curent ar fi poziţionat pionul. Această colorare poate fi realizată uşor dacă se porneşte de la nodurile fără urmaş şi la fiecare pas se colorează câte un nod ai cărui urmaşi sunt deja coloraţi. Orice joc imparţial poate fi redus la un joc cu un singur pion. Nodurile sunt poziţiile jocului şi arcele grafului sunt mutările posibile din fiecare poziţie. Jocul iniţial poate fi şi el transformat, dar numărul de noduri creşte foarte mult (pentru $n$ pioni şi $m$ noduri, numărul de noduri din jocul transformat este {$n^m^$}) şi nu este practic să colorăm graful rezultat. Folosind teoria dezvoltatã de Sprague şi Grundy, putem reduce complexitatea analizei jocului cu $n$ pioni la complexitatea analizei jocului cu un pion.

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

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

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

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

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

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

h3. Problema 7 (CEOI 2000, problema Sticks)

_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ă._

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

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

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

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

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