Baltic Way 1990 · Problem 17
Combinatorics
In two piles there are 72 and 30 sweets respectively. Two students take, one after another, some sweets from one of the piles. Each time the number of sweets taken from a pile must be an integer multiple of the number of sweets in the other pile. Is it the beginner of the game or his adversary who can always assure taking the last sweet from one of the piles?
When you’re ready
Review material becomes available with the next Daily.
Review
Topics
Games and strategies · Algorithms and processes
Solutions
Solution
Solution:
Note that one of the players must have a winning strategy. Assume that it is the player making the second move who has it. Then his strategy will assure taking the last sweet also in the case when the beginner takes sweets as his first move. But now, if the beginner takes sweets then the second player has no choice but to take another sweets from the same pile, and hence the beginner can use the same strategy to assure taking the last sweet himself. This contradiction shows that it must be the beginner who has the winning strategy.