bq. Se consideră $N$ grămezi de pietre. Doi jucători, vor ridica alternativ oricâte pietre dintr-o singură grămadă. Câştigătorul este cel care ia ultima piatră.

h3. Soluţie

În rezolvare distingem mai multe cazuri:

* Pentru cazul trivial în care numărul de grămezi este egal cu $1$, primul jucător are, evident, strategie de câştig, el putând lua toate pietrele din grămadă.
* Dacă numărul de grămezi este egal cu $2$, primul jucător are strategie de câştig atunci când numărul de pietre din prima grămadă este diferit de numărul de pietre din cea de-a doua, strategia lui fiind cea de a aduce tot timpul grămada mai mare la numărul de pietre al grămezii mai mici, şi cum jocul este finit, înseamnă că primul jucător o să aducă jocul în starea $(0, 0)$.

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.

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:

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

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.

Întrucât 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.

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

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

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

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

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