This question already has an answer here:

A professor of one of my courses introduced us to a game to play during down-time, we start with 1000, then we take turns subtracting the powers of 2 (1 to 512), from 1000, we can use the same power of 2 multiple times, but you cannot end up with a negative difference, or a difference of zero. That is, the winner reaches a difference of 1, from which the next player has no moves (cannot subtract 1 from 1 to leave a difference of zero).

He asked us if we could have any strategies and if it matters what player goes first. Now, I have simulated many games and come to conclusion that it might not matter who goes first, but any strategy I seem to come up with seems flawed.

Has anyone else heard of this game? Is there a winning strategy, and does it matter who goes first or not? Furthermore, is there any generalized version of this game, say maybe with powers of n, or starting with an integer total m?


marked as duplicate by Jyrki Lahtonen, Ross Millikan, Adrian Keister, Leucippus, max_zorn Sep 13 '18 at 4:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 5
    $\begingroup$ Hint: instead of starting from 1000, solve the game when you start from small numbers $n$. Start with $n=1$ (where you certainly don't want to be the first player), then $n=2$ (where the first player wins by subtracting $1$), then $n=3$ (where the first player wins by subtracting $2$), and so on. Write down all the results in a table. Eventually, you will notice a simple pattern. This suggests a simple rule for determining which player wins as a function of $n$, which leads to a proof and winning strategy. This is a fun problem I which I urge you try to solve on your own! $\endgroup$ – Mike Earnest Sep 12 '18 at 19:25
  • $\begingroup$ "it might not matter who goes first" it definitely does matter. $\endgroup$ – Arthur Sep 12 '18 at 19:27
  • 1
    $\begingroup$ Are you familiar with the concept of $N$ positions and $P$ positions? You are looking for a rule that separates them. Any deterministic, finite, perfect information, symmetric game is Nim in disguse. You just need to find the mapping between the game positions and Nim heaps. $\endgroup$ – Ross Millikan Sep 12 '18 at 19:47
  • 1
    $\begingroup$ @JyrkiLahtonen: In that question, the player who takes the last marble wins. Here, the player who takes the last marble loses. I think that requires a different analysis? $\endgroup$ – joriki Sep 12 '18 at 20:36
  • $\begingroup$ @joriki: I believe you are right in that the analysis is different, but perhaps the game is just switched? In that, player two has the advantage as the final winning turn is no longer in the hands of the first player? $\endgroup$ – ZeroSum Sep 13 '18 at 1:19