\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{IMO 2023/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 129}
\maketitle

\section*{Problem}
Let $x_1$, $x_2$, \dots, $x_{2023}$ be pairwise different positive real numbers such that
\[ a_n = \sqrt{(x_1+x_2+\dots+x_n)
  \left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_n}\right)} \]
is an integer for every $n=1,2,\dots,2023$. Prove that $a_{2023} \geq 3034$.

\section*{Video}
\href{https://www.youtube.com/watch?v=vDG6i7LmiFU&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/vDG6i7LmiFU}}

\section*{External Link}
\url{https://aops.com/community/p28104298}

\newpage

\section*{Solution}
Note that $a_{n+1} > \sqrt{\sum_1^n x_i \sum_1^n \frac{1}{x_i}} = a_n$ for all $n$,
so that $a_{n+1} \geq a_n + 1$.
Observe $a_1 = 1$.
We are going to prove that \[ a_{2m+1} \geq 3m+1 \qquad \text{for all } m \geq 0 \]
by induction on $m$, with the base case being clear.

We now present two variations of the induction.
The first shorter solution compares $a_{n+2}$ directly to $a_n$,
showing it increases by at least $3$.
Then we give a longer approach that compares $a_{n+1}$ to $a_n$,
and shows it cannot increase by $1$ twice in a row.

\paragraph{Induct-by-two solution.}
Let $u = \sqrt{\frac{x_{n+1}}{x_{n+2}}} \neq 1$.
Note that by using Cauchy-Schwarz with three terms:
\begin{align*}
  a_{n+2}^2 &= \Bigg[ (x_1+\dots+x_n)+x_{n+1}+x_{n+2} \Bigg]
    \Bigg[ \left(\frac{1}{x_1}+\dots+\frac{1}{x_n}\right)
    +\frac{1}{x_{n+2}} + \frac{1}{x_{n+1}} \Bigg] \\
  &\geq \left( \sqrt{ (x_1+\dots+x_n)\left(\frac{1}{x_1}+\dots+\frac{1}{x_n}\right)}
    + \sqrt{\frac{x_{n+1}}{x_{n+2}}} + \sqrt{\frac{x_{n+2}}{x_{n+1}}} \right)^2 \\
  &= \left( a_n + u + \frac 1u \right)^2. \\
  \implies a_{n+2} &\ge a_n + u + \frac 1u > a_n + 2
\end{align*}
where the last equality $u + \frac 1u > 2$ is by AM-GM, strict as $u \neq 1$.
It follows that $a_{n+2} \geq a_n + 3$, completing the proof.

\paragraph{Induct-by-one solution.}
The main claim is:
\begin{claim*}
  It's impossible to have
  $a_n = c$, $a_{n+1} = c+1$, $a_{n+2} = c+2$ for any $c$ and $n$.
\end{claim*}
\begin{proof}
  Let $p = x_{n+1}$ and $q = x_{n+2}$ for brevity.
  Let $s = \sum_1^n x_i$ and $t = \sum_1^n \frac{1}{x_n}$, so $c^2 = a_n^2 = st$.

  From $a_n = c$ and $a_{n+1} = c$ we have
  \begin{align*}
    (c+1)^2 &= a_{n+1}^2 = (p+s)\left( \frac 1p+t \right) \\
    &= st + pt + \frac1ps + 1 = c^2 + pt + \frac1ps + 1 \\
    &\overset{\text{AM-GM}}{\geq} c^2 + 2\sqrt{st} + 1 = c^2 + 2\sqrt{c^2} + 1 = (c+1)^2.
  \end{align*}
  Hence, equality must hold in the AM-GM we must have exactly
  \[ p t = \frac 1p s = c. \]
  If we repeat the argument again on $a_{n+1}=c+1$ and $a_{n+2}=c_{n+2}$, then
  \[ q \left( \frac 1p + t \right) = \frac 1q \left( p + s \right) = c + 1. \]
  However this forces $\frac pq = \frac qp = 1$ which is impossible.
\end{proof}

\end{document}
