Skip to main content
OlympiadHQ

Browse · MathNet

Print

Austrian Mathematical Olympiad

Austria counting and probability

Problem

Mr. Precise wants to take his tea cup out of the microwave precisely at the front. The microwave of Mr. Precise is not precisely cooperative. More precisely, the two of them play the following game: Let be a positive integer. The rotating plate of the microwave takes seconds for a full turn. Each time the microwave is turned on, the plate is turned clockwise or counterclockwise for an integer number of seconds such that the tea cup can end up in possible positions. One of these positions is marked ,,front“. At the start of the game, the microwave rotates the tea cup in one of these positions. Afterwards, for each move, Mr. Precise enters the integer number of seconds and the microwave decides whether to turn clockwise or counterclockwise. For which can Mr. Precise ensure that after a finite number of moves, he can take out the tea cup of the microwave precisely from the front position? (Birgit Vera Schmidt)
Solution
Answer. Mr. Precise can ensure his victory when is a power of 2.

We label the positions consecutively , , ..., where is the front position. If is a power of , say , Mr. Precise can simply always put in the current position as number of seconds. If the microwave turns the plate backwards, the tea cup will end up front immediately. Otherwise, the number of the position will be doubled and reduced modulo at each turn and therefore be divisible by after at most turns. This means that the tea cup ends up front.

Now, let , where is an odd number. We will show that the microwave can always choose a number not divisible by . This is clearly true for the first position, for example by choosing the position . After that, the tea cup is in a certain position not divisible by and Mr. Precise puts in seconds. If both and were divisible by , this would also be true for the sum, so that . Since is odd, this implies which is wrong.
Final answer
Exactly when the number of positions is a power of two

Techniques

Games / greedy algorithmsInvariants / monovariantsModular ArithmeticDivisibility / Factorization