Consider the following game: a pile of n stones is placed in front of two players. The players
take turns removing 1, 2 or 3 stones from the pile. The player who removes the last stone
loses the game. Prove that if n gives a remainder of 1 when divided by 4 then the second
player has a winning strategy, i.e. can always win the game no matter how the first player
plays. Also prove that in all other cases the first player has a winning strategy.
December 14th 2009, 06:23 PM
If n leaves a remainder of 1 divided by 4:
then if the first player pick k stones, the second player can 4-k to make the number of rest stone always leaves a remainder of 1 divided by 4. the second player always win the game.
In other case,
if n leaves a remainder of r (r=2,or 3) divided by 4:
the first player pick r-1 stones at the first step. and then If the second pick i stones, he will pick 4-i stone to make the number of rest stones always leaves a remainder of 1. the first player win the game!
if n leaves a remainder of 0 divided by 4, then the first player will pick 3 stones, after that he adopt the similar strategy mentioned above, he always win the game!