infoarena informatica de performanta

Adunarea or

Sa presupunem ca dorim sa adunam jocurile G₁, G₂, ..., G_P, astfel incat la fiecare pas jucatorul care urmeaza poate sa isi aleaga oricate jocuri si sa faca o mutare in fiecare din jocurile alese. Jucatorul care nu mai poate muta pierde. Un astfel de caz se intalneste in problema Pioni.

Teorema: Pentru un anumit joc G care este suma jocurilor G₁, G₂, ..., G_N dupa cum a fost definita mai sus o stare v = (v₁,v₂, ..., v_N) este pierzatoare daca si numai daca mex(v₁) = mex(v₂) = ... = mex(v_N) = 0.

Demonstratie: Daca toate starile v₁, v₂, ..., v_n sunt terminale atunci starea v este pierzatoare si mex(v₁) = mex(v₂) = ... = mex(v_N) = 0, deci teorema este adevarata. Daca starea x contine cel putin un joc cu valoarea Sprague-Grundy nenula se fac mutari in toate aceste jocuri astfel incat sa lase adversarul intr-o stare in care toate jocurile au valoarea SG egala cu 0. Dintr-o astfel de stare, orice mutare ar face adversarul va exista cel putin un joc cu valoarea SG nenula.