There are two piles of candy. One pile contains 20 pieces, and the other 21. Two players take turns eating all the candy in one pile and separating the remaining candy into two (not necessarily equal) piles. (A pile may have 0 candies in it.) The player who cannot eat a candy on his/her turn loses. Which player, if either, can guarantee victory in this game?
I am extremely confused on approaching this problem, particularly on where to start. Can someone please explain a strategy in approaching problems of this type?
First try to tackle similar, but simpler, games.
For example: let's say we have one pile (A) of two candies, and one pile (B) of one candy. Then we can work out the possibilities:
If player I eats pile A, then they don't have any options in how to split the remaining candies (well, candy :P); on turn 2, there will be 2 piles, one with 1 candy and one with 0 candies. Player II will then eat the only nonempty pile, and player I will lose.
If player II eats pile B, then they have two possible ways to rearrange the remaining candies: as 1 + 1 or 2 + 0. In the latter case, player II eats the nonempty pile, and player I loses. In the former case, whichever pile II eats, the result will be one pile with one candy; player I then eats that candy, and wins.
So we conclude:
(Note that this does not mean that player I always wins! It's possible for player I to play badly. It just means that as long as player I is clever enough, they can't lose.)
Now, look at some other examples - like 2 + 2, or 1 + 3, etc. - and see if you can come up with a general rule. Once you have an idea for what that rule should be, you'll have to prove it somehow; but the first step is coming up with the right idea.