Jocul de mai sus este similar cu jocul de {$NIM$}, numai ca aici nu putem lua oricate pietre dintr-o gramada, ci doar o singura piatra sau un numar prim de pietre. Pentru a rezolva problema, facem urmatoarea observatie: jocul cu mai multe gramezi respecta 'proprietatile unei adunari de tip xor':teoria-jocurilor/adunarea-jocurilor a jocurilor cu o singura gramada, deoarece la fiecare pas jucatorul care urmeaza trebuie sa isi aleaga exact un joc (o gramada) si sa faca o mutare in jocul respectiv. Conform teoremei, rezulta ca trebuie sa determinam valoarea $mex$ pentru o gramada cu $x$ pietre, si apoi sa facem suma-xor a valorilor corespunzatoare marimilor celor $N$ gramezi. In cazul in care suma-xor este diferita de {$0$} va castiga jucatorul care muta primul, iar in caz contrar va castiga celalalt jucator.
!<teoria-jocurilor/probleme?graf1.jpg 90%!
Mai ramane de calculat valoarea $mex$ pentru o gramada cu {$x$} pietre. Putem construi un graf orientat, aciclic, in care nodul numerotat cu {$x$}, {$x ≥ 0$}, reprezinta o gramada de dimensiune {$x$}. In acest graf va exista arc de la $x$ la $y$ doar daca $x - y$ este egal cu $1$ sau este un numar prim. Astfel, un arc reprezinta o posibila mutare in jocul dat.
!teoria-jocurilor/probleme?graf1.jpg!
Vom incerca sa calculam valorile Sprague-Grundy corespunzatoare nodurilor acestui graf.
Vom incerca sa calculam valorile Sprague-Grundy corespunzatoare nodurilor acestui graf. In tabelul de mai jos sunt prezentate aceste valori pentru primele noduri ale grafului.
|_. nod| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10|
|_. SG| 0| 1| 2| 3| 0| 1| 2| 3| 0| 1| 2|
Se poate demonstra prin inductie dupa $n$ ca valoarea asociata nodului $n$ este {$n modulo 4$}. Pentru {$0 ≤ n ≤ 3$} afirmatia este adevarata. Presupunem afirmatia adevarata pentru orice {$m < n$}. Din gramada de $n$ obiecte pot fi luate unul, doua sau trei obiecte, deci valoarea pentru $n$ nu poate fi niciuna din valorile pentru {$n-1$}, {$n-2$} si {$n-3$}. Valoarea {$n modulo 4$} este deocamdata cea mai mica valoare care nu este inca eliminata si poate corespunde gramezii cu $n$ obiecte. Este usor de aratat ca aceasta valoare nu va fi eliminata. Presupunem prin reducere la absurd ca valoarea ar fi eliminata, deci putem alege un numar prim $p$ de obiecte din cele $n$ astfel incat {$(n-p) modulo 4 = n modulo 4$}, echivalent cu {$p modulo 4 = 0$}, fals, deoarece $p$ era un numar prim. In concluzie, afirmatia pentru $n$ este adevarata si, conform principiului inductiei matematice, este adevarata pentru orice $n$ numar natural. In concluzie, valoarea Sprague-Grundy pentru nodul $n$ este {$n modulo 4$}.
h3. 3. 'Cartonase':problema/cartonase, concursul national .campion 2007-2008, clasele XI-XII
Coreland toate observatiile de mai sus, primul jucator castiga daca si numai daca {$(x{~1~} mod 4) xor (x{~2~} mod 4) ... xor (x{~N~} mod 4)$} este diferit de {$0$}.
h3. 2. 'Cartonase':problema/cartonase, concursul national .campion, 2007-2008
Fie $N$ cartonase asezate in linie dreapta pe o masa si doi jucatori care muta alternativ. Fiecare cartonas are o fata colorata in rosu, iar cealalta in albastru. O mutare consta in alegerea unui cartonas cu fata rosie in sus si intoarcerea lui. In plus, daca doreste, cel care e la mutare poate sa isi aleaga orice alt cartonas (indiferent de culoarea fetei care este in sus) care se afla la stanga celui ales initial si sa il intoarca. Stiind culorile fetelor care sunt initial in sus, sa se precizeze care jucator castiga.
Acest joc este cunoscut in literatura de specialitate ca _Turning Turtles_, si este de fapt echivalent cu 'jocul NIM':teoria-jocurilor/jocul-nim, studiat in acest articol. Putem asocia unui cartonas rosu situat pe pozitia $i$ o gramada cu $i$ pietre in jocul {$NIM$}. Se pot observa urmatoarele:
* Starea finala din problema este cea in care nu mai exista niciun cartonas cu fata rosie in sus. Deasemenea, in jocul {$NIM$}, se ajunge in starea finala cand toate gramezile de pietre sunt vide.
* Daca un jucator intoarce un singur cartonas rosu situat pe pozitia $i$, mutarea lui este echivalenta cu a lua toate pietrele din gramada ce contine $i$ pietre.
* Daca un jucator intoarce cartonasul rosu de pe pozitia $i$, iar apoi mai intoarce un alt cartonas de pe pozitia $j$ ({$1 ≤ j < i$}), avem urmatoarele posibilitati:
** cartonasul de pe pozitia $j$ este albastru: dupa ce se efectueaza mutarea, vom avea pe pozitia $j$ un cartonas rosu, iar pe pozitia $i$ un cartonas albastru. Aceasta mutare este echivalenta cu a lua exact $i-j$ pietre din gramada ce contine $i$ pietre, obtinand o gramada cu $j$ pietre.
** cartonasul de pe pozitia $j$ este rosu: dupa ce se efectueaza mutarea, vom aveam pe pozitiile $i$ si $j$ cartonase albastre, inainte acestea fiind rosii. Aceasta mutare este echivalenta cu a lua toate pietrele din gramezile ce contineau {$i$}, respectiv {$j$} pietre. Insa in jocul {$NIM$}, a lua toate pietrele din gramezile ce contin $i$, respectiv $j$ pietre este echivalent cu a lua $i-j$ pietre din gramada cu $i$ pietre, deoarece suma-xor a numerelor de pietre din gramezi nu se schimba.
Folosindu-ne de aceste observatii, putem concluziona ca primul jucator va castiga atunci si numai atunci cand suma-xor a pozitiilor unde se afla cartonasele cu fata rosie in sus este diferita de {$0$}.
h3. 3. 'A Coloring Game':http://acm.sgu.ru/problem.php?contest=0&problem=328, concurs regional, Rusia, 2007
Fie $N$ casute asezate in linie una dupa alta. Initial, fiecare casuta are exact una din cele trei stari posibile: necolorata, colorata in rosu, colorata in albastru. Sunt doi jucatori care muta alternativ. Prin mutare se intelege colorarea unei casute necolorate in rosu sau in albastru, astfel incat, la fiecare pas, sa nu existe doua casute adiacente colorate la fel. Sa se precizeze care jucator are strategie sigura de castig.
Pentru a rezolva aceasta problema ne vom folosi de 'numerele Sprague-Grundy':teoria-jocurilor/numere-SG si de teoria prezentata in capitolul 'Adunarea jocurilor':teoria-jocurilor/adunarea-jocurilor. Se observa ca sirul initial de casute poate fi divizat in mai multe subsecvente maximale disjuncte, astfel incat fiecare subsecventa este de unul din cele $4$ tipuri prezentate mai jos:
* subsecventa cu ambele capete necolorate (tip {$1$})
* subsecventa cu un capat colorat si cu un capat necolorat (tip {$2$})
* subsecventa cu ambele capete colorate la fel (tip {$3$})
* subsecventa cu un capat colorat in rosu, iar celalalt in albastru (tip {$4$})
Colorarea unei casute inseamna o mutare in jocul determinat de subsecventa careia apartine casuta. Cum la fiecare pas se alege un singur joc din cele existente si se efectueaza o singura mutare in acest joc, suntem in cazul unei adunari de tip xor a jocurilor. In consecinta, vom determina valorile Sprague-Grundy pentru fiecare joc independent in parte si vom face suma-xor a acestor valori.
Sa notam cu {$A{~n~}$} valoarea Sprague-Grundy a unei secvente de lungime {$n$} de tipul {$1$}. Similar, se noteaza cu {$B{~n~}$}, {$C{~n~}$} si {$D{~n~}$} valorile pentru secvente de lungime $n$ de tipul {$2$}, $3$ si respectiv {$4$}. Pentru a calcula efectiv aceste valori facem toate mutarile posibile si calculam $mex$ dintre valorile obtinute.
h3. 4. Triomino, Bytecode, 2008.
!>teoria-jocurilor/probleme?triomino.jpg 70%!
Fie o tabla cu doua linii si $N$ coloane si doi jucatori care muta alternativ. La fiecare pas, jucatorul aflat la mutare aseaza pe tabla o piesa de forma celei din figura alaturata, astfel incat aceasta piesa sa nu se suprapuna (nici macar partial) peste alte piese deja asezate pe tabla. Atunci cand este asezata, piesa poate fi rotita cu {$90$}, {$180$} sau {$270$} de grade. Sa se precizeze care din cei doi jucatori are strategie de castig. De exemplu, pentru {$N = 3$}, jucatorul care muta primul are strategie de castig, iar pentru {$N = 4$} ce de-al doilea jucator are o astfel de strategie. Se cere un algoritm de complexitate {$O(N^2^)$}.
h3. 5. 'Chess Training':http://www.topcoder.com/stat?c=problem_statement&pm=6866&rd=10808, Topcoder, SRM 384
Aplicatie pt. WTIA
p{margin:1em; padding: 0.5em; height: 45px; border-top: 1px solid silver;}=.
'Notiuni de baza':teoria-jocurilor | 'Jocul NIM':teoria-jocurilor/jocul-nim | 'Numere Sprague-Grundy':teoria-jocurilor/numere-SG |
