Skip to main content
OlympiadHQ

Browse · MathNet

Print

Austrian Mathematical Olympiad

Austria counting and probability

Problem

On a table, we have ten thousand matches, two of which are inside a bowl.

Anna and Bernd play the following game: They alternate taking turns and Anna begins. A turn consists of counting the matches in the bowl, choosing a proper divisor of this number and adding matches to the bowl. The game ends when more than 2024 matches are in the bowl. The person who played the last turn wins. Prove that Anna can win independently of how Bernd plays.
Solution
Anna's strategy consists of always adding a single match to the bowl while there are less than 1350 matches inside. With this strategy, she will always change an even number of matches to an odd number of matches, so that Bernd is forced to choose an odd divisor and give her an even number of matches again. Bernd will have at most 1350 matches and can add at most a third, since there is no larger odd proper divisor. Since , he cannot reach more than 2024 matches in this phase of the game. Therefore, there will come a turn where Anna starts with an even number of at least 1350 matches. She can add half of them and obtains at least matches and has won.

Techniques

Games / greedy algorithmsInvariants / monovariants