A problem from the Leningrad Mathematical Olympiad: A and B take turns removing matches from a pile. The pile starts with 500 matches, A goes first, and the player who takes the last match wins. The catch is that the quantity that each player withdraws on a given turn must be a power of 2. Does either player have a winning strategy?
|
SelectClick for Answer |
If there were only 3 matches in the original pile, A would lose — he could withdraw 1 or 2 matches, but then B could immediately withdraw the remainder and win the game. If there were 4 or 5 matches in the original pile then A could saddle B with a losing 3-match pile, but if there were 6 in the original pile, then by the same principle B could saddle A with the 3-match pile.
The winning strategy, then, is always to leave your opponent a quantity that’s a multiple of 3. A can accomplish this on his first turn by taking 2 matches from the pile of 500, leaving 498 = 3 × 166 matches for B, who cannot now escape his fate.
|
