Let $a_0, b_0, c_0$ be complex numbers, and define \begin{align*}a_{n+1} &= a_n^2 + 2b_nc_n \\ b_{n+1} &= b_n^2 + 2c_na_n \\ c_{n+1} &= c_n^2 + 2a_nb_n\end{align*}for all nonnegative integers $n.$ Suppose that $\max{\{|a_n|, |b_n|, |c_n|\}} \leq 2022$ for all $n.$ Prove that $$|a_0|^2 + |b_0|^2 + |c_0|^2 \leq 1.$$
Problem
Source: 2022 USAJMO Problem 6
Tags: AMC, USA(J)MO, USAJMO
24.03.2022 21:40
24.03.2022 21:42
this was a joke problem 6, what happened to maa this year.
24.03.2022 21:43
ok dotted got the same thing as me thankfully no fakesolve
24.03.2022 23:51
get?
25.03.2022 01:08
Let $\omega\in\{1,e^{\frac{2\pi i}{3}}, e^{\frac{4\pi i}{3}}\}$. Let $z_n=a_n+\omega b_n+\omega^2 c_n$ for $n$ even and $z_n=a_n+\omega^2b_n+\omega c_n$ for $n$ odd. Then the problem gives $z_{n+1}=z_n^2$. If $|z_0|>1$ then $|z_n|\to\infty$ as $n\to\infty$, contradicting $\max\{|a_n|,|b_n|,|c_n|\}\le 2022$. Thus $|z_0|\le 1$ for each choice of $\omega$. Denoting $\zeta=e^{\frac{2\pi i}{3}}$ we have \[ |a_0+b_0+c_0|^2\le 1, |a_0+b_0\zeta+c_0\zeta^2|^2\le 1, |a_0+b_0\zeta^2+c_0\zeta|^2\le 1. \]Expanding, we have \begin{align*} |a_0|^2+|b_0|^2+|c_0|^2+(a_0\overline{b_0}\zeta^0+a_0\overline{c_0}\zeta^0+b_0\overline{a_0}\zeta^0+b_0\overline{c_0}\zeta^0+c_0\overline{a_0}\zeta^0+c_0\overline{b_0}\zeta^0)&\le 1\\ |a_0|^2+|b_0|^2+|c_0|^2+(a_0\overline{b_0}\zeta^2+a_0\overline{c_0}\zeta^1+b_0\overline{a_0}\zeta^1+b_0\overline{c_0}\zeta^2+c_0\overline{a_0}\zeta^2+c_0\overline{b_0}\zeta^1)&\le 1\\ |a_0|^2+|b_0|^2+|c_0|^2+(a_0\overline{b_0}\zeta^1+a_0\overline{c_0}\zeta^2+b_0\overline{a_0}\zeta^2+b_0\overline{c_0}\zeta^1+c_0\overline{a_0}\zeta^1+c_0\overline{b_0}\zeta^2)&\le 1 \end{align*}Averaging these yields the desired result.
25.03.2022 02:20
... Let $S_n = |a_n|^2+|b_n|^2+|c_n|^2$. I claim that if $S_0>1$, then $S_n$ grows arbitrarily large as $n \to \infty$. In particular, there will exist $n$ with $$|a_n|^2+|b_n|^2+|c_n|^2 > 3 \cdot 2022^2,$$which contradicts $\text{max}(|a_n|, |b_n|, |c_n|) \leq 2022$. Notice that \begin{align*} S_{n+1} &= |a_{n+1}|^2+|b_{n+1}|^2+|c_{n+1}|^2 \\ &= \sum_{\mathrm{cyc}} (a_n^2 + 2b_nc_n)(\overline{a_n}^2+2\overline{b_nc_n}) \\ &= |a_n|^4+|b_n|^4+|c_n|^4 + 4(|b_nc_n|^2+|c_na_n|^2+|a_nb_n|^2) + 2(\overline{a_n}^2b_nc_n+\overline{b_n}^2c_na_n+\overline{c_n}^2a_nb_n+b_nc_n\overline{a_n}^2+c_na_n\overline{b_n}^2+a_nb_n\overline{c_n}^2) \\ &= (|a_n|^2+|b_n|^2+|c_n|^2)^2 + 2|\overline{a_n}c_n+\overline{b_n}a_n+\overline{c_n}b_n|^2 \\ &\geq S_n^2. \end{align*}Thus $S_n \geq S_0^{2^n}$. It is clear that if $S_0 > 1$ and $n \to \infty$, $S_n \to \infty$ as well. Thus, we must have $S_0 \leq 1$, as desired.
25.03.2022 03:38
CircleInvert wrote:
get? I'm SO MAD i got exactly that and then had tunnel vision for 2 hours while i was desperately trying to deal with the Re
25.03.2022 04:01
how many points for saying that $|a_{n+1}|^2+|b_{n+1}|^2+|c_{n+1}|^2\geq(|a_n|^2+|b_n|^2+|c_n|^2)^2$ proves the problem?
25.03.2022 04:05
asdf334 wrote: how many points for saying that $|a_{n+1}|^2+|b_{n+1}|^2+|c_{n+1}|^2\geq(|a_n|^2+|b_n|^2+|c_n|^2)^2$ proves the problem? 1 at most because you need to prove it But if you proved this and this is your final line, 7.
25.03.2022 04:33
DottedCaculator wrote:
are you having a brain die nvm i see it now
25.03.2022 04:33
i did the a_i,b_i,c_i real case first so i found that the remaining term was square, then extended to complex
25.03.2022 04:37
DottedCaculator wrote:
Wait Hold on This is part of the random crap that I wrote down to try and get a point or two Gaming??
25.03.2022 05:29
Here's a low IQ and horrible solution. Let $a_n = x_{n,1} + iy_{n,1}, b_n = x_{n,2} + iy_{n,2}, c_n = x_{n,3} + iy_{n,3}$. We have $S_{n+1} = |a_{n+1}^2| + |b_{n+1}^2| + |c_{n+1}^2| = \sum x_{i,{n+1}}^2 + \sum y_{i,n+1}^2$. Note that $x_{n+1, 1} = x_{n,1}^2 - y_{n,1}^2 + 2x_{n,2}x_{n,3} + 2y_{n,2}y_{n,3}$ and $y_{n+1,1}^2 = 2(x_{n,1}y_{n,1} + x_{n,2}y_{n,3} + x_{n,3}y_{n,2})$, from now on, assume $x_i = x_{n,i}$ for sanity sake. $\sum x_{n+1,1}^2 = \sum x_i^4 + \sum y_i^4 + 4 (x_1x_2 + x_1x_3 + y_1y_3)^2 + 4 (y_1y_2 + y_2y_3 + y_1y_3)^2 + 4 \sum x_i^2y_{i+1}y_{i+2} - 4 \sum y_i^2x_{i+1}x_{i+2} - 4x_1x_2x_3(x_1 + x_2 + x_3) - 4y_1y_2y_3(y_1 + y_2 + y_3) - 2 \sum x_i^2y_i^2$ and $\sum y_{n+1, 1}^2 = 4(\sum x_i^2y_j^2 + 2(x_1x_2 + x_2x_3 + x_1x_3)(y_1y_2 + y_1y_3 + y_2y_3))$ So adding them, $S_{n+1} - S_{n}^2 = 2(x_1x_2 + x_1x_3 + x_2x_3 + y_1y_2 + y_2y_3 + y_1y_3)^2 + 2 \sum_{i \neq j} x_i^2x_j^2 + \text{horrible stuff}$ (i am too braindead currently, i'll edit in the "stuff" later) which factorizes as $$S_{n+1} - S_n^2 = 2(\sum_{i \neq j} x_ix_j + \sum_{i \neq j}y_iy_j)^2 + 2(x_1y_2 + x_2y_3 + x_3y_1 - x_2y_1 - x_3y_2 - x_1y^3)^2$$which is nonnegative and hence $S_{n+1} \ge S_n^2$ so if $S_0 > 1$, then $S_n$ gets arbitrarily large, so we are done. $\blacksquare$
25.03.2022 05:41
math31415926535 wrote: this was a joke problem 6, what happened to maa this year. The backstory seems to be that #6 was originally intended to be the canonical solution, which does make this problem much neater, cuter and difficult [in particular, it exemplifies the individual recurrences themselves much better]. It seems that unfortunately, most competitors found Dotted's/my/M4L's solution to be much more intuitive (which I agree it is, but much less satisfying as well).
25.03.2022 05:42
HamstPan38825 wrote: math31415926535 wrote: this was a joke problem 6, what happened to maa this year. The backstory seems to be that #6 was originally intended to be the canonical solution, which does make this problem much neater, cuter and difficult [in particular, it exemplifies the individual recurrences themselves much better]. It seems that unfortunately, most competitors found Dotted's/my/M4L's solution to be much more intuitive (which I agree it is, but much less satisfying as well). yeah our solution is MUCH faster I thought that I had fakesolved when I got it, it was that easy
25.03.2022 11:36
Let $S_n=|a_n|+|b_n|+|c_n|$ for all $n$ Key claim: $S_{n+1} \geq S_n^2$ for all $n$. Proof: Equivalently, we want to prove (let $a_n=x$, $b_n=y$ and $c_n=z$) that $$|x^2+2yz|^2+|y^2+2zx|^2+|z^2+2xy|^2 \geq (|x|^2+|y|^2+|z|^2)$$ However, $|x^2+2yz|^2+|y^2+2zx|^2+|z^2+2xy|^2-(|x|^2+|y|^2+|z|^2)^2=(x^2+2yz)\overline{x^2+2yz}+(y^2+2zx)\overline{y^2+2zx}+(z^2+2xy)\overline{z^2+2xy}=$ $=(x^2+2yz)(\overline{x}^2+2\overline{y}\overline{z})+(y^2+2zx)(\overline{y}^2+2\overline{z}\overline{x})+(z^2+2xy)(\overline{z}^2+2\overline{x}\overline{y})-(|x|^2+|y|^2+|z|)^2=\ldots=2|\overline{x}y+\overline{y}z+\overline{z}x|^2 \geq 0,$ as desired $\blacksquare$ To the problem, suppose that $S_0>1$. An easy induction shows that $S_n \geq S_0^{2^n}$ for all $n$, and since $\lim_{n \rightarrow +\infty} S_0^{2^n}=+\infty$, we may pick $n$ such that $S_0^{2^n} > 3 \cdot 2022$. In this case, however, $3 \cdot 2022 \geq 3 \max \{|a_n|,|b_n|,|c_n| \} \geq S_n \geq S_0^{2^n}> 3\cdot 2022,$ a contradiction. Hence we must have $S_0 \leq 1$, as desired.
27.03.2022 20:33
With a suitable choice of $f_k$, the problem is equivalent to the following (where $*$ represents convolution): Restated problem wrote: Let $\{f_k\}$ be a bounded sequence of functions $\mathbb{Z}/n\mathbb{Z}\to\mathbb{C}$ such that $f_{k+1}=f_k*f_k$. Prove that $\lVert f_k\rVert\leq1$. Solving this problem becomes an application of Fourier tricks, each of which corresponds to a part of the solution in post 6.
30.03.2022 18:43
Let $x_n=|a_n|^2+|b_n|^2+|c_n|^2$, and suppose FTSOC that $x_0>1$. By the given recurrences we have: \begin{align*} x_{n+1}&=|a_{n+1}|^2+|b_{n+1}|^2+|c_{n+1}|^2\\ &=|a_n^2+2b_nc_n|^2+|b_n^2+2c_na_n|^2+|c_n^2+2a_nb_n|^2\\ &=(a_n^2+2b_nc_n)(\overline{a_n}^2+2\overline{b_n}\overline{c_n})+(\overline{b_n}^2+2\overline{c_n}\overline{a_n})(\overline{b_n}^2+2\overline{c_n}\overline{a_n})+(\overline{c_n}^2+2\overline{a_n}\overline{b_n})(\overline{c_n}^2+2\overline{a_n}\overline{b_n})\\ &=x_n^2+2|a_n\overline{b_n}+b_n\overline{c_n}+c_n\overline{a_n}|^2\\ &\ge x_n^2. \end{align*}by induction, $x_n\ge x_0^{2^n}$, so taking $n>\log_2\left(\frac{\ln2022}{\ln x_0}\right)+1000$, we have $x_n>2022$, a contradiction.
07.07.2022 21:18
This problem is tricky because you need to believe that $|a_{n+1}|^2+|b_{n+1}|^2+|c_{n+1}|^2$ can be related to $|a_n|^2+|b_n|^2+|c_n|^2$, be very familiar with complex number manipulations, be able to spot complex number factorizations (which I’ve never practiced before). I try to present the solution as naturally as possible. Some of the identities used in this problems are $|z|^2=z\overline{z}$, $\overline{w+z}=\overline{w}+\overline{z}$, $\overline{wz}=\overline{w}\cdot\overline{z}$, and $(\overline{z})^k = \overline{z^k}$. Let $x_n = |a_n|^2+|b_n|^2+|c_n|^2$. We claim that if $x_0>1$, then as $n\to\infty$, $x_n\to\infty$. This would contradict $\max{\{|a_n|, |b_n|, |c_n|\}} \leq 2022$. \begin{align*} x_{n+1} &= \sum_{\text{cyc}} |a_{n+1}|^2 \\ &= \sum_{\text{cyc}} a_{n+1}\overline{a_{n+1}} \\ &= \sum_{\text{cyc}} (a_n^2 + 2b_nc_n)\overline{a_n^2 + 2b_nc_n} \\ &= \sum_{\text{cyc}} \left[ |a_n^2|^2 + 4|b_nc_n|^2 + a_n^2(\overline{2b_nc_n}) + \overline{a_n^2} (2b_nc_n)\right] \\ &= (|a_n|^2+|b_n|^2+|c_n|^2)^2 + \sum_{\text{cyc}} \left[ 2|b_nc_n|^2 + 2a_n^2\overline{b_nc_n} + 2\overline{a_n^2}b_nc_n \right] \\ &= (|a_n|^2+|b_n|^2+|c_n|^2)^2 + 2\sum_{\text{cyc}} \left[b_nc_n\overline{b_nc_n} + a_n^2\overline{b_nc_n} + \overline{a_n^2}b_nc_n \right] \end{align*}Now we need to deal with the sum. Since the $x_i$ are real numbers, we suspect that the sum can be expressed in terms of absolute value. There are also $9=3^2$ terms, so the sum could be factored as $(k_1+k_2+k_3)(k_4+k_5+k_6)$. Each term has 2 regular parts and 2 conjugate parts, so we could have all $k_i$ be equal to $w_i\overline{z_i}$, or the first half be $w_iz_i$ and the second half be $\overline{w_iz_i}$. With all three observations, we are motivated to consider when $k_4=\overline{k_1}$, $k_5=\overline{k_2}$, $k_6=\overline{k_3}$. After some experimentation, we realize that the sum is equivalent to $|a_n\overline{b_n}+b_n\overline{c_n}+c_n\overline{a_n}|^2$. Thus, \[ x_{n+1} = x_n^2 + 2|a_n\overline{b_n}+b_n\overline{c_n}+c_n\overline{a_n}|^2 \ge x_n^2, \]So $x_n \ge x_0^{2^n}$. Therefore, if $x_0>1$, then as $n\to\infty$, $x_n\to\infty$, contradiction, so $x_0\le1$.
09.01.2023 09:52
math31415926535 wrote: this was a joke problem 6, what happened to maa this year. With five correct solutions out of 278 students, I think it is fine...
20.08.2023 03:30
Proof that $(|a_n|+|b_n|+|c_n|)^2 \le |a_{n-1}|+|b_{n-1}|+|c_{n-1}|.$ Let $a_n=x, b_n=y, c_n=z$, I did this because I don't want a latex headache. We need to prove that $|x^2+2yz|^2+|y^2+2zx|^2+|z^2+2xy|^2 \geq |x|^2+|y|^2+|z|^2$, so $|x^2+2yz|^2+|y^2+2zx|^2+|z^2+2xy|^2 - (|x|^2+|y|^2+|z|^2) \ge 0.$ Since $z\overline{z}=|z|^2$, we have, $|x^2+2yz|^2+|y^2+2zx|^2+|z^2+2xy|^2=(x^2+2yz)\overline{x^2+2yz}+(y^2+2zx)\overline{y^2+2zx}+(z^2+2xy)\overline{z^2+2xy}.$ Now, $|x^2+2yz|^2+|y^2+2zx|^2+|z^2+2xy|^2 - (|x|^2+|y|^2+|z|^2)=x^2+2yz)\overline{x^2+2yz}+(y^2+2zx)\overline{y^2+2zx}=2|\overline{x}y+\overline{y}z+\overline{z}x|^2 \geq 0.$ Hence, proved. $\blacksquare$
03.12.2023 05:40
I feel like this was the easiest problem of the test lol Edit: oops my sol was wrong (see post below)
03.12.2023 06:09
Mr.Sharkman wrote: $a_{0}^{2}+b_{0}^{2}+c_{0}^{2} \le |a_{0}+b_{0}+c_{0}|^{2} \le 1,$ and hence we are done. wrong
26.01.2024 06:16
Joke confirmed. At most a 9 minute solve. Assume for contradiction that $|a_0|^2 + |b_0|^2 + |c_0|^2>1$. Realize that \[ |a_{n+1}|^2+|b_{n+1}|^2+|c_{n+1}|^2 = \sum_{\text{cyc}} (|a_n|^4+4|b_n|^2|c_n|^2) + 2 \sum_{\text{cyc}} b_nc_n\overline{a_n^2} + 2 \sum_{\text{cyc}} \overline{b_nc_n} a_n^2. \]The crux is that we can factor the conjugate terms and obtain \[ |a_{n+1}|^2+|b_{n+1}|^2+|c_{n+1}|^2 = (|a_n|^2+|b_n|^2+|c_n|^2)^2+2|\overline{a_n}b_n+\overline{b_n}c_n+\overline{c_n}a_n|^2 \ge (|a_n|^2+|b_n|^2+|c_n|^2)^2. \]Since $|a_0|^2 + |b_0|^2 + |c_0|^2>1$, the sequence $s_n := |a_n|^2 + |b_n|^2 + |c_n|^2>1$ is unbounded above, a contradiction. Thus $|a_0|^2 + |b_0|^2 + |c_0|^2 \le 1$, and we are done.
05.03.2024 23:00
Multiplying the first equation by its conjugate gives \[|a_{n+1}|^2=(a_n^2+2b_nc_n)(\overline{a_n^2}+2\overline{b_nc_n})=|a_n|^4+2|b_n|^2|c_n|^2+2|b_nc_n|^2+2a_n^2\overline{b_nc_n}+2\overline{a_n^2}b_nc_n.\]Summing cyclically, we have \[\sum|a_{n+1}|^2=\left(\sum|a_n|^2\right)^2+2\left|\sum a_n\overline{b_n}\right|^2\ge\left(\sum|a_n|^2\right)^2.\]Then $\textstyle\sum|a_0|^2>1$ would imply $\lim_{n\rightarrow\infty}\sum|a_n|^2\rightarrow\infty$, contradiction. $\square$
06.03.2024 01:36
redacted