h2. Indicaţii de rezolvare
Jocul imparţial propus în această problemă se numeşte 'jocul NIM':http://en.wikipedia.org/wiki/Nim, stând la baza teoriei jocurilor. 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.
Jocul imparţial propus în această problemă se numeşte 'jocul NIM':http://en.wikipedia.org/wiki/Nim, stând la baza teoriei jocurilor. Numim stare câştigătoare o configuraţie a grămezilor pentru care primul jucător are strategie sigură de câştig, respectiv stare necâştigatoare o configuraţie pentru care primul jucator va pierde. Se observă că stările câştigătoare corespund situaţiilor în 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:
Pentru a demonstra acest lucru, următoarele condiţii 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.
# Dintr-o stare cu suma XOR 0, se poate ajunge doar în stări cu suma XOR pozitivă, sau jocul se termină. Scăzând din orice gramadă o cantitate pozitivă, evident vom schimba configuraţia binară a numărului de pietre cu cel putin un bit, deci şi suma XOR. Jocul se termină cand toate gramezile au 0 pietre, deci şi suma XOR va fi 0.
# Dintr-o stare cu suma XOR pozitiva, se poate ajunge intr-o stare cu suma XOR 0. Căutăm o gramadă cu un număr X de pietre, care are un bit de 1 pe poziţia bitului cel mai semnificativ al sumei XOR, notată cu S. Din acea grămadă se vor scădea X - (X XOR S) pietre, (X XOR S) fiind mai mic decat X deoarece se anulează bitul cel mai semnificativ al lui S. Suma XOR rămasă după scădere este egală cu 0.
Pentru o demonstratie mai pe larg si alte variante de joc NIM, puteti consulta acest 'articol':http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf
Pentru o demonstraţie mai pe larg şi alte variante de joc NIM, puteţi consulta acest 'articol':http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf
h2. Aplicatii
h2. Aplicaţii
* 'Xerox':problema/xerox
* 'Joc3':problema/joc3
