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"

(Created page with "Two rational numbers \(\tfrac{m}{n}\) and \(\tfrac{n}{m}\) are written on a blackboard, where \(m\) and \(n\) are relatively prime positive integers. At any point, Evan may pi...")
 
m
 
(9 intermediate revisions by 5 users not shown)
Line 1: Line 1:
−
Two rational numbers \(\tfrac{m}{n}\) and \(\tfrac{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 \(\tfrac{x+y}{2}\) or their harmonic mean \(\tfrac{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.
+
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"