How to find the What is the sprague-grundy value of $Div$ games.

Question

I'm doing this work for a game theory class. We learned how to find the What is the sprague-grundy value with $Nim$ and $Take-away$ games, but not $Div$ games. Can someone explain how to find the sprague-grundy of $Div(30)$? Thank you.

Answer 1

The only way to find the Sprague-Grundy value for Div$(30)$ is brute force. Namely, draw out the entire game tree, and starting from the bottom up, compute the Grundy number of each sub-position. This sounds hard, but the game tree is not that huge, and you should be able to use the symmetries of the problem to save some work. Divide the states in your tree into levels based on how many numbers are left; at the top, the initial state has $7$ divisors, and when the game is over, there are $0$ left.

It helps to realize that the divisors of $30=2\times3\times 5$, and each of these prime factors behaves exactly alike. For example, once you have found the Grundy value of the position obtained by removing $2$, then $3\cdot 5$, this gives you the values for removing $3$ then $2\cdot 5$ and $5$ then $2\cdot 3$ for free.