Number Game

can anybody make me understand this problem??There is no explanation given in the editorial??
And how to approach these kind of Problems??

Question-link text

Game theory Q can be sometimes tricky to solve, but this one is simple. There is a pattern which you need to get hold of to solve the Q. The winner depends solely on N if both players play optimally. Finding answer for small cases and extending it to larger cases is the key for solving this problem

Compute answers manually till N=9. Can you see a pattern?

Click to view
  1. A
  2. B
  3. B
  4. B
  5. A
  6. B
  7. B
  8. B
  9. A
  10. B
  11. B
  12. B

The pattern is clearly ABBB, ABBB . Whenever (n-1)%4=0, alice wins. Why are we able to extend our observation to larger cases??? Think, or see hint below :stuck_out_tongue:

Click to view

Lets take example of N=5 and 8. First of all, we must be clear that Bob loses on N=5 for all possible moves. Also, Bob loses at N=5 because he has to first make a turn here.

Now see N=8. If he takes out 3 from it, we will be back to case of N=5, BUT ALICE HAS TO MAKE A MOVE NOW.
And like Bob, she will lose for all possible moves.

If, after making a move, Bob can come to any tile where he’d have lost on playing first (for all possible moves), he will win (because then instead of him, alice will play first for that N and she will lose for all possible moves. This observation is sufficient to extend our observation of smaller cases to larger ones.

These problems are direct application of grundy numbers. Such problems are similar to Game of Nim. Just google grundy numbers or Game of Nim.

To solve such problems, find the grundy number. If grundy numbers is zero, then the person who moves first will always lose. If it is non-zero then the person who moves first will always win. The trick is in the approach in finding the grundy number with the given constraints.

NOTE: In such problems, never approach in finding a pattern. It will just consume your time in a competition, and certainly, you will end up in a wrong pattern or miss edge case. Just find the grundy number and check if it is zero or not.

you are awesome!!!so is the explanation

1 Like