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, clasele XI-XII

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 in sus, sa se precizeze care jucator castiga.

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 &le; 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%!