h1. Teoria jocurilor: numerele Sprague Grundy

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

(Categoria -, Autor _Cosmin Negruşeri_)

(Categoria _Matematica_, Autor _Cosmin Negruşeri_)

'Articol de transcris':downloads?action=download&file=SpragueGrundy.pdf

(toc){width: 28em}*{text-align:center;} *Conţinut*

(toc){width: 20em}*{text-align:left;} *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
* 'Numerele Sprague Grundy':numerele-sprague-grundy#sprague-grundy
* 'Probleme care se rezolvă cu numerele Sprague Grundy':numerele-sprague-grundy#probleme-sg

* 'Probleme care folosesc strategia NIM':numerele-spreague-grundy#probleme1
* 'Numerele Sprague Grundy':numerele-sprague-grundy#numerele-sprague-grundy
* 'Probleme care se pot rezolva cu numerele Sprague Grundy':numerele-sprague-grundy#probleme2

* '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.

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?

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

Pentru început ne vom familiariza cu jocul clasic _*NIM*_:

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

_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

h4. Soluţie

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

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

* Dacă numărul de grămezi este mai mare decât doi, strategia se complică şi nu se mai observă cu "ochiul liber". Stările câştigătoare pentru mai multe grămezi sunt acele stări pentru care suma $XOR$ a numerelor de pietre din grămezi este diferită de $0$, restul stărilor fiind de pierdere.

* Dacă numărul de grămezi este mai mare decât doi strategia se complică şi nu se mai observă cu "ochiul liber". Stările câştigătoare pentru mai multe grămezi sunt acele stări pentru care suma $XOR$ a numerelor de pietre din grămezi este diferită de $0$, restul stărilor fiind de pierdere.

De exemplu, dacă avem o gramadă cu o piatră, o gramadă cu trei pietre, o gramadă cu cinci pietre şi o gramadă cu şapte pietre:

$o$
$ooo$
$ooooo$
$oooooo$

o
ooo
ooooo
oooooo

Atunci vom avea:
$1 = (0001){~2~}$

$5 = (0101){~2~}$
$7 = (0111){~2~}$

Efectuând '$XOR$':http://www.fredosaurus.com/notes-cpp/expressions/bitops.html (operatorul $^$ în $C/C++$) între reprezentãrile binare ale numerelor  obţinem $0 = (0000){~2~}$. Conform propoziţiei de mai sus această stare este de pierdere.

Efectuând '$XOR$':http://www.fredosaurus.com/notes-cpp/expressions/bitops.html (operatorul ^ în C/C++) între reprezentãrile binare ale numerelor  obţinem $0 = (0000){~2~}$. Conform propoziţiei de mai sus această stare este de pierdere.

Să demonstrăm cele afirmate. Dintr-o poziţie cu suma $XOR$ egală cu $0$, pentru orice mutare ajungem evident la o poziţie cu suma $XOR$ diferită de $0$, pentru că luând dintr-o grămadă un număr $x$ de pietre, în suma $XOR$ corespunzătoare noii stări bitul cel mai semnificativ al lui $x$ va avea valoarea $1$.

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

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

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

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.

h3. Problema 2

Această problemă a fost propusă spre rezolvare participanţilor la barajul pentru lărgirea lotului naţional din 1997.

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

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

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 _(El Judge MIPT online programming contest Nim Game Give Away!)_

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.

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

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

h2(#numerele-sprague-grundy). Numerele Sprague Grundy

Jocurile care prezintă interes pentru jucători sunt acelea care necesită examinarea unui număr foarte mare de stări pentru determinarea strategiei de câştig, deoarece în caz contrar câştigătorul s-ar cunoaşte chiar de la început. Spre deosebire de aceştia, matematicienii sau informaticienii sunt interesaţi de determinarea unor strategii pentru astfel de jocuri.
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).

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(#probleme-sg). Probleme care se pot rezolva folosind numerele Sprague Grundy

h2(#probleme2). Probleme care se pot rezolva folosind numerele Sprague Grundy

h3. Problema 4