Maths Olympiad Prep

Library / /93 of 115

Number theory Difficulty 7.6 National olympiad, round 2 Find the answer

Two rational numbers mn\frac{m}{n} and nm\frac{n}{m} are written on a blackboard, where mm and nn are relatively prime positive integers. At any point, Evan may pick two of the numbers xx and yy written on the board and write either their arithmetic mean x+y2\frac{x+y}{2} or their harmonic mean 2xyx+y\frac{2xy}{x+y} on the board as well. Find all pairs (m,n)(m,n) such that Evan can write 11 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.

Solution

We claim that all odd m,nm, n work if m+nm+n is a positive power of 2.
Proof:
We first prove that m+n=2km+n=2^k works. By weighted averages we have that n(mn)+(2kn)nm2k=m+n2k=1\frac{n(\frac{m}{n})+(2^k-n)\frac{n}{m}}{2^k}=\frac{m+n}{2^k}=1 can be written, so the solution set does indeed work. We will now prove these are the only solutions.
Assume that m+n2km+n\ne 2^k , so then m+n0(modp)m+n\equiv 0\pmod{p} for some odd prime pp . Then mn(modp)m\equiv -n\pmod{p} , so mnnm1(modp)\frac{m}{n}\equiv \frac{n}{m}\equiv -1\pmod{p} . We see that the arithmetic mean is 1+(1)21(modp)\frac{-1+(-1)}{2}\equiv -1\pmod{p} and the harmonic mean is 2(1)(1)1+(1)1(modp)\frac{2(-1)(-1)}{-1+(-1)}\equiv -1\pmod{p} , so if 1 can be written then 11(modp)1\equiv -1\pmod{p} and 20(modp)2\equiv 0\pmod{p} which is obviously impossible, and we are done.
-Stormersyle
The problems on this page are copyrighted by the Mathematical Association of America 's American Mathematics Competitions .

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.