Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 USAJMO Problems/Problem 6"
m
 
(8 intermediate revisions by 5 users not shown)
Line 1: Line 1:
−
Two rational numbers <math>\(\tfrac{m}{n}\)</math> and <math>\(\tfrac{n}{m}\) </math> are written on a blackboard, where <math>\(m\)</math> and <math>\(n\)</math> are relatively prime positive integers. At any point, Evan may pick two of the numbers <math>\(x\)</math> and <math>\(y\)</math> written on the board and write either their arithmetic mean <math>\(\tfrac{x+y}{2}\)</math> or their harmonic mean <math>\(\tfrac{2xy}{x+y}\)</math> on the board as well. Find all pairs <math>\((m,n)\)</math> such that Evan can write <math>1</math> on the board in finitely many steps.
+
Two rational numbers <math>\frac{m}{n}</math> and <math>\frac{n}{m} </math> are written on a blackboard, where <math>m</math> and <math>n</math> are relatively prime positive integers. At any point, Evan may pick two of the numbers <math>x</math> and <math>y</math> written on the board and write either their arithmetic mean <math>\frac{x+y}{2}</math> or their harmonic mean <math>\frac{2xy}{x+y}</math> on the board as well. Find all pairs <math>(m,n)</math> such that Evan can write <math>1</math> on the board in finitely many steps.
  
 
Proposed by Yannick Yao
 
Proposed by Yannick Yao
 +
 +
==Solution==
 +
We claim that all odd <math>m, n</math> work if <math>m+n</math> is a positive power of 2.
 +
 +
Proof:
 +
We first prove that <math>m+n=2^k</math> works. By weighted averages we have that <math>\frac{n(\frac{m}{n})+(2^k-n)\frac{n}{m}}{2^k}=\frac{m+n}{2^k}=1</math> can be written, so the solution set does indeed work. We will now prove these are the only solutions.
 +
 +
Assume that <math>m+n\ne 2^k</math>, so then <math>m+n\equiv 0\pmod{p}</math> for some odd prime <math>p</math>. Then <math>m\equiv -n\pmod{p}</math>, so <math>\frac{m}{n}\equiv \frac{n}{m}\equiv -1\pmod{p}</math>. We see that the arithmetic mean is <math>\frac{-1+(-1)}{2}\equiv -1\pmod{p}</math> and the harmonic mean is <math>\frac{2(-1)(-1)}{-1+(-1)}\equiv -1\pmod{p}</math>, so if 1 can be written then <math>1\equiv -1\pmod{p}</math> and <math>2\equiv 0\pmod{p}</math> which is obviously impossible, and we are done.
 +
 +
-Stormersyle
 +
 +
==Video Solution==
 +
https://www.youtube.com/watch?v=hIX89vyuGD8&list=PLa8j0YHOYQQK1xH_fn0WSXR-AW9uWdDEf&index=1&t=1s - AMBRIGGS
 +
 +
==See also==
 +
{{USAJMO newbox|year=2019|num-b=5|aftertext=|after=Last Problem}}
 +
 +
{{MAA Notice}}

Latest revision as of 11:51, 8 November 2022

Two rational numbers $\frac{m}{n}$ and $\frac{n}{m}$ are written on a blackboard, where $m$ and $n$ are relatively prime positive integers. At any point, Evan may pick two of the numbers $x$ and $y$ written on the board and write either their arithmetic mean $\frac{x+y}{2}$ or their harmonic mean $\frac{2xy}{x+y}$ on the board as well. Find all pairs $(m,n)$ such that Evan can write $1$ on the board in finitely many steps.

Proposed by Yannick Yao

Solution

We claim that all odd $m, n$ work if $m+n$ is a positive power of 2.

Proof: We first prove that $m+n=2^k$ works. By weighted averages we have that $\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+n\ne 2^k$, so then $m+n\equiv 0\pmod{p}$ for some odd prime $p$. Then $m\equiv -n\pmod{p}$, so $\frac{m}{n}\equiv \frac{n}{m}\equiv -1\pmod{p}$. We see that the arithmetic mean is $\frac{-1+(-1)}{2}\equiv -1\pmod{p}$ and the harmonic mean is $\frac{2(-1)(-1)}{-1+(-1)}\equiv -1\pmod{p}$, so if 1 can be written then $1\equiv -1\pmod{p}$ and $2\equiv 0\pmod{p}$ which is obviously impossible, and we are done.

-Stormersyle

Video Solution

https://www.youtube.com/watch?v=hIX89vyuGD8&list=PLa8j0YHOYQQK1xH_fn0WSXR-AW9uWdDEf&index=1&t=1s - AMBRIGGS

See also

2019 USAJMO (Problems • Resources)
Preceded by
Problem 5 		Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_USAJMO_Problems/Problem_6&oldid=180435"