* 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 o gramadă cu o piatră, o gramadă cu trei pietre, o gramadă cu cinci pietre şi o gramadă cu şapte pietre:
De exemplu, dacă avem $4$ grămezi cu $1$, $3$, $5$ respectiv $7$ pietre:
$*o*$
$*ooo*$
$*ooooo*$
$*ooooooo*$
* $*O*$
* $*OOO*$
* $*OOOOO*$
* $*OOOOOOO*$
Atunci vom avea:
$1 = (0001){~2~}$
$3 = (0011){~2~}$
$5 = (0101){~2~}$
$7 = (0111){~2~}$
* $*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.
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$.
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*$.
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$.
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:
$4{@ ^ 8 ^ @}17 = (00100){~2~}{@ ^ @}(01000){~2~}{@ ^ @}(10001){~2~} = (11101){~2~} = 29$.
* $*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 - 17 ^@ 29 = 5 = (00101){~2~}$.
* $*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$.
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
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
h3. Problema 2 (Baraj, ONI 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 × 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$.
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.
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.
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.
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
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).
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).
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.
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:
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.
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$.
