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.

  • $\begingroup$ Can you remind us what the rules of "Div" are? $\endgroup$ – Mike Earnest Apr 22 '18 at 22:59
  • $\begingroup$ @MikeEarnest You write down the divisors of $n$ and each player has the chance to at least take one divisor from $N$ and if there are divisors of that divisor of $N$ you can take those from the pile. $\endgroup$ – jeff c Apr 22 '18 at 23:06
  • $\begingroup$ for ex. $Div(6)$ the divisors are $1,2,3$. you don't include $6$. So if player one takes $3$, then $1$ goes too because its a divisort of $3$. $\endgroup$ – jeff c Apr 22 '18 at 23:08

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.

  • $\begingroup$ "Div" is also known as Schuh's game, it's related to Chomp, and since $30$ is squarefree, this is a special case of David Gale's "subset take-away" game, which is discussed at MO and MSE $\endgroup$ – Mark S. Sep 15 '18 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.