DA
|

h3. Explicaţie

h2. Indicatii de rezolvare
 
Numim stare castigatoare o configuratie a gramezilor pentru care primul jucator are strategie sigura de castig, respectiv stare necastigatoare o configuratie pentru care primul jucator va pierde. Se observa ca starile castigatoare corespund situatiilor in care suma XOR a numerelor de pietre din gramezi este mai mare ca 0.
 
Pentru a demonstra acest lucru, urmatoarele conditii sunt necesare si suficiente:
 
# Dintr-o stare cu suma XOR 0, se poate ajunge doar in stari cu suma XOR pozitiva, sau jocul se termina. Scazand din orice gramada o cantitate poztiva, evident vom schimba configuratia binara a numarului de pietre cu cel putin un bit, deci si suma XOR. Jocul se termina cand toate gramezile au 0 pietre, deci si suma XOR va fi 0.
# Dintr-o stare cu suma XOR pozitiva, se poate ajunge intr-o stare cu suma XOR 0. Cautam o gramada cu un numar X de pietre, care are un bit de 1 pe pozitia bitului cel mai semnificativ al sumei XOR, notata cu S. Din acea gramada se vor scadea X - (X XOR S) pietre, (X XOR S) fiind mai mic decat X deoarece se anuleaza bitul cel mai semnificativ al lui S. Suma XOR ramasa dupa scadere este egala cu 0.
 
 
h2. Aplicatii
 

...

== include(page="template/taskfooter" task_id="nim") ==