Let and be relatively prime positive integers. The numbers and are written on a blackboard. At any point, Evan may pick two of the numbers and written on the board and write either their arithmetic mean or their harmonic mean . For which can Evan write 1 on the board in finitely many steps?
Problem 915
Official solution
We claim this is possible if and only is a power of 2 . Let , so the numbers on the board are and .
Impossibility. The main idea is the following.
Claim - Suppose is an odd prime. Then if the initial numbers on the board are , then all numbers on the board are .
Proof. Let . Note that and . Thus and both make sense modulo and are equal to .
Thus if there exists any odd prime divisor of (implying ), then
and hence all numbers will be forever. This implies that it's impossible to write 1 , whenever is divisible by some odd prime.
₪ Construction. Conversely, suppose is a power of 2 . We will actually construct 1 without even using the harmonic mean.
Note that
and obviously by taking appropriate midpoints (in a binary fashion) we can achieve this using arithmetic mean alone.