Diferente pentru numerele-sprague-grundy intre reviziile #36 si #38

Nu exista diferente intre titluri.

Diferente intre continut:

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). Problema 3 ('Nim Game - Give Away!':http://acm.mipt.ru/judge/problems.pl?problem=103, El Judge)
h3(#problema-3). Problema 3: 'Nim Game - Give Away!':http://acm.mipt.ru/judge/problems.pl?problem=103 (El Judge)
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.
În continuare, să studiem alte probleme ce se pot rezolva cu numerele $Sprague-Grundy$.
h3(#problema-4). Problema 4 (Joc, Bursele Agora 2003/2004, Runda 13)
h3(#problema-4). Problema 4: Joc (Bursele Agora 2003/2004, Runda 13)
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$.
h3(#problema-5). Problema 5 ('Stone game':http://acm.mipt.ru/judge/problems.pl?problem=101, 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^$.
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, 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$.
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). Problema 7 (Sticks, CEOI 2000)
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$, $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(#problema-8). Problema 8 ('Joc':problema/joc2, Bursele Agora 2006)
h3(#problema-8). Problema 8: 'Joc':problema/joc2 (Bursele Agora 2006)
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ă;
* 'Interactive Mathematics':http://www.cut-the-knot.com
* 'Wolfram MathWorld':http://www.mathworld.wolfram.com
* 'IPSC':http://ipsc.ksp.sk/
 
h2. Discuţii pe forum
 

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.