Maths Olympiad Prep

Track / Stage 5 / 315 of 400 #915 of 1964

Problem 915

AIME late
Number theory Difficulty 5.8 Find the answer

Let mm and nn be relatively prime positive integers. The numbers mn\frac{m}{n} and nm\frac{n}{m} are written on a blackboard. At any point, Evan may pick two of the numbers xx and yy written on the board and write either their arithmetic mean 12(x+y)\frac{1}{2}(x+y) or their harmonic mean 2xyx+y\frac{2 x y}{x+y}. For which (m,n)(m, n) can Evan write 1 on the board in finitely many steps?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

We claim this is possible if and only m+nm+n is a power of 2 . Let q=m/nq=m / n, so the numbers on the board are qq and 1/q1 / q.
Impossibility. The main idea is the following.
Claim - Suppose pp is an odd prime. Then if the initial numbers on the board are 1(modp)-1(\bmod p), then all numbers on the board are 1(modp)-1(\bmod p).

Proof. Let ab1(modp)a \equiv b \equiv-1(\bmod p). Note that 2≢0(modp)2 \not \equiv 0(\bmod p) and a+b2≢0(modp)a+b \equiv-2 \not \equiv 0(\bmod p). Thus a+b2\frac{a+b}{2} and 2aba+b\frac{2 a b}{a+b} both make sense modulo pp and are equal to 1(modp)-1(\bmod p).
Thus if there exists any odd prime divisor pp of m+nm+n (implying pmnp \nmid m n ), then
q1q1(modp). q \equiv \frac{1}{q} \equiv-1 \quad(\bmod p) .
and hence all numbers will be 1(modp)-1(\bmod p) forever. This implies that it's impossible to write 1 , whenever m+nm+n is divisible by some odd prime.
₪ Construction. Conversely, suppose m+nm+n is a power of 2 . We will actually construct 1 without even using the harmonic mean.

Note that
nm+nq+mm+n1q=1 \frac{n}{m+n} \cdot q+\frac{m}{m+n} \cdot \frac{1}{q}=1
and obviously by taking appropriate midpoints (in a binary fashion) we can achieve this using arithmetic mean alone.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.