Problem:
Given a pile of 2000 stones, two players take turns in taking stones from the pile. Each player must remove , or stones from the pile at each turn, but may not take the same number as his opponent took on his last move. The player who takes the last stone wins. Does the first or second player have a winning strategy?
Solution:
The first player has a winning strategy. He takes on his first move leaving (). Now we claim that the first player can always leave: (1) , (2) by taking away , (3) by taking away , or (4) , and that the second player can never leave .
Let us look at each of these in turn. If the first player leaves , then the second player can take and leave . In that case the first player takes (a type (3) move). If the second player takes or , leaving or , then the first player takes (respectively) and leaves (a type (4) move).
If the first player leaves by taking away , then the second player cannot leave , because he cannot take stones. If he takes leaving respectively, then the first player takes leaving (a type (1) move). If the second player takes leaving , then the first player takes leaving (a type (4) move).
If the first player leaves by taking , then the second player cannot leave , because he cannot take stones. If he takes stones, leaving , then the first player takes stones leaving (a type (1) move).
Finally, if the first player leaves , and the second player takes stone, then the first player takes stones leaving (a type (2) move). If the second player takes , or stones leaving , then the first player takes stones leaving (a type (1) move).
So the second player can never leave and hence, in particular, can never take the last stone. But we have shown that the first player can always make a move of one of the four types, so can always move and hence must win (since after less than moves there will be no stones left).