Teoria jocurilor: numerele Sprague Grundy

Teoria jocurilor: numerele Sprague-Grundy

h1. Teoria jocurilor: numerele Sprague Grundy

h1. Teoria jocurilor: numerele Sprague-Grundy

== include(page="template/implica-te/scrie-articole" user_id="portocala") ==
(Categoria _Matematică_, Autor _Cosmin Negruşeri_)

(toc){width: 28em}*{text-align:center;} *Conţinut*

(toc){width: 25em}*{text-align:center;} *Conţinut*

* 'Introducere':numerele-sprague-grundy#introducere
* 'Ce este jocul NIM?':numerele-sprague-grundy#jocul-nim
* 'Aplicaţii ale strategiei NIM':numerele-sprague-grundy#aplicatii-nim

* 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 $4$ grămezi cu $1$, $3$, $5$ respectiv $7$ pietre:

De exemplu, dacă avem $4$ grămezi cu $1$, $3$, $5$, respectiv $7$ pietre:

* $*O*$
* $*OOO*$

* $*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, suma $XOR$ corespunzătoare noii stări, pe poziţia bitului de $*1*$ cel mai din dreapta în reprezentarea 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ă al cărui număr de pietre are bitul $*1*$ pe poziţia celei mai mari puteri 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ă în $y$ se anulează bitul cel mai semnificativ al lui $x$). Atunci noua sumă $XOR$ va fi egală cu $*0*$.

De exemplu:

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 - 12 = 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*$.