Two players write alternatively some integers on the blackboard. The rules are the following : - The first player write $1$. - At each of the other turns, the player has to write $a+1$ or $2a$ where $a$ is any number already wrote in the blackboard and $2a \leq 1000.$ - One cannot write a number which has already been written, and no number is erased. - The player who writes $1000$ is the winner. Determine which player has a winning strategy. Pierre.
Problem
Source: Me
Tags:
zscool
26.12.2004 07:19
bumping this up haven't had too much time to think about it, but at first thought, it seems like the first player can always write an odd integer on the board.
pbornsztein
26.12.2004 12:51
And? Pierre.
_tequilla
06.01.2005 19:11
First player wins if you write 1000,998,996,....,502 or 250, 248,246,....,126 or 62,60,58......,32 or 15,13,11,....,1 then you can wins
Myth
06.01.2005 19:22
backtracking
Renshaw
07.01.2005 23:11
@tequila: I think you are incorrectly assuming that the $a$ must be the previous number written on the board. If $a$ can indeed be any number already written, then the first player loses. To lose, one must be forced to write either 500 or 999. No one is going to have to do that until all the numbers 1-499 are written, because $a+1$ is always an option. Since 502 is also an option as soon as 251 is written, 502-998 must also be written. Thus, after all integers from 1 to 998, excluding 500 and 501, are written on the board, the person whose turn it is loses. 996 integers => even => first player's turn.
pbornsztein
07.01.2005 23:59
That's it Renshaw. But, for Tequila, I have made the same mistake as you did at first attempt. Some contestants have made it too and, unfortunately for them, they did not correct their answer (but I did ). Pierre.