Diferente pentru numerele-sprague-grundy intre reviziile #16 si #17

Nu exista diferente intre titluri.

Diferente intre continut:

h3. Soluţie
* Pentru cazul trivial în care numărul de grămezi este egal cu $1$, primul jucător are, evident, strategie de câştig, el putând lua toate pietrele din grămadă.
* 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 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 o gramadă cu o piatră, o gramadă cu trei pietre, o gramadă cu cinci pietre şi o gramadă cu şapte pietre:
$o$
$ooo$
$ooooo$
$ooooooo$
$*o*$
$*ooo*$
$*ooooo*$
$*ooooooo*$
Atunci vom avea:
$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$.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.