Maths Olympiad Prep

Library / /253 of 383

Algebra Difficulty 8.8 Shortlist Prove it IMO

Let x1,x2,,x2023x_{1}, x_{2}, \ldots, x_{2023} be distinct real positive numbers such that
an=(x1+x2++xn)(1x1+1x2++1xn) a_{n}=\sqrt{\left(x_{1}+x_{2}+\cdots+x_{n}\right)\left(\frac{1}{x_{1}}+\frac{1}{x_{2}}+\cdots+\frac{1}{x_{n}}\right)}
is an integer for every n=1,2,,2023n=1,2, \ldots, 2023. Prove that a20233034a_{2023} \geqslant 3034.

Solutions — 2

Solution 1

We start with some basic observations. First note that the sequence a1,a2,,a2023a_{1}, a_{2}, \ldots, a_{2023} is increasing and thus, since all elements are integers, an+1an1a_{n+1}-a_{n} \geqslant 1. We also observe that a1=1a_{1}=1 and
a2=(x1+x2)(1x1+1x2)>2 a_{2}=\sqrt{\left(x_{1}+x_{2}\right)\left(\frac{1}{x_{1}}+\frac{1}{x_{2}}\right)}>2
by Cauchy-Schwarz inequality and using x1x2x_{1} \neq x_{2}. So, a23a_{2} \geqslant 3.

Now, we proceed to the main part of the argument. We observe that 3034 is about three halves of 2023. Motivated by this observation, we will prove the following.

Claim. If an+1an=1a_{n+1}-a_{n}=1, then an+2an+12a_{n+2}-a_{n+1} \geqslant 2.

In other words, the sequence has to increase by at least 2 at least half of the times. Assuming the claim is true, since a1=1a_{1}=1, we would be done since
a2023=(a2023a2022)+(a2022a2021)++(a2a1)+a1(2+1)1011+1=3034 \begin{aligned} a_{2023} & =\left(a_{2023}-a_{2022}\right)+\left(a_{2022}-a_{2021}\right)+\cdots+\left(a_{2}-a_{1}\right)+a_{1} \\ & \geqslant(2+1) \cdot 1011+1 \\ & =3034 \end{aligned}

We now prove the claim. We start by observing that
an+12=(x1++xn+1)(1x1++1xn+1)=(x1++xn)(1x1++1xn)+1+1xn+1(x1++xn)+xn+1(1x1++1xn)an2+1+21xn+1(x1++xn)xn+1(1x1++1xn)=an2+1+2an=(an+1)2, \begin{aligned} a_{n+1}^{2}= & \left(x_{1}+\cdots+x_{n+1}\right)\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n+1}}\right) \\ = & \left(x_{1}+\cdots+x_{n}\right)\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n}}\right)+1 \\ & +\frac{1}{x_{n+1}}\left(x_{1}+\cdots+x_{n}\right)+x_{n+1}\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n}}\right) \\ \geqslant & a_{n}^{2}+1+2 \sqrt{\frac{1}{x_{n+1}}\left(x_{1}+\cdots+x_{n}\right) \cdot x_{n+1}\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n}}\right)} \\ = & a_{n}^{2}+1+2 a_{n} \\ = & \left(a_{n}+1\right)^{2}, \end{aligned}
where we used AM-GM to obtain the inequality. In particular, if an+1=an+1a_{n+1}=a_{n}+1, then
1xn+1(x1++xn)=xn+1(1x1++1xn). \begin{equation*} \frac{1}{x_{n+1}}\left(x_{1}+\cdots+x_{n}\right)=x_{n+1}\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n}}\right) . \tag{1} \end{equation*}
Now, assume for the sake of contradiction that both an+1=an+1a_{n+1}=a_{n}+1 and an+2=an+1+1a_{n+2}=a_{n+1}+1 hold. In this case, (1) gives
1xn+2(x1++xn+1)=xn+2(1x1++1xn+1). \frac{1}{x_{n+2}}\left(x_{1}+\cdots+x_{n+1}\right)=x_{n+2}\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n+1}}\right) .
We can rewrite this relation as
xn+1xn+2(1xn+1(x1++xn)+1)=xn+2xn+1(xn+1(1x1++1xn)+1). \frac{x_{n+1}}{x_{n+2}}\left(\frac{1}{x_{n+1}}\left(x_{1}+\cdots+x_{n}\right)+1\right)=\frac{x_{n+2}}{x_{n+1}}\left(x_{n+1}\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n}}\right)+1\right) .
From (1) again, we conclude that xn+1=xn+2x_{n+1}=x_{n+2} which is a contradiction.

Solution 2

The trick is to compare an+2a_{n+2} and ana_{n}. Observe that
an+22=(x1++xn+2)(1x1++1xn+2)=(x1++xn)(1x1++1xn)+(xn+1+xn+2)(1xn+1+1xn+2)+(x1++xn)(1xn+1+1xn+2)+(xn+1+xn+2)(1x1++1xn)an2+(xn+1+xn+2)(1xn+1+1xn+2)+2(xn+1+xn+2)(1xn+1+1xn+2)(x1++xn)(1x1++1xn)=an2+(xn+1+xn+2)(1xn+1+1xn+2)+2an(xn+1+xn+2)(1xn+1+1xn+2), \begin{aligned} a_{n+2}^{2}= & \left(x_{1}+\cdots+x_{n+2}\right)\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n+2}}\right) \\ = & \left(x_{1}+\cdots+x_{n}\right)\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n}}\right)+\left(x_{n+1}+x_{n+2}\right)\left(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}\right) \\ & \quad+\left(x_{1}+\cdots+x_{n}\right)\left(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}\right)+\left(x_{n+1}+x_{n+2}\right)\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n}}\right) \\ \geqslant & a_{n}^{2}+\left(x_{n+1}+x_{n+2}\right)\left(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}\right) \\ & \quad+2 \sqrt{\left(x_{n+1}+x_{n+2}\right)\left(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}\right)\left(x_{1}+\cdots+x_{n}\right)\left(\frac{1}{x_{1}}+\cdots+\frac{1}{x_{n}}\right)} \\ = & a_{n}^{2}+\left(x_{n+1}+x_{n+2}\right)\left(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}\right)+2 a_{n} \sqrt{\left(x_{n+1}+x_{n+2}\right)\left(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}\right)}, \end{aligned}
where we used AM-GM to obtain the inequality. Furthermore, we have
(xn+1+xn+2)(1xn+1+1xn+2)>4 \left(x_{n+1}+x_{n+2}\right)\left(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}\right)>4
because xn+1xn+2x_{n+1} \neq x_{n+2} by assumption. Therefore, it follows that
an+22>an2+4+4an=(an+2)2 a_{n+2}^{2}>a_{n}^{2}+4+4 a_{n}=\left(a_{n}+2\right)^{2}
Because an+2a_{n+2} and ana_{n} are both positive integers, we conclude that
an+2an+3 a_{n+2} \geqslant a_{n}+3
A simple induction gives a2k+13k+a1a_{2 k+1} \geqslant 3 k+a_{1} for every k0k \geqslant 0. Since a1=1a_{1}=1, it follows that a2k+13k+1a_{2 k+1} \geqslant 3 k+1. We get the desired conclusion for k=1011k=1011.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.