== include(page="template/implica-te/scrie-articole" user_id="portocala") ==

(Categoria _Matematică_, Autor _Cosmin Negruşeri_)

(Categoria _Matematica_, Autor _Cosmin Negruşeri_)

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

$o$
$ooo$
$ooooo$

$ooooooo$

$oooooo$

Atunci vom avea:

$1 = (0001){~2~}$
$3 = (0011){~2~}$
$5 = (0101){~2~}$

Mai rămâne de demonstrat că din orice poziţie cu suma $XOR$ diferită de $0$ putem trece printr-o mutare convenabilă într-o poziţie cu suma $XOR$ egală cu $0$. Căutăm o grămadă care are un număr de pietre mai mare sau egal cu cea mai mare putere a lui $2$ care apare în suma $XOR$. Fie $x$ valoarea sumei $XOR$ a tuturor grămezilor şi $y$ numărul de pietre din grămada găsită mai devreme. O mutare "câştigătoare" este extragerea din grămada găsită care are $y$ pietre a {$y - (x XOR y)$} pietre ({$x XOR y$} este mai mic decât $y$ pentru că se anulează biţii cei mai semnificativi ai lui $y$ şi $x$). Atunci noua sumă $XOR$ va fi egală cu $0$.

De exemplu:
 

De exemplu:

$4{@ ^ 8 ^ @}17 = (00100){~2~}{@ ^ @}(01000){~2~}{@ ^ @}(10001){~2~} = (11101){~2~} = 29$.

Mutarea câştigătoare constă în a lua din cea de-a treia gramadă un număr de pietre egal cu:
 

Mutarea câştigătoare constă în a lua din cea de-a treia gramadă un număr de pietre egal cu:

$17 - (17 @^ 29) = 17 - 17 ^@ 29 = 5 = (00101){~2~}$.
După acest pas grămezile vor avea $4$, $8$, $12$ pietre. Ne aflăm astfel într-o stare cu suma $XOR$ egală cu $0$.

h3. Problema 1

bq. Pe o tablă de şah, care are $n × 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.

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.

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

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
Această problemă a fost propusă spre rezolvare participanţilor la barajul pentru lărgirea lotului naţional din 1997.

bq. Pe o linie sunt plasate la coordonate întregi $2 × 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.

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.

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

Toate jocurile imparţiale cu doi jucători cu informaţie totală pot fi reduse la jocul *$NIM$* care se joacă cu nişte grămezi virtuale, în care mutările posibile sunt extragerea oricâtor pietre dintr-o grămadă sau adăugarea oricâtor pietre la o grămadă (aşa cum am menţionat anterior, adãugarea de pietre la o grămadă nu complică analiza jocului).
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:

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

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

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 %{color:gray} $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$.

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.

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

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

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

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._
Să determinăm valorile Sprague Grundy pentru grămezi mici:

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

%{color:gray}$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.

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

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

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

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

$1 2 3 4 5 6 7 8 9 10 11 12 13 14$
$0 1 0 2 1 3 0 4 2  5  1  6  3  7$

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)

h3. Problema 7 _(CEOI 2000, Cluj-Napoca, 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ă._