Alice and Bob are playing a game. There are 'n' discs. Alice starts the game. The players play alternatively thereafter. In each turn, the players have to choose a number which is a power of 4, say 'd' and subtract it from 'n'. So 'n' will be 'n-d' now. A player who cannot choose a power of 4 to deduct in his turn will lose the game.
Example: if n = 4, then Alice will choose 4 and end the game for Bob. As he will be left with 0 in his turn and he cannot choose a power of 4.
What will be the optimal strategy for the players in this case? And in general how to find the optimal strategy for players? What are the rules of thumb?
First, if n is not a multiple of 4, map it to the greatest but smaller than it multiple of 4. Now, player 1 will lose iff
or 
.
If n = 5, the mapped number will be 4, so 'n' is now 4. and n % 20 => 4 So player 1 should win. But here there are only two choices:
So anyways here player two will win.? Am I missing something?
And how did you arrive at this solution?
I forgot the players can use the number 1. With that, you don't need to round n down and the answer should be: player 1 will lose iff
or 
.
I just wrote a dp solution and found the pattern by watching the outputs for some inputs.
I got it now. Thanks!
This question is live in one of the hiring challenge on HackerEarth