2
$\begingroup$

Following is the problem from a finished programming contest.

Two players try to create a number, DesiredTotal, by adding numbers from 1 to N. The first to cross the number is the winner. The number to be added cannot be repeated. For example, if one player used 4 to increase the sum from 20 to 24, the neither player can use 4 again in the game.

Now I understand how the above problem could be solved using dynamic programming by exploring all the possible paths and memoizing the solution, but the game being impartial still qualifies to be a Nim game.

Am I correct that, it is a Nim game? If yes, could somebody help me to reduce into a Nim game?

Below is the source but it requires signing in.

Theory: https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/

Source: https://leetcode.com/contest/leetcode-weekly-contest-10/problems/can-i-win/

$\endgroup$
6
  • $\begingroup$ I'm not sure what you mean by "A nim game." Could you define this class of games? $\endgroup$ Nov 26, 2016 at 11:29
  • $\begingroup$ Here you go: topcoder.com/community/data-science/data-science-tutorials/… $\endgroup$ Nov 26, 2016 at 12:21
  • $\begingroup$ Why the negative vote? It is a finished contest and I am trying to grasp the theory on Nim games by practising some questions? $\endgroup$ Nov 27, 2016 at 9:56
  • $\begingroup$ Your example is not formulated very well. It seems that once 4 is used, neither player can use it again. $\endgroup$ Nov 28, 2016 at 22:15
  • $\begingroup$ Sources which aren't accessible aren't useful. $\endgroup$ Nov 28, 2016 at 22:15

1 Answer 1

2
$\begingroup$

Your game is an impartial game, and so it is covered by the Sprague–Grundy theorem, which say that it is equivalent to a "nimber". Note that the state of the game consists of the current value of the sum as well as the current set of allowed addends. You can compute the Grundy function, which gives the equivalence to Nim, using dynamic programming.

$\endgroup$
2
  • $\begingroup$ Thanks, I guess so. I will think more along the lines you mentioned. If not able to reduce, I will ping back. Grundy number is the unique number to denote the state of the game. So do I have to find the function to map state(sum,set) to a grundy number? English is not my mother tongue, so I apologize if I miss the clarity. $\endgroup$ Nov 29, 2016 at 4:54
  • $\begingroup$ @MangatRaiModi The Grundy function gives the mapping to Nim. $\endgroup$ Nov 29, 2016 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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