# Nim-Like Game: Subtracting powers of 2 from 1000. [duplicate]

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_zornSep 13 '18 at 4:41

• 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! – Mike Earnest Sep 12 '18 at 19:25
• 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. – Ross Millikan Sep 12 '18 at 19:47