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. Proposed by Yannick Yao
Problem
Source: 2019 USAMO Problem 5, 2019 USAJMO Problem 6
Tags: number theory, relatively prime, USA(J)MO, USAMO, USAJMO, Hi
19.04.2019 01:59
I claim the answer is all \(m+n=2^k\) for some \(k\in \mathbb N\). First, we prove that it works, letting \(m+n=2^k\). Then, we can take the following weighted arithmetic mean \[\dfrac{1}{2^k}\left( m\left(\frac{n}{m}\right)+n\left(\frac{m}{n}\right)\right).\] Now, assume an odd prime \(p\mid m+n\). We now prove the following, noting that \(p\nmid 1+1\) (thus, proving the lemma solves the problem). Lemma. if \(\tfrac{a}{b}\) and \(\tfrac{c}{d}\) are fully simplified fractions such that \(p\mid a+b\) and \(p\mid c+d\), then \(p\) also divides the sum of the numerator and denominator of the arithmetic and harmonic means. Proof. Compute each mean to get that they can be written as \(\frac{ad+bc}{2bd}, \frac{2ac}{ad+bc}\) respectively. Now, let \(g=\gcd(2bd, ad+bc), h=\gcd(2ac, ad+bc)\). Note that \(p\nmid gh\), because \(p\nmid abcd\). Thus, it suffices to show that \(p\mid ad+bc+2bd\) and \(p\mid ad+bc+2ac\), but this is equivalent to \(p\mid (a+b)d+(c+d)b\) and \(p\mid (a+b)c+(c+d)a\), which finishes.
19.04.2019 01:59
Angery. Spent more than three hours and got nowhere
19.04.2019 02:00
hwl0304 wrote: I claim the answer is all \(m+n=2^k\) for some \(k\in \mathbb N\). First, we prove that it works, letting \(m+n=2^k\). Then, we can take the following weighted arithmetic mean \[\dfrac{1}{2^k}\left( m\left(\frac{n}{m}\right)+n\left(\frac{m}{n}\right)\right).\] Now, assume an odd prime \(p\mid m+n\). We now prove the following, noting that \(p\nmid 1+1\) (thus, proving the lemma solves the problem). Lemma. if \(\tfrac{a}{b}\) and \(\tfrac{c}{d}\) are fully simplified fractions such that \(p\mid a+b\) and \(p\mid c+d\), then \(p\) also divides the sum of the numerator and denominator of the arithmetic and harmonic means. Proof. Compute each mean to get that they can be written as \(\frac{ad+bc}{2bd}, \frac{2ac}{ad+bc}\) respectively. Now, let \(g=\gcd(2bd, ad+bc), h=\gcd(2ac, ad+bc)\). Note that \(p\nmid gh\), because \(p\nmid abcd\). Thus, it suffices to show that \(p\mid ad+bc+2bd\) and \(p\mid ad+bc+2ac\), but this is equivalent to \(p\mid (a+b)d+(c+d)b\) and \(p\mid (a+b)c+(c+d)a\), which finishes. Ayy cool, I did that same thing
19.04.2019 02:01
I said let m+n be c×2^k where c is the largest odd factor then all numbers Evan writes are -1 mod c so c is 1. Then I showed the construction.
19.04.2019 02:02
How much partial would I get for stating that I solved the problem for arithmetic means only or harmonic means only, and that $m+n=2^t$? I also made a few other remarks such as $t$ writable implies $\tfrac1t$ writable.
19.04.2019 02:03
Note that the harmonic condition is essentially useless....
19.04.2019 02:04
Nice problem, but pretty easy for JMO6 and USAMO5. The answer is all $(m, n)$ summing to a power of two. To see that this works, say $m+n = 2^s$ and note that \[1 = \frac{m}{2^s} \cdot \frac{n}{m} + \frac{n}{2^s} \cdot \frac{m}{n}\]and we can get any dyadic average by using the arithmetic mean only. Now suppose that $m+n$ is not a power of two, so there exists an odd prime $p \mid m+n$. Then $\tfrac{m}{n} \equiv \tfrac{n}{m} \equiv -1 \pmod{p}$ and so every written number is congruent to $-1$ modulo $p$. But $1 \not\equiv -1 \pmod{p}$, the end.
19.04.2019 02:06
The answer is $m,n$ odd with $m+n$ a power of $2$. These work because you can take rational weightings of $x$ and $y$ with denominators that are powers of $2$ (by using ``binary search'' with the arithmetic mean), so $\frac{n}{m+n}\cdot\frac{m}{n}+\frac{m}{m+n}\cdot\frac{n}{m}=1$ can be written on the board. Now assume $m+n$ is not a power of $2$, then there is an odd prime $p$ dividing $m+n$. Claim: If $p\nmid a,b,c,d$ but $p\mid a+b,c+d$ then $p\nmid (ad+bc),(2bd),(2ac)$ but $p\mid (ad+bc+2bd),(2ac+ad+bc)$. Proof: Routine modular arithmetic. $\square$ But this means that if we operate on $\frac{a}{b}$ and $\frac{c}{d}$ to get $\frac{r}{s}=\frac{ad+bc}{2bd}$ or $\frac{2ac}{ad+bc}$, then if $p$ divides $a+b$ and $c+d$ then $p$ divides $r+s$, where all of these fractions are in simplest form. But to get $1$, we need $p\mid2$, contradiction.
19.04.2019 02:23
Fun fact: this didn't end up in my solution, but I believe I proved that the set of fractions you can create doesn't change if your operations are arithmetic mean and reciprocal rather than AM and HM.
19.04.2019 02:25
yeah i showed what @above got but i got wrong solution set how many points will I get for this?
19.04.2019 02:26
mfang92 wrote: yeah i showed what @above got but i got wrong solution set how many points will I get for this? perhaps 2 points
19.04.2019 02:27
mfang92 wrote: yeah i showed what @above got but i got wrong solution set how many points will I get for this? My understanding is that partial points are primarily based on overlap with the correct solution. As I haven't yet seen a solution that uses this fact to substantially simplify the problem, I'd guess that this gets 0-1.
19.04.2019 02:36
Sorry I am stupid. Who is Evan?
19.04.2019 02:39
franzliszt wrote: Sorry I am stupid. Who is Evan? The person in the flavortext. Also v_Enhance who writes problems for the USA(J)MO, but I'm sure that's a coincidence. @2below tf? i got scammed
19.04.2019 02:41
TheUltimate123 wrote: franzliszt wrote: Sorry I am stupid. Who is Evan? The person in the flavortext. Also v_Enhance who writes problems for the USA(J)MO, but I'm sure that's a coincidence. I'm pretty sure he wrote this problem... Than it won't be a coincidence. Edit: lol Evan didn't write this
19.04.2019 02:43
MathGeek2018 wrote: I'm pretty sure he wrote this problem... Not mine. I appreciated the cameo appearance though.
19.04.2019 03:17
Did anyone else have a solution along these lines? 1. Using only AM and reciprocals (thus needing two elements to sum to 2) 2. Writing everything as $\frac{a}{2^b}+\frac{2^c}{d}$ 3. Finding that $\left(\frac{a}{2^b}+\frac{2^c}{d}\right)+\left(\frac{a'}{2^{b'}}+\frac{2^{c'}}{d'}\right) = 2$ for $d$, $d'$ odd and positive leads to $d=d'$, which then leads to a contradiction (quite a few steps in here) 4. If two terms add up to 2, their denominators must be powers of 2. 5. Conclude that if $\frac{a}{2^b}$ is one of these terms, then $\frac{a}{2^b}=\lambda \frac{m}{n}+(1-\lambda)\frac{n}{m}$ for some rational $0\le\lambda\le 1$ and the denominator of $\lambda$ being a power of 2. 6. Then there exists some rational $x$ with $0\le x\le 1$ and the denominator of $x$ a power of 2 with $1=x\frac{m}{n}+(1-x)\frac{n}{m}$ which then implies that $m+n$ is a power of 2. If you didn't do anything similar to this, this likely doesn't make any sense, so please ignore. Also, I glossed over the proof to 5 since I was running out of time.
19.04.2019 03:19
How do you know you can write everything as $\frac{a}{2^b}+\frac{2^c}{d}$
19.04.2019 03:21
If I forgot to say m,n odd, will I get a point off?
24.11.2021 18:10
We claim the answer is $\boxed{m+n=2^s\forall s\in\mathbb{N}}$. We will first show that this works. Take the following weighted arithmetic mean $\frac{m}{2^s}\cdot\frac{n}{m}+\frac{n}{2^s}\cdot\frac{m}{n}=1$. Now we will show that nothing else works. Suppose that an odd prime $p$ divides $m+n$. Then $\frac{m}{n}\equiv\frac{n}{m}\equiv-1\pmod p$. We can see that both the arithmetic mean and harmonic mean will be $-1\pmod p$, which means we can never write $1$.
25.11.2021 00:23
Claim: The answer is $\boxed{m+n=2^x, x \in \mathbb{N}}$. Proof: A construction for $m+n=2^x$ is $$\frac{m}{2^x}\cdot\frac{n}{m}+\frac{n}{2^x}\cdot\frac{m}{n}=1.$$Suppose $m+n$ is not a power of $2,$ then there must exists an odd prime $p$ such that $$p \mid m+n \implies m+n \equiv 0\pmod{p} \implies \frac{m}{n} \equiv \frac{n}{m} \equiv -1 \pmod{p},$$because $m$ and $n$ are relatively prime. But $1 \not\equiv -1 \pmod{p}.$ Hence, we are done. $\blacksquare$
13.03.2022 07:19
Fun question. It is easy to show that any odd divisor of $m+n$ will divide the sum of the numerator and denominator of all generated numbers, but at the very end to generate 1, you would need $\frac{a-b}{a}, \frac{a+b}{a}$ but $\gcd(2a-b, 2a+b) \mid 4$ so $m+n$ has no odd divisors, and the construction is trivial.
30.03.2022 18:30
Suppose $m+n$ is not a power of $2$. Note that $m+n>1$. Then let $p\mid m+n$ for an odd prime $p$, we have: $$m+n\equiv0\pmod p\Rightarrow\frac mn\equiv\frac nm\equiv-1\pmod p.$$Also, if $\frac ab\equiv\frac cd\equiv-1\pmod p$ then: $$\frac{\frac ab+\frac cd}2\equiv\frac{2\cdot\frac ab\cdot\frac cd}{\frac ab+\frac cd}\equiv-1\pmod p,$$so by induction, all numbers that are written on the board are $-1\pmod p$. But then $1$ cannot be ever written on the board. Now we show that if $m+n=2^k$ for some $k\in\mathbb N$, Evan can write $1$ under this process. Notice that we can get weighted arithmetic means of elements written on the board with denominator $2^k$ from normal arithmetic means, and so Evan eventually may write: $$\frac{n\cdot\frac mn+m\cdot\frac nm}{2^k}=1.$$
12.10.2022 09:40
Let $m+n=k$ for integer $k$. Choose any prime number $p$ such that $p|k$. Then we have $$ m \equiv -n \mod p \Rightarrow \frac{m}{n} \equiv \frac{n}{m} \equiv -1 \mod p$$Observe that For any $a,b,c,d$ such that $\frac{a}{b} \equiv \frac{c}{d} \equiv -1 \mod p$, we have: \begin{align*} &\frac{\frac{a}{b}+\frac{c}{d}}{2} \equiv \frac{-2}{2} \equiv -1 \mod p \\ & \frac{2 \frac{a}{b} \cdot \frac{c}{d}}{ \frac{a}{b}+ \frac{c}{d}} \equiv \frac{2}{-2} \equiv -1 \mod p \end{align*}Which means that any numbers in blackboard are equivalent to $-1$ mod $p$, since we want $1$ on the blackboard, which is equivalent to $1$ mod $p$, we have contradiction except for $p=2$ since $ 1 \equiv -1 \mod 2$. The only thing we left is showing that $m+n=2^x$ works, which is possible by weighted arithmetic mean since $$\frac{n(\frac{m}{n})+(2^k-n)\frac{n}{m}}{2^k}=1$$
04.01.2023 07:30
The great part about DCY-process is that most of the problems are pretty popular and I can post all of them without looking like a weirdo (slovenia kazakhstan tournament of towns moment) The answer is $\boxed{\text{all relatively prime }(m, n)\text{ with }m+n = 2^k}$ for some positive integer $k$. The key claim is the following: Claim: All fractions $\frac{p}{2^q}\cdot\frac mn + \frac{2^p-p}{2^q}\cdot\frac nm$ for positive integers $0 < p < 2^q$ are achievable by Evan. Proof: We induct. The base case $k = 1$ is trivial. Assume $k = j$ works. Let $0 < a_1$, $a_2 < 2^j$. Then $1 < a_1 + a_2 < 2^{j+1}-1$ are possible by arithmetic mean, and $1$ and $2^{j+1}-1$ are possible by arithmetic meaning $\frac{1}{2^j}\cdot\frac mn + \frac{2^j-1}{2^j}\cdot \frac nm$ with $\frac nm$ and $\frac{2^j-1}{2^j}\cdot\frac mn + \frac{1}{2^j}\cdot \frac nm$ with $\frac mn$, respectively, which completes the induction. Obviously taking $q = k$ and $p = n$ proves that the answer works. Now FTSOC assume some pair $(m, n)$ not of the above form works. Then some odd prime $p$ divides $m+n$. Notice that the numerators of $\frac mn + 1 = \frac{m+n}{n}$ and $\frac nm + 1 = \frac{m+n}{m}$ are divisible by $p$, and the denominators are not. Also notice that the arithmetic and harmonic mean preserve this property (not shown here). Therefore, since $(m, n)$ work, the final fraction must "cancel out" the $p$ in the numerator, which is clearly impossible, done.
09.01.2023 04:53
wow nice We claim that the answer is when $m+n$ is a power of 2. If it is, then WLOG $m<n$ since $m=n$ is trivial. Then, the ratio the gap between $m/n$ and 1 and the gap between 1 and $n/m$ is $n:m$, and therefore, if $m+n$ is a power of 2, then 1 is a weighted mean of the two original numbers where the weights have denominators that are powers of 2, so we an just use an arithmetic mean move repeatedly to reach it. Otherwise, $m+n$ is divisible by some odd prime $p$. Note that due to relatively prime, neither $m$ nor $n$ are divisible by $p$. Claim: If $a,b,c,d$ are such that $a+b$ and $c+d$ are multiples of $p$ but none of $a,b,c,d$ themselves are multiples of $p$, then the sum of the numerators and denominators of both the harmonic mean and arithmetic mean of $a/b$ and $c/d$ are divisible by $p$. The aritmetic mean is $$\frac{ad+bc}{2bd}.$$Note that $a\equiv -b\pmod p$ and $c\equiv -d\pmod p$. Therefore, $$ad+bc+2bd\equiv -ac-ac+2ac\equiv 0\pmod p.$$Additionally, there will be no adverse cancellation since $2bd$ is not a multiple of $p$. The harnomic mean is $$\frac{2ac}{ad+bc},$$and again we hvae $$2ac+ad+bc\equiv 2ac-ac-ac\equiv 0\pmod p,$$and there will also be no adverse cancellation. Also, note that $2ac$ and $2bd$ are both not divisible by $p$, so the new fraction will still have niether the top or bottom divisible by $p$ but the sum divisible by $p$. Therefore, if $m+n$ is not a power of 2, then all numbers that we create will have numerator and denominator sum to a multiple of $p$ but neither of them are actually multiples of $p$, so we cannot reach 1
12.01.2023 15:58
I see nobody posted this construction yet. I hope it is correct. I will prove that any pair of odd numbers $(m,n)$ with $m+n=2^k$ for some $k$ works. $\textbf{Necessity}$ Claim: After only using the arithmetic mean, every new number written on the board can be written as \[2^k\left(u\cdot \frac{m}{n}+v\cdot\frac{n}{m}\right)\]where $u,v$ are positive integers with $u+v=2^k$. Proof: Induction on the number of already written numbers on the board. However, the equation \[2^k\left(u\cdot \frac{m}{n}+(2^k-u)\cdot\frac{n}{m}\right)=1\]has the solution \[u=\frac{2^km}{m+n}\]and since $gcd(m,n)=1$, we must have $m+n\mid 2^k\Rightarrow m+n=2^{\alpha}$. $\textbf{Sufficiency}$ Suppose $m+n=2^k$ and both are odd. We would like to have $u=n$. For this consider the binary representation of $n$ \[n=1+2^{\alpha_1}+2^{\alpha_2}+\ldots +2^{\alpha_i}\]Now, when Evan will want to add $2+\alpha_j$'th number on the board, he will write the arithmetic mean between $\frac{m}{n}$ and the last already written number. This will happen for every $1\le j\le i$. For the other positions he will write the arithmetic mean between $\frac{n}{m}$ and the last already written number. In the end we will have \[u=1+2^{\alpha_1}+2^{\alpha_2}+\ldots +2^{\alpha_i}=n\]so we are done.
09.09.2023 04:01
Note that $m+n=2^k$ always works due to fractions $\frac{i}{2^j}\frac mn + \frac{2^i-i}{2^j}\frac nm$ being achievable by suitable applications of arithmetic mean; taking i=n, j=m finishes. On the other hand, note that $\frac{ad+bc}{2bd},\frac{2ac}{ad+bc}$ (AM and HM) are s.t. the sum of numerator and denominator of either of those are divisible by an odd prime p when p|a+b,c+d, with a,b,c,d not divisible by p; this means that if the numerator eventually equals denominator, both numerator and denominator must be divisible by that odd prime p, but this is a contradiction since 2ac and 2bd are not divisible by p by assumption (and that now, ad+bc,2bd,2ac,ad+bc are all not divisible by p, meaning we reduce into a'/b',c'/d' with the same properties). We conclude.
13.11.2023 00:57
If $n+m$ is a power of $2$, then $\frac{n\cdot\frac mn+m\cdot\frac nm}{n+m}=1$ so it is possible to write $1$ as a combination of arithmetic means. Otherwise, there exists an odd $p\mid n+m$. Then, each of the numbers are $-1$ mod $p$ and every operation writes down a number that is $-1$ mod $p$. Therefore, since $1\not\equiv-1\pmod p$, it is impossible to write down $1$. Therefore, Evan can write $1$ if and only if $m+n$ is a power of $2$.
18.11.2023 21:18
Claim: Let $r \in [0, 1]$ be a dyadic rational. Then the number $rx+(1-r)y$ can be formed, if $(x, y)$ is the pair of numbers on the board at some point. Proof. Let $x$ correspond to the point $(1, 0)$ and $y$ to the point $(0, 1)$. Utilizing the arithmetic mean, we can take the midpoints of subsegments until we reach the point $(r, 1-r)$ by looking at the binary expansion of $r$, as desired. I contend that all pairs $(m, n)$ with $m+n=2^k$ for some positive integer $k$ work. Call such pairs good. For good pairs $(m, n)$, we use the construction \[r \cdot \frac{m}{n}+(1-r) \cdot \frac{n}{m}, \]where $r=\tfrac{n}{m+n}$. Clearly the above expression is $1$, so all good pairs work. Now we show that any pair that is not good -- a bad pair -- does not work. Let $(m, n)$ be a bad pair. Suppose that $p$ is an odd prime with $p \mid m+n$, and note that neither $m$ nor $n$ are divisible by $p$, or else both are and that contradicts the relatively prime condition. Working over $\bmod{\ p}$, \[ \frac{m}{n} \equiv \frac{n}{m} \equiv -1 \pmod{p}. \]Since the arithmetic and harmonic means are preserved $\bmod{\ p}$, and the arithmetic and harmonic means of $(-1, -1)$ is always $-1$, the number $1$ is never written on the board, as desired.
21.07.2024 07:11
25.08.2024 20:14
We claim that $m+n$ has to be a power of $2.$ Note that if not, then $\frac{m}{n} \equiv -1 \pmod p$ for some odd prime $p.$ Then all writable terms also have to be $-1 \pmod p.$ Now we show that it is possible. Note that we can simply just weigh the average in binary because $m+n$ is a power of $2.$ Therefore we're done$.\blacksquare$
17.12.2024 03:35
Freest JMO #6 EVER (compare to 2018 JMO/6 )Honestly its super clean tho The answer is all $(m,n)$ with $m+n$ a power of $2.$ The first step is necessity. Claim:If $p \mid m+n,$ then all the fractions written on the board have the sum of their numerator and denominator a multiple of $p.$ We will show this by strong induction. The base case, $k=2,$ is by assumption. For the inductive step, let the two fractions that we apply the operation to next be $\frac{a}{b},$ and $\frac{c}{d}.$ Then, the sum of the numerator and denominator will be $\frac{ad+bc+2bd}{\gcd(ad+bc, 2bd)}.$ Notice that the numerator of this is a multiple of $p,$ while the denominator is not, thus proving the claim. So, we have shown necessity, and thus we are done.