h4. _De ce este acest joc echivalent cu jocul NIM?_

Aşa cum la $NIM$ puteam lua oricâte pietre dintr-o grămadă, aici putem muta pionul dintr-un nod cu valoarea $g$ într-un nod astfel încât noua valoare pentru pionul $i$ poate fi orice număr de la $0$ la $g - 1$. Prin urmare, pentru a verifica dacă suntem într-o poziţie de câştig în jocul cu pionii, putem aplica strategia jocului $NIM$ şi obţinem că suntem într-o poziţie de câştig dacă suma $XOR$ a numerelor din nodurile ocupate de cei $n$ pioni este diferită de $0$. Această sumă se numeşte funcţia _Sprague Grundy,_ $SG{(i~1~, …, i~n~)} = gi{~1~} {@^@} gi{~2~} {@^@} gi{~3~} {@^ … ^@} gi{~n~}$.

Aşa cum la $NIM$ puteam lua oricâte pietre dintr-o grămadă, aici putem muta pionul dintr-un nod cu valoarea $g$ într-un nod astfel încât noua valoare pentru pionul $i$ poate fi orice număr de la $0$ la $g - 1$. Prin urmare, pentru a verifica dacă suntem într-o poziţie de câştig în jocul cu pionii, putem aplica strategia jocului $NIM$ şi obţinem că suntem într-o poziţie de câştig dacă suma $XOR$ a numerelor din nodurile ocupate de cei $n$ pioni este diferită de $0$. Această sumă se numeşte funcţia _Sprague Grundy,_ $SG(i~1~, …, i~n~) = gi{~1~} {@^@} gi{~2~} {@^@} gi{~3~} {@^ … ^@} gi{~n~}$.

Problema de la runda 47 ({_Pioni_}) se rezolvă acum uşor efectuând o sortare topologică a nodurilor grafului aciclic şi numerotând nodurile folosind funcţia $mex$.