h3. Adunarea xor

Vom aduna jocurile {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~N~}$} astfel incat la fiecare pas jucatorul care urmeaza trebuie sa isi aleaga exact un joc si sa faca o mutare in jocul respectiv. Jucatorul care nu mai poate muta pierde. Un astfel de joc este generalizarea jocului cu un pion din capitolul precedent si se intalneste in problema 'Pawns':problema/pawns, data la concursul national Bursele Agora. Pentru a determina castigatorul in cazul acestui joc, ne vom folosi de urmatoarea teorema:

Vom aduna jocurile {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~P~}$} astfel incat la fiecare pas jucatorul care urmeaza trebuie sa isi aleaga exact un joc si sa faca o mutare in jocul respectiv. Jucatorul care nu mai poate muta pierde. Un astfel de joc este generalizarea jocului cu un pion din capitolul precedent si se intalneste in problema 'Pawns':problema/pawns, data la concursul national Bursele Agora. Pentru a determina castigatorul in cazul acestui joc, ne vom folosi de urmatoarea teorema:

_Teorema_: Pentru un anumit joc $G$ care este suma jocurilor {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~P~}$} dupa cum a fost definita mai sus o stare {$v = (v{~1~},v{~2~}, ..., v{~P~})$} este pierzatoare daca si numai daca {$mex(x{~1~}) xor mex(x{~2~}) xor ... xor mex(x{~P~}) = 0$}.

_Teorema_: Pentru un anumit joc $G$ care este suma jocurilor {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~P~}$} dupa cum a fost definita mai sus o stare este pierzatoare daca si numai daca {$mex(x{~1~}) xor mex(x{~2~}) xor ... xor mex(x{~P~}) = 0$}, unde x{~i~} reprezinta .

_Demonstratie_: Vom arata ca jocul $G$ este echivalent cu un joc $NIM$ cu $N$ gramezi in care gramada $i$ are {$mex(v{~i~})$} pietre. In jocul $NIM$ putem alege o gramada cu {$mex(x{~i~})$} pietre si sa luam cateva astfel incat in gramada sa ramana a<g(xi) pietre. Acestei mutari in jocul NIM ii corespunde o mutare in jocul compus G in care se alege jocul individual Gi si se muta din stare curenta xi intr-o stare y cu g(y)=a. Deoarece a<g(xi) va exista mereu o astfel de stare y. Nu vom lua in considerare mutarile cand dintr-o stare xi se muta intr-o stare y cu g(y)>g(xi) deoarece urmatorul jucator poate muta din starea y intr-o stare z cu g(z)=g(xi) si anuleaza practic mutarea precedentului. (de editat)