IMO 2023 Problem 4
Write
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m50s
Problem
Let $x_1, x_2, \cdots , x_{2023}$ be pairwise different positive real numbers such that $$ a_n = \sqrt{(x_1+x_2+ \text{···} +x_n)(\frac1{x_1} + \frac1{x_2} + \text{···} +\frac1{x_n})} $$ is an integer for every $n = 1,2,\cdots,2023$. Prove that $a_{2023} \ge 3034$.
Exploration
Write
$$S_n=x_1+\cdots+x_n,\qquad T_n=\frac1{x_1}+\cdots+\frac1{x_n}.$$
Then
$$a_n=\sqrt{S_nT_n}.$$
The first step is to understand how $a_n$ changes when $x_n$ is added. Expanding,
$$a_n^2-a_{n-1}^2 =(S_{n-1}+x_n)\left(T_{n-1}+\frac1{x_n}\right)-S_{n-1}T_{n-1}.$$
This simplifies to
$$a_n^2-a_{n-1}^2 =\frac{S_{n-1}}{x_n}+x_nT_{n-1}+1.$$
The expression
$$\frac{S_{n-1}}{x_n}+x_nT_{n-1}$$
has the form $u+\frac{a_{n-1}^2}{u}$. By AM-GM it is at least $2a_{n-1}$, with equality when
$$x_n=\sqrt{\frac{S_{n-1}}{T_{n-1}}} =\frac{S_{n-1}}{a_{n-1}}.$$
Since every $a_n$ is an integer, $a_n^2-a_{n-1}^2$ is an integer. Hence the quantity above is also an integer. If equality in AM-GM does not occur, then that quantity is a strictly larger integer than $2a_{n-1}$, so it is at least $2a_{n-1}+1$. Consequently the square difference is at least $2a_{n-1}+2$, which forces
$$a_n\ge a_{n-1}+2.$$
If equality in AM-GM does occur, then
$$a_n^2-a_{n-1}^2=2a_{n-1}+1=(a_{n-1}+1)^2-a_{n-1}^2,$$
hence
$$a_n=a_{n-1}+1.$$
Thus every step contributes either $+1$ or at least $+2$. The problem becomes combinatorial: how many $+1$ steps can occur?
Suppose the $n$-th step is a $+1$ step. Then
$$x_n=\frac{S_{n-1}}{a_{n-1}}.$$
Computing
$$\frac{S_n}{a_n} =\frac{S_{n-1}+x_n}{a_{n-1}+1} =\frac{S_{n-1}}{a_{n-1}} =x_n.$$
Hence the next $+1$ step would require $x_{n+1}=x_n$, impossible because the $x_i$ are pairwise distinct. Therefore $+1$ steps can never be consecutive.
Among the $2022$ transitions from $a_1$ to $a_{2023}$, at most $1011$ can be $+1$ steps. The minimum total increase is obtained when exactly $1011$ transitions contribute $1$ and the remaining $1011$ contribute $2$. This gives
$$a_{2023}\ge 1+1011+2\cdot1011=3034.$$
The crucial point is proving that two consecutive minimal increments are impossible.
Problem Understanding
This is a Type B problem.
For
$$S_n=x_1+\cdots+x_n,\qquad T_n=\frac1{x_1}+\cdots+\frac1{x_n},$$
the quantity
$$a_n=\sqrt{S_nT_n}$$
is assumed to be an integer for every $n=1,\dots,2023$. The numbers $x_1,\dots,x_{2023}$ are positive and pairwise distinct.
The task is to prove the lower bound
$$a_{2023}\ge 3034.$$
The main difficulty is that the values $x_i$ are arbitrary positive reals, so direct estimates on $S_n$ and $T_n$ are too weak. The integrality of every $a_n$ must be exploited. The key idea is to study the increment from $a_{n-1}$ to $a_n$. Integrality forces each increment to be either exactly $1$ or at least $2$. The pairwise distinctness then shows that increments equal to $1$ cannot occur consecutively. Counting the smallest possible total increase yields the required bound.
Proof Architecture
Lemma 1. For every $n\ge2$,
$$a_n^2-a_{n-1}^2 =\frac{S_{n-1}}{x_n}+x_nT_{n-1}+1.$$
This follows from expanding $(S_{n-1}+x_n)(T_{n-1}+1/x_n)$.
Lemma 2. For every $n\ge2$, either
$$a_n\ge a_{n-1}+2,$$
or
$$a_n=a_{n-1}+1.$$
Moreover,
$$a_n=a_{n-1}+1$$
holds exactly when
$$x_n=\frac{S_{n-1}}{a_{n-1}}.$$
This comes from AM-GM applied to the expression in Lemma 1 and the integrality of the $a_i$.
Lemma 3. If
$$a_n=a_{n-1}+1,$$
then
$$\frac{S_n}{a_n}=x_n.$$
This is obtained by substituting the equality condition from Lemma 2.
Lemma 4. Two consecutive equalities
$$a_n=a_{n-1}+1,\qquad a_{n+1}=a_n+1$$
are impossible.
Using Lemma 3, the second equality would force $x_{n+1}=x_n$, contradicting pairwise distinctness.
The hardest direction is proving that a nonminimal AM-GM value forces an increment of at least $2$, not merely a larger square difference. The integrality of $a_n$ is essential there.
Solution
Let
$$S_n=x_1+\cdots+x_n,\qquad T_n=\frac1{x_1}+\cdots+\frac1{x_n}.$$
Then
$$a_n=\sqrt{S_nT_n}.$$
Since
$$a_1=\sqrt{x_1\cdot \frac1{x_1}}=1,$$
we have $a_1=1$.
Lemma 1
For every $n\ge2$,
$$a_n^2-a_{n-1}^2 =\frac{S_{n-1}}{x_n}+x_nT_{n-1}+1.$$
Proof
Using
$$S_n=S_{n-1}+x_n,\qquad T_n=T_{n-1}+\frac1{x_n},$$
we obtain
$$a_n^2-a_{n-1}^2 =S_nT_n-S_{n-1}T_{n-1}.$$
Expanding,
$$\begin{aligned} a_n^2-a_{n-1}^2 &=(S_{n-1}+x_n)\left(T_{n-1}+\frac1{x_n}\right)-S_{n-1}T_{n-1}\ &=\frac{S_{n-1}}{x_n}+x_nT_{n-1}+1. \end{aligned}$$
This proves the lemma. ∎
This establishes the exact square increment; replacing it by a rough inequality would lose the information needed later.
Lemma 2
For every $n\ge2$, either
$$a_n=a_{n-1}+1,$$
or
$$a_n\ge a_{n-1}+2.$$
Furthermore,
$$a_n=a_{n-1}+1$$
if and only if
$$x_n=\frac{S_{n-1}}{a_{n-1}}.$$
Proof
By Lemma 1,
$$a_n^2-a_{n-1}^2 =\frac{S_{n-1}}{x_n}+x_nT_{n-1}+1.$$
Since
$$S_{n-1}T_{n-1}=a_{n-1}^2,$$
the arithmetic-geometric mean inequality gives
$$\frac{S_{n-1}}{x_n}+x_nT_{n-1} \ge 2\sqrt{S_{n-1}T_{n-1}} = 2a_{n-1}.$$
Equality holds precisely when
$$\frac{S_{n-1}}{x_n}=x_nT_{n-1},$$
which is equivalent to
$$x_n^2=\frac{S_{n-1}}{T_{n-1}}$$
and hence
$$x_n=\sqrt{\frac{S_{n-1}}{T_{n-1}}} =\frac{S_{n-1}}{a_{n-1}},$$
because all quantities are positive.
Assume first that equality holds. Then
$$a_n^2-a_{n-1}^2=2a_{n-1}+1.$$
Hence
$$a_n^2=(a_{n-1}+1)^2.$$
Since $a_n>0$,
$$a_n=a_{n-1}+1.$$
Now assume equality does not hold. Then
$$\frac{S_{n-1}}{x_n}+x_nT_{n-1}>2a_{n-1}.$$
The left-hand side is an integer because
$$\frac{S_{n-1}}{x_n}+x_nT_{n-1} =(a_n^2-a_{n-1}^2)-1,$$
and both $a_n$ and $a_{n-1}$ are integers. Therefore
$$\frac{S_{n-1}}{x_n}+x_nT_{n-1}\ge 2a_{n-1}+1.$$
Consequently
$$a_n^2-a_{n-1}^2\ge 2a_{n-1}+2.$$
If $a_n=a_{n-1}+1$, then
$$a_n^2-a_{n-1}^2=2a_{n-1}+1,$$
contradicting the previous inequality. Thus
$$a_n\ge a_{n-1}+2.$$
The lemma is proved. ∎
This establishes that every transition contributes either exactly $1$ or at least $2$; without using integrality one would obtain only a weaker estimate.
Lemma 3
If
$$a_n=a_{n-1}+1,$$
then
$$\frac{S_n}{a_n}=x_n.$$
Proof
By Lemma 2,
$$x_n=\frac{S_{n-1}}{a_{n-1}}.$$
Using
$$S_n=S_{n-1}+x_n, \qquad a_n=a_{n-1}+1,$$
we compute
$$\frac{S_n}{a_n} = \frac{S_{n-1}+x_n}{a_{n-1}+1} = \frac{S_{n-1}+\frac{S_{n-1}}{a_{n-1}}}{a_{n-1}+1}.$$
Factoring $S_{n-1}$,
$$\frac{S_n}{a_n} = \frac{S_{n-1}\left(1+\frac1{a_{n-1}}\right)}{a_{n-1}+1} = \frac{S_{n-1}}{a_{n-1}} = x_n.$$
This proves the lemma. ∎
This identifies the precise value of $S_n/a_n$ after a minimal increment; omitting the explicit computation would hide the mechanism preventing consecutive minimal increments.
Lemma 4
Two consecutive equalities
$$a_n=a_{n-1}+1$$
and
$$a_{n+1}=a_n+1$$
cannot both hold.
Proof
Assume
$$a_n=a_{n-1}+1.$$
By Lemma 3,
$$\frac{S_n}{a_n}=x_n.$$
If also
$$a_{n+1}=a_n+1,$$
then Lemma 2 gives
$$x_{n+1}=\frac{S_n}{a_n}.$$
Hence
$$x_{n+1}=x_n.$$
This contradicts the assumption that the numbers $x_1,x_2,\dots,x_{2023}$ are pairwise distinct. Therefore two consecutive equalities are impossible. ∎
This shows that minimal increments cannot occur back-to-back; merely knowing that the $x_i$ are distinct is insufficient without identifying the exact equality condition.
We now finish the proof.
There are $2022$ transitions
$$a_1\to a_2,\quad a_2\to a_3,\quad \dots,\quad a_{2022}\to a_{2023}.$$
By Lemma 2, each transition contributes either $1$ or at least $2$. By Lemma 4, transitions contributing $1$ are never consecutive. Among $2022$ positions, at most
$$1011$$
can contribute $1$.
Hence at least
$$2022-1011=1011$$
transitions contribute at least $2$.
Since $a_1=1$,
$$a_{2023} \ge 1+1011\cdot1+1011\cdot2 = 3034.$$
Thus
$$a_{2023}\ge 3034.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the passage from AM-GM to the dichotomy between increments $1$ and at least $2$.
Starting from
$$a_n^2-a_{n-1}^2 =\frac{S_{n-1}}{x_n}+x_nT_{n-1}+1,$$
AM-GM yields
$$\frac{S_{n-1}}{x_n}+x_nT_{n-1}\ge2a_{n-1}.$$
When equality fails, the quantity is strictly larger than $2a_{n-1}$. Because it is an integer, it is at least $2a_{n-1}+1$. This extra integrality step is indispensable. Without it one obtains only
$$a_n^2-a_{n-1}^2>2a_{n-1}+1,$$
which does not immediately force $a_n\ge a_{n-1}+2$.
The second delicate step is proving that a minimal increment determines $x_n$ uniquely.
Equality in AM-GM requires
$$\frac{S_{n-1}}{x_n}=x_nT_{n-1}.$$
Multiplying by $x_n$ gives
$$S_{n-1}=x_n^2T_{n-1}.$$
Since all quantities are positive,
$$x_n=\sqrt{\frac{S_{n-1}}{T_{n-1}}}.$$
Using
$$a_{n-1}^2=S_{n-1}T_{n-1},$$
one obtains
$$\sqrt{\frac{S_{n-1}}{T_{n-1}}} =\frac{S_{n-1}}{a_{n-1}}.$$
Dropping positivity would introduce a spurious negative root.
The third delicate step is excluding consecutive minimal increments.
Assume
$$a_n=a_{n-1}+1.$$
Then
$$x_n=\frac{S_{n-1}}{a_{n-1}},$$
and
$$\frac{S_n}{a_n} = \frac{S_{n-1}+x_n}{a_{n-1}+1} = x_n.$$
If the next step were also minimal, then
$$x_{n+1}=\frac{S_n}{a_n}=x_n.$$
The contradiction uses exactly the pairwise distinctness assumption. Forgetting this final identification would leave a gap.
Alternative Approaches
A different presentation introduces
$$b_n=a_n-a_{n-1}.$$
Lemma 2 shows that $b_n\in{1}\cup[2,\infty)$, while Lemma 4 shows that the value $1$ never appears twice in succession. The problem then becomes a purely combinatorial minimization: among $2022$ terms $b_n$, each at least $1$, with no adjacent terms equal to $1$, the minimum possible sum is achieved by the alternating pattern
$$1,2,1,2,\dots,1,2.$$
This immediately gives
$$\sum b_n\ge 3033.$$
Another route keeps everything at the level of square differences. One proves that
$$a_n^2-a_{n-1}^2\ge 2a_{n-1}+1,$$
with equality characterized exactly. The equality characterization again excludes consecutive occurrences. Summing the resulting lower bounds and tracking equality positions leads to the same estimate. The main approach is preferable because it converts the square-difference information directly into statements about the integer increments $a_n-a_{n-1}$, making the final counting argument transparent.