iamrk's blog

Help: Optimal Strategy Problem
By iamrk, history, 6 years ago, In English

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?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:

    1. player 1 can take out 4 and then player two will take out 1 so player two will win.
    2. player 1 can take out 1 and then player two will take out 4 so player two will win.

    So anyways here player two will win.? Am I missing something?

    And how did you arrive at this solution?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This question is live in one of the hiring challenge on HackerEarth

→ Reply