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,_ %{color:gray}$SG(i{~1~}$, …, $i{~n~}#41; = 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,_ %{color:gray}$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$.