Maths Olympiad Prep

Library / /2 of 2

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Nordic Mathematical Olympiad

Problem:

The number 10200710^{2007} is written on a blackboard. Anne and Berit play a game where the player in turn makes one of two operations:

(i) Replace a number xx on the blackboard by two integer numbers aa and bb greater than 11 such that x=abx = ab;

(ii) Erase one or both of two equal numbers on the blackboard.

The player who is not able to make her turn loses the game. Who has a winning strategy?

Solution

Solution:

We describe a winning strategy for Anne. Her first move is
10200722007,52007 10^{2007} \rightarrow 2^{2007}, 5^{2007}
We want to show that Anne can act in such a way that the numbers on the blackboard after each of her moves are of the form
2α1,,2αk,5α1,,5αk 2^{\alpha_{1}}, \ldots, 2^{\alpha_{k}}, 5^{\alpha_{1}}, \ldots, 5^{\alpha_{k}}
This is the case after Anne's first move. If Berit for example replaces 2αj2^{\alpha_{j}} by 2β12^{\beta_{1}} and 2β22^{\beta_{2}}, then Anne would replace 5αj5^{\alpha_{j}} by 5α15^{\alpha_{1}} and 5α25^{\alpha_{2}}. If Berit for example erases 5αj5^{\alpha_{j}} or two 5αj5^{\alpha_{j}}'s (which means that there is an αi=αj\alpha_{i} = \alpha_{j}), then Anne would erase 2αj2^{\alpha_{j}} or two 2αj2^{\alpha_{j}}'s. Thus for each move Berit makes, Anne can answer with a 'symmetric' move. Since the game is finite, Berit must be the first player failing to make a move. Thus Anne has a winning strategy.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.