h1. Teoria jocurilor: numerele Sprague Grundy
h1. Teoria jocurilor: numerele Sprague-Grundy
(Categoria -, Autor _Cosmin Negruşeri_)
== include(page="template/implica-te/scrie-articole" user_id="portocala") ==
'Articol de transcris':downloads?action=download&file=SpragueGrundy.pdf
(Categoria _Matematică_, Autor _Cosmin Negruşeri_)
(toc){width: 20em}*{text-align:left;} *Continut*
* 'Introducere':numerele-sprague-grundy#intro
* 'Ce este jocul NIM?':numerele-sprague-grundy#nim
* 'Probleme care folosesc strategia NIM':numerele-spreague-grundy#probleme1
* 'Numerele Sprague Grundy':numerele-sprague-grundy#nsg
* 'Probleme care se pot rezolva cu numerele Sprague Grundy':numerele-sprague-grundy#probleme2
* 'Bibliografie':numerele-sprague-grundy#bib
(toc){width: 25em}*{text-align:center;} *Conţinut*
* 'Introducere':numerele-sprague-grundy#introducere
* 'Ce este jocul NIM?':numerele-sprague-grundy#jocul-nim
* 'Aplicaţii ale strategiei NIM':numerele-sprague-grundy#aplicatii-nim
* 'Numerele Sprague-Grundy':numerele-sprague-grundy#sprague-grundy
* 'Aplicaţii ale numerelor Sprague-Grundy':numerele-sprague-grundy#aplicatii-sg
* 'Concluzii':numerele-sprague-grundy#concluzii
* 'Probleme suplimentare':numerele-sprague-grundy#probleme-suplimentare
* 'Bibliografie':numerele-sprague-grundy#bibliografie
h2(#intro). Introducere
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 uner 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(#jocul-nim). Ce este jocul NIM?
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ã._
În rezolvare distingem mai multe cazuri:
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ă.
* 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.
* Pentru cazul trivial în care numãrul de grãmezi este egal cu 1, primul jucator 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.
De exemplu, dacă avem $4$ grămezi cu $1$, $3$, $5$, respectiv $7$ pietre:
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*$
* $*OOOOOOO*$
Atunci vom avea:
1 = (0001){~2~}
3 = (0011){~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.
* $*1 = (0001){~2~}*$
* $*3 = (0011){~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.
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, suma $XOR$ corespunzătoare noii stări, pe poziţia bitului de $*1*$ cel mai din dreapta în reprezentarea lui $x$, va avea valoarea $*1*$.
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ă al cărui număr de pietre are bitul $*1*$ pe poziţia celei mai mari puteri 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ă în $y$ se anulează bitul cel mai semnificativ al lui $x$). Atunci noua sumă $XOR$ va fi egală cu $*0*$.
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:
* $*17 - (17 ^ 29) = 17 - 12 = 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*$.
h2(#aplicatii-nim). Aplicaţii ale strategiei NIM
Exemplificăm în continuare câteva probleme în care se foloseşte strategia jocului $NIM$.
h3(#problema-1). Problema 1
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.
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.
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.
h3. Soluţie
De exemplu:
%{color:gray}4{@ ^ 8 ^ @}17 = (00100){~2~}{@ ^ @}(01000){~2~}{@ ^ @}(10001){~2~} = (11101){~2~} = 29%.
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).
Mutarea câştigãtoare constã în a lua din cea de-a treia gramadã un numãr de pietre egal cu:
%{color:gray}17 - (17 @^ 29) = 17 - 17 ^@ 29 = 5 = (00101){~2~}%.
h3(#problema-2). Problema 2 (Baraj ONI 1997)
Dupã acest pas grãmezile vor avea 4, 8, 12 pietre. Ne aflãm astfel într-o stare cu suma _XOR_ egalã cu 0.
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. Soluţie
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$.
h2(#probleme1). Probleme care folosesc strategia NIM
h3(#problema-3). Problema 3: 'Nim Game - Give Away!':http://acm.mipt.ru/judge/problems.pl?problem=103 (El Judge)
h3. Problema 1
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.
_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._
h3. Soluţie
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 întro poziţie de pierdere.
Când jucatorul care nu are strategie de câştig mutã înapoi _x_ casuţ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).
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ă distrugă o grămadă de $x$ pietre, jucătorul poate lua $x - 1$, iar dacă ar trebui să lase o singură piatră din grămada actuală, poate lua întreaga grămadă. Astfel, numărul de grămezi rămase va fi impar şi el nu va face ultima mutare.
h3. Problema 2
h2(#sprague-grundy). Numerele Sprague-Grundy
Aceastã problemã a fost propusã spre rezolvare participanţilor la barajul pentru lãrgirea lotului naţional din 1997.
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).
_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._
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.
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._
În continuare, considerăm următorul enunţ:
h3. Problema 3 _(El Judge MIPT online programming contest Nim Game Give Away!)_
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 mai poate muta.
_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._
Î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.
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.
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$.
h2(#nsg). Numerele Sprague Grundy
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$.
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).
_De ce este acest joc echivalent cu jocul NIM?_
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:
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} {\mathbin{\char`\^}} g_{i_2} {\mathbin{\char`\^}} g_{i_3} {\mathbin{\char`\^}} ... {\mathbin{\char`\^}} g_{i_n}</tex>.
_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._
Problema se rezolvă acum uşor efectuând o sortare topologică a nodurilor grafului aciclic şi numerotând nodurile folosind funcţia $mex$.
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.
h2(#aplicatii-sg). Aplicaţii ale numerelor 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 %{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.
În continuare, să studiem alte probleme ce se pot rezolva cu numerele $Sprague-Grundy$.
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._
h3(#problema-4). Problema 4: Joc (Bursele Agora 2003/2004, Runda 13)
h4. _De ce este acest joc echivalent cu jocul NIM?_
bq. Să se verifice existenţa unei strategii de câştig pentru un joc similar cu $NIM$ în care se poate lua dintr-o grămadă o piatră sau un număr prim de pietre.
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,_ %{color:gray} {_SG_}({_i{~1~}_}, …, {_i{~n~}_}) = {_gi{~1~}_} {@^@} _gi{~2~}_ {@^@} _gi{~3~}_ {@^ … ^@} {_gi{~n~}_}%.
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$.
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._
h3(#problema-5). Problema 5: 'Stone game':http://acm.mipt.ru/judge/problems.pl?problem=101 (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~} ≤ 10^200^$.
h2(#probleme2). Probleme care se pot rezolva folosind numerele Sprague Grundy
h3. Soluţie
h3. Problema 4
Să determinăm valorile $Sprague-Grundy$ pentru grămezi mici:
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.
$0 : 0; 1 : 1; 2 : 2; 3 : 0; 4 : 1; 5 : 2; 6 : 0$
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._
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 un număr cu $200$ de cifre este simplu de găsit determinând suma cifrelor numărului.
h3. Problema 5 _(El Judge MIPT online programming contest, Stone game)_
h3(#problema-6). Problema 6: 'Stone game II':http://acm.mipt.ru/judge/problems.pl?problem=102 (El Judge)
_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 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$.
Sã determinãm valorile Sprague Grundy pentru grãmezi mici:
%{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. Soluţie
h3. Problema 6 _(El Judge MIPT online programming contest, Stone game II)_
Numărul $100000$ nu este foarte mare şi valorile $Sprague-Grundy$ pot fi determinate _off-line_ şi incluse în programul nostru sub formă de constante. Putem scrie pentru valori mici secvenţa $Sprague-Grundy$:
_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._
$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$
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ã.
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, Cluj-Napoca, problema Sticks)_
h3(#problema-7). Problema 7: Sticks (CEOI 2000)
_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$, $7$, $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._
h3. Soluţie
h3. Problema 8
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 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#bib, pe site-ul '[7]':numerele-sprague-grundy#bib, sau pe siteul concursului '.campion':http://campion.edu.ro.
h3(#problema-8). Problema 8: 'Joc':problema/joc2 (Bursele Agora 2006)
h3. Problema 9
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ă;
{*} pot să rupă şi să mănânce orice linie sau coloană de pătrăţele care nu se află pe marginea tabletei;
{*} pot 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$.
Niciuna 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 nicio mutare. În fişierul de intrare se va afla numărul $N$ ({$1 ≤ N ≤ 100$}) de tablete, iar pe următoarea linie vor fi $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.
Aceastã problemã a fost propusã spre rezolvare la ediţia din acest an a Olimpiadei Naţionale de Informaticã din Ucraina.
h3. Soluţie
_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$:
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( \underbrace{ \underbrace{SG_{i,k} {\mathbin{\char`\^}} SG_{i,j-k},}_{1 \leq k < j} \underbrace{SG_{k,j} {\mathbin{\char`\^}} SG_{i-k,j},}_{1 \leq k < i} }_{mutarea\ \^{i}nt\^{a}i } </tex> <tex> \underbrace{ \underbrace{SG_{i,k} {\mathbin{\char`\^}} SG_{i,j-k-1},}_{1 \leq k < j - 1} \underbrace{SG_{k,j} {\mathbin{\char`\^}} SG_{i-k-1,j},}_{1 \leq k < i - 1} }_{mutarea\ a\ doua} </tex> <tex> \underbrace{ \underbrace{SG_{i-2,j-2}}_{i > 2,\ j > 2} }_{mutarea\ a\ treia} )</tex>
_SG{~i,j~}_ = mex({_SG{~i,k~}_} ^ _SG{~i,j-k~},_ (1 ≤ _k_ < {_j_}) mutarea întâi
_SG{~k,j~}_ ^ _SG{~i-k,j~},_ (1 ≤ _k_ < {_i_})
_SG{~i,k~}_ ^ _SG{~i,j-k-1~},_ (1 ≤ _k_ < {_j - 1_}) mutarea a doua
_SG{~k,j~}_ ^ _SG{~i-k-1,j~},_ (1 ≤ _k_ < {_i - 1_})
{_SG{~i-2,j-2~}_}) ({_i_} > 2 şi _j_ > 2) 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 $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 a valorilor matricei $SG$ are ordinul de complexitate $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 • 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^)._
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.
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(#bib). Bibliografie
h2(#probleme-suplimentare). Probleme suplimentare
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/
* 'Joc3':problema/joc3
* 'Got Root?':http://ipsc.ksp.sk/contests/ipsc2003/real/problems/g.php, _IPSC 2003_
Cosmin-Silvestru Negruşeri este student în anul III la Universitatea Babeş-Bolyai din Cluj-Napoca. El poate fi contactat prin e-mail la adresa [email protected]._
h2(#bibliografie). Bibliografie
* 'Colecţia GInfo':http://www.ginfo.ro/
* Mihai Oltean - _Programarea Jocurilor Matematice_, Editura Albastră, Cluj-Napoca, 1996
* Thomas S. Ferguson - 'Game Theory Text':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/
