I am practising some olympiad problems. Not getting how to solve type of problems where we have a game and we need to answer who will win. Here is one such problem:
Amy and Bob play the game. At the beginning, Amy writes down a positive integer on the board. Then the players take moves in turn, Bob moves first. On any move of his, Bob replaces the number $n$ on the blackboard with a number of the form $n-a^2$, where a is a positive integer. On any move of hers, Amy replaces the number $n$ on the blackboard with a number of the form $n^k$, where $k$ is a positive integer. Bob wins if the number on the board becomes zero. Can Amy prevent Bob’s win?
I don't have any idea how I can proceed to solve this. Can anyone please explain the general strategy to solve this type of problems taking this as an example?
I think the point of questions like this is that there is not a general strategy - rather they challenge you to think about what you know and how to employ that information.
That said, what you are looking for here is some kind of pattern which will form the basis of a proof. Where I would begin is thinking "which are the positions which Bob wins/Amy loses quickly" so here is a way of beginning - you want to identify numbers which are safe for Amy. I've left some details
Obviously if Amy leaves a square Bob wins. If Bob leaves a square, then Amy's next move must leave a square, and Bob wins.
So if Amy leaves a sum of two squares, Bob can leave a square and win. I wonder how far you can go in that direction.
You should know that any positive integer can be expressed as the sum of at most four squares. Reasoning along the lines above, can Amy guarantee to stay on safe numbers, or can Bob always force her off?