|Home||Archive||About||Math Hour||Math Hour Olympiad|
Problem. Amy and Brandon play a game with a stack of 30 coins. They take turns removing either 1 or 2 coins at a time. The person that takes the last coin wins. Amy figures out a trick: as long as Brandon goes first, she can win. What's her trick?
Who wins if the stack starts with 1 coin? What about 2 coins? 3 coins?
If it's your turn, then a 3 coin stack is a losing position, and 1 coin stack or 2 coin stack is a winning position. If there are 4 coins, can you force your opponent into a losing position, thereby winning? How about 5 coins? 6 coins?
Solution: Amy removes coins to keep the stack a multiple of 3. She can always do this because if Brandon takes 1 coins, she'll take 2, and if Brandon takes 2 coins, she'll take 1. Because 0 is a multiple of 3, Amy will be the one to take the last coin.
In general, Amy can do this whenever the starting stack is a multiple of 3. Whenever the starting stack is not a multiple of 3, the first player, in this case Brandon, has a winning strategy. (What is it?)