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$
  • $\begingroup$ I'm not sure what you mean by "A nim game." Could you define this class of games? $\endgroup$ – David Richerby Nov 26 '16 at 11:29
  • $\begingroup$ Here you go: topcoder.com/community/data-science/data-science-tutorials/… $\endgroup$ – Mangat Rai Modi Nov 26 '16 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$ – Mangat Rai Modi Nov 27 '16 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$ – Yuval Filmus Nov 28 '16 at 22:15
  • $\begingroup$ Sources which aren't accessible aren't useful. $\endgroup$ – Yuval Filmus Nov 28 '16 at 22:15
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$
  • $\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$ – Mangat Rai Modi Nov 29 '16 at 4:54
  • $\begingroup$ @MangatRaiModi The Grundy function gives the mapping to Nim. $\endgroup$ – Yuval Filmus Nov 29 '16 at 5:28

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.