The numbers 1, . . . , 1000 are written on the board. Two players take
turns erasing a number; a number x may be erased if x = 1, or x − 1 has
been erased, or x is even and x/
2
has been erased. The player to erase
1000 wins.
Which player has a winning strategy?
The first player wins if the number of numbers removed is odd once 1000 has been removed. I think that regardless of what number is removed the opponent can always choose to remove some number other than 500 or 999 until only these numbers and 1000 remains, and therefore the first player wins. This is because whichever number the opponent chooses to remove no numbers are eliminated from consideration, since each player will keep trying to avoid removing 500 or 999 until they and 1000 only remain and the opponent can pick a number 1 greater than the number they choose to erase. Assuming optimal play each player will avoid their loss as long as possible so in all 999 numbers will be removed at the end of the game, since either 500 or 999 may not be removed.
Is my approach correct?
Best Answer
No :
$501$ cannot be removed before $500$
so there is a losing position when faced with $500,501,999,1000$ remaining