h3(#problema-4). Problema 4 (Joc, Bursele Agora 2003/2004, Runda 13)

În acestă problemă se cere să verificăm 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.

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.

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

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

h3(#problema-5). Problema 5 ('Stone game':http://acm.mipt.ru/judge/problems.pl?problem=101&CGISESSID=b4a5b84bd176d84796a209dc7c8002b8, El Judge)

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

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

h3. Soluţie

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

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-6). Problema 6 ('Stone game II':http://acm.mipt.ru/judge/problems.pl?problem=102&CGISESSID=b4a5b84bd176d84796a209dc7c8002b8, El Judge)

h3(#problema-6). Problema 6 ('Stone game II':http://acm.mipt.ru/judge/problems.pl?problem=102, El Judge)

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

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

h3. Soluţie

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$:

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$:

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

h3(#problema-7). Problema 7 (Sticks, CEOI 2000)

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

h3. Soluţie

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

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(#problema-8). Problema 8 ('Joc':problema/joc2, Bursele Agora 2006)

{*} 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 x 1$.

Nici una 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 nici o mutare.

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.

h3. Soluţie
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$:

TODO start

<tex> SG_{i,j} = mex(SG_{i,k} {\mathbin{\char`\^}} SG_{i,j-k}, (1 \leq k < j) </tex> mutarea întâi
<tex> SG_{k,j} {\mathbin{\char`\^}} SG_{i-k,j}, \hspace{21 mm}(1 \leq k < i) </tex>
<tex> SG_{i,k} {\mathbin{\char`\^}} SG_{i,j-k-1}, \hspace{17.5 mm} (1 \leq k < j - 1) </tex> mutarea a doua

<tex> SG_{i-2,j-2}) \hspace{28 mm} (i > 2 , j > 2 )</tex> 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 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^)$.

TODO end

h2(#concluzii). Concluzii

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 (online)':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/
 

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