Mount Inequality erupts on a sequence :o

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

821 posts

#1 h Jul 9, 2023, 4:43 AM • 24 Y

Y by EthanWYX2009, Amir Hossein, OronSH, mathfan2020, GeoKing, Supercali, Mogmog8, mathmax12, dangerousliri, oolite, Schur-Schwartz, centslordm, ismayilzadei1387, ihatemath123, Lamboreghini, Sedro, buddyram, aidan0626, megarnie, seifbaba, A21, cubres, farhad.fritl, jannatiar

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} \geqslant 3034.$

This post has been edited 6 times. Last edited by GrantStar, Jul 9, 2023, 4:54 AM
Reason: Renaming source

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

beansenthusiast505

26 posts

beansenthusiast505

#2 h Jul 9, 2023, 4:44 AM • 1 Y

Y by cubres

inequality has returned, my prayers were not answered (i’m not in imo and prob trying later but it should be p1/4 difficulty)

This post has been edited 1 time. Last edited by beansenthusiast505, Jul 9, 2023, 4:45 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

qwedsazxc

168 posts

qwedsazxc

#3 h Jul 9, 2023, 4:47 AM • 13 Y

Y by mathleticguyyy, adorefunctionalequation, Hyperabola, Geometry285, GeoKing, Rebel_1, rightways, Celestialer, centslordm, Lamboreghini, aidan0626, Lichenw, cubres

Let's show that $a_{n+2}\geq a_n+3$ for all $n$ . By C-S and AM-GM:
$a_{n+2}\geq a_n+\sqrt{\frac{(x_{n+1}+x_{n+2})^2}{x_{n+1}x_{n+2}}}>a_n+2.$ Therefore $a_{n+2}\geq a_n+3$ . Since $a_1=1$ , $a_{2023}\geq a_{2021}+3\geq\cdots\geq a_1+3033=3034$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EthanWYX2009

875 posts

EthanWYX2009

#4 h Jul 9, 2023, 4:49 AM • 9 Y

Y by GeoKing, ike.chen, ys-lg, Euler_Gauss, ehuseyinyigit, Lamboreghini, DrPoe1898, cubres, Want-to-study-in-NTU-MATH

Motivation. It is obvious to see that $3034=2022\times\frac 32+1,$ which leads us to the lemma below $.$
Lemma. For $\forall n\in\mathbb Z_+,a_{n+2}\geq a_n+3.$
Lemma Proof. As $a_n,a_{n+2}\in\mathbb Z_+,$ we only need to prove that $a_{n+2}>a_n+2.$ Using Cauchy inequality $,$
$\begin{aligned}a_{n+2}=\sqrt{\sum\limits_{k=1}^{n+2}x_k\sum\limits_{k=1}^{n+2}\frac 1{x_k}}&\geqslant\sqrt{\sum\limits_{k=1}^{n}x_k\sum\limits_{k=1}^{n}\frac 1{x_k}}+\sqrt{(x_{n+1}+x_{n+2})\left(\frac 1{x_{n+1}}+\frac 1{x_{n+2}}\right)}\\&=a_n+\sqrt{4+\frac{(x_{n+1}-x_{n+2})^2}{x_{n+1}x_{n+2}}}>a_n+2.\blacksquare\\\end{aligned}$ Proof. Using Lemma we have $a_{2023}\geq a_{2021}+3\geq\cdots\geq a_1+3\times 1011=3034.\blacksquare$

This post has been edited 2 times. Last edited by EthanWYX2009, Jul 9, 2023, 1:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

juckter

324 posts

juckter

#5 h Jul 9, 2023, 5:04 AM • 3 Y

Y by Johnson100, Saniva_Rakib_Soha, cubres

We claim $a_{n + 2} \ge a_n + 3$ which is clearly enough. Let $s_n = x_1 + x_2 + \dots + x_n$ and $h_n = \frac{1}{x_1} + \frac{1}{x_2} + \dots + \frac{1}{x_n}$ . Then

$a_{n + 1}^2 = s_{n + 1}h_{n + 1} = (s_n + x_{n + 1})\left(h_n + \frac{1}{x_{n + 1}}\right) = s_nh_n + \left(\frac{s_n}{x_{n + 1}} + x_nh_{n + 1}\right) + 1 = a_n^2 + \left(\frac{s_n}{x_{n + 1}} + x_{n + 1}h_n\right) + 1$
By AM-GM we have $\frac{s_n}{x_{n+1}} + x_{n+1}h_n \ge 2\sqrt{s_nh_n} = 2a_1$ and therefore $a_{n + 1}^2 \ge a_n^2 + 2a_n + 1 = (a_n + 1)^2$ . Thus $a_{n + 1} \ge a_n + 1$ for all $n$ , with equality if and only if $\frac{s_n}{x_{n+1}} = x_{n+1}h_n$ , or $x_{n+1}^2 = \frac{s_n}{h_n}$ . We finally prove that equality cannot happen twice in a row. Otherwise we have

$x_{n + 1}^2 = \frac{s_{n + 1}}{h_{n + 1}} = \frac{s_n + x_{n + 1}}{h_n + \frac{1}{x_{n + 1}}} = \frac{s_n + \sqrt{\frac{s_n}{h_n}}}{h_n + \sqrt{\frac{h_n}{s_n}}} = \frac{s_n}{h_n} = x_n^2$
A contradiction as $x_1, x_2, \dots, x_{2023}$ are all distinct.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

S.Ragnork1729

215 posts

S.Ragnork1729

#6 h Jul 9, 2023, 5:41 AM • 2 Y

Y by Johnson100, cubres

Solution : We will move on with a claim first.
Claim : $a_{n+2} > a_n+2$
Proof : Observe that $a_{n+2} > a_n+2$ $\Longleftrightarrow \sqrt{(x_1+....+x_{n+2})(\frac{1}{x_1}+....+\frac{1}{x_{n+2}}} > \sqrt{(x_1+....+x_{n})(\frac{1}{x_1}+....+\frac{1}{x_{n}}} +2 .$ Now let $y=\sum_{i=1}^{n} x_i$ and $z=\sum_{i=1}^{n} \frac{1}{x_i}$ , then we have to show $\sqrt{(y+x_{n+1}+x_{n+2})(z+\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})} > \sqrt{yz}+2$ $\Longleftrightarrow yz+y(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})+z(x_{n+1}+x_{n+2})+(x_{n+1}+x_{n+2})(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}) > yz+4\sqrt{yz}+4$ and it is obvious by AM-GM.
Hence we get $a_{2023} \geq a_{2021}+3 \geq a_{2019}+6 \geq \cdots a_4+3030 \geq a_1+3033 =1+3033=3034 .$ Note : The problem was very good but the main part was to prove $a_{n+2} \geq a_{n}+3$ using AM-GM and Algebraic Expansion.

This post has been edited 2 times. Last edited by S.Ragnork1729, Jul 9, 2023, 6:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathuz

1525 posts

mathuz

#7 h Jul 9, 2023, 5:53 AM • 1 Y

Y by cubres

Obviously, $a_n$ should be an increasing (strictly) sequence of positive integers with $a_1=1$ . We will show that $a_{n+1}=a_n+1$ and $a_{n+2} = a_{n+1}+1$ doesn't hold at the same time. Assume it does.

We know that $a_{n+1}^2-a_n^2=x_{n+1}\left(\frac{1}{x_1}+\ldots +\frac{1}{x_{n}}\right) + \frac{1}{x_{n+1}} \left(x_1+\ldots +x_n\right)+1 = 2a_n+1$ and $2a_n = x_{n+1}\left(\frac{1}{x_1}+\ldots +\frac{1}{x_{n}}\right) + \frac{1}{x_{n+1}} \left(x_1+\ldots +x_n\right) \ge 2a_n$ by AM-GM, so we should have $x_{n+1}\left(\frac{1}{x_1}+\ldots +\frac{1}{x_{n}}\right) = \frac{1}{x_{n+1}} \left(x_1+\ldots +x_n\right) = a_n.$ Similarly, we can obtain $x_{n+2}\left(\frac{1}{x_1}+\ldots +\frac{1}{x_{n+1}}\right) = \frac{1}{x_{n+2}} \left(x_1+\ldots +x_{n+1}\right) = a_{n+1}.$ That means $a_nx_{n+1}+x_{n+1}=x_1+x_2+\ldots +x_n+x_{n+1} = a_{n+1}x_{n+2}$ and since $a_{n+1}=a_n+1$ we get that $x_{n+1}=x_{n+2}$ , which is a contradiction.

Hence, if $a_{n+1}-a_n=1$ then $a_{n+2}-a_{n+1}>1$ , or vice versa. In any case, $a_{n+2}-a_n\ge 3$ and $a_{2023} \ge a_1+3\cdot 1011 = 3034$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GrantStar

821 posts

GrantStar

#8 h Jul 9, 2023, 6:05 AM • 9 Y

Y by RobertRogo, GeoKing, centslordm, ehuseyinyigit, Lamboreghini, channing421, aidan0626, Jack_w, cubres

Solution without words

Reason that doing the same thing for gaps of one fails

This post has been edited 2 times. Last edited by GrantStar, Jul 9, 2023, 6:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Alfredfeed

9 posts

Alfredfeed

#9 h Jul 9, 2023, 6:24 AM • 1 Y

Y by cubres

Solution without using AM-GM
Lets prove $a_{n+1}$ $\geq$ $a_{n-1}+3$

s = $x_1 + x_2 + ... + x_{n-1}$

h = $\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_{n-1}}$

$a^2_{n-1}$ = hs

$a^2_{n} = (s+x_n)(h+\frac{1}{x_n})$

$a^2_{n} = hs + \frac{s}{x_n} + {x_n}h + 1$

$a^2_{n-1} = a_{n-1}^2 + \frac{s}{x_n} + xh + 1$

assume $a^2_{n}$ = $a_{n-1}+1$ ; $a^2_{n+1}$ = $a_{n}+1$

otherwise its trivial since obviously $a_{n-1}<a_{n}$

2 $a_{n-1}=\frac{s}{x_n}+xh$

$h=\frac{a^2}{s}$

2 $a_{n-1}=\frac{s}x+\frac{x}s{a_{n-1}^2}$

let $k = \frac{s}x$

2 $a_{n-1}$ =k+ $\frac{1}k{a_{n-1}^2}$

solving for $a_{n-1}$ , we get:

$a_{n-1}$ = $\frac{s}x$

s= $a_{n-1}$ x

$a_{n-1}+1=\frac{s+x}x'$

x'(a+1)=x(a+1)

x'=x
contradiction, so $a_{n+1}$ $\geq$ $a_{n-1}+3$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AnonymousBunny

339 posts

AnonymousBunny

#10 h Jul 9, 2023, 6:29 AM • 2 Y

Y by GeoKing, cubres

The crucial claim is the following:

Claim: For any $n$ , it cannot be the case that $a_{n+1} = a_n + 1$ and $a_{n+2} = a_{n+1}+1$ .
Proof:
Suppose, FTSOC, $a_{n+1} = a_n + 1, a_{n+2} = a_{n+1}+1$ .

$a_{n+1} = a_n + 1 \iff x_{n+1} \left( x_1 + x_2 + \cdots + x_n \right) + \dfrac{1}{x_{n+1}} \left(x_1 + \cdots + x_n \right) = 2a_n$

Treat this as a quadratic in $x_{n+1}$ : its discriminant vanishes and the only root is $x_{n+1} = \dfrac{a_n}{1/x_1 + \cdots + 1/x_n}$ .
Similarly, $x_{n+2} = \dfrac{a_{n}+1}{1/x_1 + \cdots + 1/x_{n+1}}$ . I now claim that $x_{n+1} = x_{n+2}$ , which is a contradiction. This follows from a simple calculation:

$x_{n+1} = x_{n+2} \iff a_n \left( \dfrac{1}{x_1} + \cdots + \dfrac{1}{x_{n+1}}\right) = (a_n+1) \left( \dfrac{1}{x_1} + \cdots + \dfrac{1}{x_n} \right) \iff x_{n+1} = \dfrac{a_n}{1/x_1+\cdots + 1/x_n} \blacksquare$
Now, note that $a_2 \geq 2$ by Cauchy-Schwartz. Since equality cannot hold (as $x_1, x_2$ are distinct), in fact, $a_2 \geq 3$ . Also note that $a_n$ is strictly increasing. The claim shows that $a_i$ must jump more than one once every two steps, i.e., $a_{n+2} \geq a_n + 3$ . Applying this inequality repeatedly gives the result.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Manteca

52 posts

Manteca

#11 h Jul 9, 2023, 6:35 AM • 3 Y

Y by ZNatox, GeoKing, cubres

$a_{n+1}^2 = a_n^2 + 1 + x_{n+1}(\frac{1}{x_1}+ \cdots + \frac{1}{x_{n}}) + \frac{1}{x_{n+1}}(x_1 + \cdots + x_{n}) \geq a_n^2 + 1 + 2a_n = (a_n+1)^2$ By AM-GM, with equality if and only if the two things we are summing are equal, in particular $x_{n+1} = \sqrt{\frac{A}{B}}$ where $A = \sum a_i$ and $B = \sum \frac{1}{a_i}$ .
If also $a_{n+2} = a_{n+1} + 1$ then again we must have $x_{n+2} = \sqrt{\frac{A+\sqrt{\frac{A}{B}}}{B+\sqrt{\frac{B}{A}}}}$ but both things inside the square root are equal so $x_{n+1} = x_{n+2}$ but that cant happen so at least $a_{n+2} \geq a_n + 3$ . Finally $a_{2023} \geq 1 + 3 \cdot 1011 = 3034$ as we wanted to show.

This post has been edited 1 time. Last edited by Manteca, Jul 9, 2023, 6:37 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

djmathman

7939 posts

djmathman

#12 h Jul 9, 2023, 6:44 AM • 3 Y

Y by Assassino9931, RobertRogo, cubres

Sneaky little bugger.

Define $A_n := x_1 + x_2 + \cdots + x_n$ and $B_n := \tfrac 1{x_1} + \tfrac1{x_2} + \cdots + \tfrac1{x_n}$ . Observe that
$\begin{align*} a_{n+1}^2 &= \left(A_n + x_{n+1}\right)\left(B_n + \frac{1}{x_{n+1}}\right) \\ &= A_nB_n + \frac{A_n}{x_{n+1}} + B_n x_{n+1} + 1 \\ &\geq A_nB_n + 2\sqrt{A_nB_n} + 1 = (a_n + 1)^2. \end{align*}$ Hence $a_{n+1} \geq a_n + 1$ .

We now prove the stronger inequality $a_{n+2} \geq a_n + 3$ . Suppose, by way of contradiction, that $a_{n+2} = a_n + 2$ . Then equality cases in both inequalities above (i.e. for $a_{n+1}$ and $a_{n+2}$ ) hold, so $x_{n+1} = \sqrt{\tfrac{A_n}{B_n}}$ and
$x_{n+2}^2 =\frac{A_n + x_{n+1}}{B_n + \frac 1{x_{n+1}}} = \frac{A_n + \sqrt{\frac{A_n}{B_n}}}{B_n + \sqrt{\frac{B_n}{A_n}}}= \frac{A_n}{B_n}.$ (The last equality is true because $\tfrac{x_{n+1}}{\frac{1}{x_{n+1}}} = x_{n+1}^2 = \tfrac{A_n}{B_n}$ .) This contradicts the fact that the $x_j$ are pairwise distinct.

Remark. I think the claims here are motivated, but the main sticking point for me was getting over my confusion about why the bound wasn't tighter. (It didn't help that I made a few algebra mistakes along the way.) Proving the inequality $a_{n+2} \geq a_n + 3$ directly is certainly faster, but this solution shows why we need to consider this stronger bound in the first place.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Minkowsi47

48 posts

Minkowsi47

#13 h Jul 9, 2023, 7:34 AM • 1 Y

Y by cubres

MOTIVATION : The thing which motivate $a_{n+2} \geq a_{n}+3$ is $a_{2023}\geq 3034$ as actually this is the point for me which makes me realise to follow up this claim. proving that claim is same as GrantStar did and finishes up the problem. :-D

This post has been edited 1 time. Last edited by Minkowsi47, Jul 9, 2023, 7:35 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Tintarn

9045 posts

Tintarn

#14 h Jul 9, 2023, 7:37 AM • 3 Y

Y by carefully, ehuseyinyigit, cubres

So. Is the bound $3034$ actually sharp?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PythZhou

6 posts

PythZhou

#15 h Jul 9, 2023, 7:39 AM • 1 Y

Y by cubres

Too easy for IMO inequality.
Claim : $a_{n+2}>a_{n}+2$ which is equivalent to $a_{n+2} \ge a_{n}+3$ since $a_n$ is an integer. Hence $a_{2023} \ge a_1+\sum_{n=1}^{1011}3=3034$
Then prove the claim:

We define $X_n=x_1 + x_2 + \cdots + x_n$ and $Y_n=\frac{1}{x_1}+\cdots+\frac{1}{x_{n}}$ , so $a_n=\sqrt{X_n Y_n}$
$\begin{align*} a_{n+2}=&\sqrt{(x_1 + x_2 + \cdots + x_n+x_{n+1}+x_{n+2}) (\frac{1}{x_1}+\cdots+\frac{1}{x_{n}}+\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})} \\ &= \sqrt{(X_n+x_{n+1}+x_{n+2})(Y_n+\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})} \\ &= \sqrt{a_n^2+X_n(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})+Y_n(x_{n+1}+x_{n+2})+(x_{n+1}+x_{n+2})(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})} \\ &> \sqrt{a_n^2+ 4 \sqrt{X_nY_n}+4} \\ &= \sqrt{a_n^2+4a_n+4}=a_n+2 \end{align*}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sami1618

928 posts

sami1618

#84 h Jul 17, 2024, 6:07 PM • 2 Y

Y by GeoKing, cubres

We show that we can not have $a_n=k$ , $a_{n+1}=k+1$ , and $a_{n+2}=k+2$ , which is sufficient. Let $s=x_1+x_2+\dots+x_n$ and $t=\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_n}$ . Then $k^2=st$ $(k+1)^2=(s+x_{n+1})(t+\frac{1}{x_{n+1}})\iff 2k=t\cdot x_{n+1}+s\cdot \frac{1}{x_{n+1}}$ $(k+2)^2=(s+x_{n+1}+x_{n+2})(t+\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})\iff 2k+2=(t+\frac{1}{x_{n+1}})\cdot x_{n+2}+(s+x_{n+1})\cdot \frac{1}{x_{n+1}}$ Applying AM-GM to the third equality we must have that $t\cdot x_{n+1}=s\cdot \frac{1}{x_{n+1}}\iff x_{n+1}=\frac{\sqrt{s}}{\sqrt{t}}$ . Applying AM-GM to the fifth equality we must have that $(t+\frac{1}{x_{n+1}})\cdot x_{n+2}=$ $(s+x_{n+1})\cdot \frac{1}{x_{n+1}}\iff x_{n+2}=\frac{\sqrt{s}}{\sqrt{t}}$ , a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sammy27

83 posts

Sammy27

#85 h Jul 17, 2024, 9:57 PM • 2 Y

Y by Eka01, cubres

Solution

This post has been edited 3 times. Last edited by Sammy27, Jul 17, 2024, 10:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dkedu

180 posts

dkedu

#86 h Jul 18, 2024, 11:33 PM • 1 Y

Y by cubres

We will show that $a_{n+2} \ge a_n + 3$ which implies the result since $a_1 = 1$ .

By Cauchy-Schwarz we have $a_{n+2} = \sqrt{[(x_1+x_2+\dots+ x_n) + (x_{n+1} + x_{n+2})]\left[\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+ \frac 1{x_n} \right)+ \left(\frac{1}{x_{n+1}} + \frac{1}{x_{n+2}}\right)\right]} \ge \sqrt{(x_1+x_2+\dots+x_n)\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_n}\right)} + \sqrt{\frac{(x_{n+1} + x_{n+2})^2 }{x_{n+1}x_{n+2}}} > a_n + 2$ where the final inequality is strict since $x_{n+1} \neq x_{n+2}$ so we have the result $a_{n+2} \ge a_n + 3$ since $a_i$ is an integer for all $i$ so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

brainfertilzer

1831 posts

brainfertilzer

#87 h Jul 20, 2024, 8:55 PM • 1 Y

Y by cubres

Note that $a_1 = 1$ so it suffices to show $a_{n+2}\ge a_n + 3$ for all $n$ and we'll be done by induction. Fix $n$ and let $S = \sum_{i\le n} x_i$ and $T = \sum_{i\le n}1/x_i$ . Relabel $x_{n+1}, x_{n+2}$ as $p,q$ for convenience of typesetting. Then note that
$a_{n+2} = \sqrt{\left(S + p + q\right)\left(T + \frac{1}{p} + \frac{1}{q}\right)}\stackrel{\text{CS}}{\ge} \sqrt{ST} + \sqrt{p\cdot \frac{1}{p}} + \sqrt{q \cdot \frac{1}{q}} = a_n + 2.$ But note that equality only holds if $S/T = p/(1/p) = q/(1/q)$ . But this means $p^2 = q^2\implies p = q$ , impossible since the $x_i$ are distinct. Hence equality doesn't hold and we have $a_{n+2} > a_n + 2$ . Since the $a_i$ are integers, this means $a_{n+2}\ge a_n + 3$ as needed.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

N3bula

302 posts

N3bula

#88 h Sep 14, 2024, 7:14 AM • 1 Y

Y by cubres

Proceed by induction, clearly we have that $a_1=1$ , I will now prove $a_{n+2}>a_{n}+2$ which gives $a_{n+2}\geq a_n+3$ .
We get:
$a_{n+2}^2=a_n^2+\left( \frac{1}{x_{n+1}} +\frac{1}{x_{n+2}} \right)(x_{n+1}+x_{n+2})+(x_{n+1}+x_{n+2})\left(\sum_{i=1}^{n}\frac{1}{x_i}\right)+\left(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}\right)\left(\sum_{i=1}^{n}x_i\right)$ Now by two applications of am-gm and the fact $a_{n+1}\neq a_{n+2}$ we get:
$a_{n+2}^2> a_n^2+4+2a_n\sqrt{\left( \frac{1}{x_{n+1}} +\frac{1}{x_{n+2}} \right)(x_{n+1}+x_{n+2})}$ A final am-gm application gives:
$a_{n+2}^2>a_n^2+4a_n+4$ Which suffices.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bobthesmartypants

4337 posts

bobthesmartypants

#89 h Sep 22, 2024, 1:48 AM • 1 Y

Y by cubres

Intimidating-looking problem that ends up being not so bad at all.

We use induction to show $a_{2n-1}\ge 3n-2$ and $a_{2n}\ge 3n$ . Base cases $a_1=1$ is trivial, and $a_2\ge 3$ follows from Cauchy-Schwarz $a_2= \sqrt{(x_1+x_2)\left(\frac{1}{x_1}+\frac{1}{x_2}\right)} > 2\implies a_2\ge 3$ noting that equality case $x_1=x_2$ cannot be obtained.

Now assuming $a_{2n-1}\ge 3n-2$ and $a_{2n}\ge 3n$ , we first find by Cauchy Schwarz
$\begin{align*} a_{2n+1} &= \sqrt{(x_1+\cdots +x_{2n}+x_{2n+1})\left(\frac{1}{x_1}+\cdots + \frac{1}{x_{2n}}+\frac{1}{x_{2n+1}}\right)}\\ &= \sqrt{((x_1+\cdots +x_{2n})+x_{2n+1})\left(\frac{a_{2n}^2}{x_1+\cdots +x_{2n}}+\frac{1}{x_{2n+1}}\right)}\\ &\ge a_{2n}+1 \ge 3(n+1)-2 \end{align*}$ with equality case $x_{2n+1} = \frac{x_1+\cdots +x_{2n}}{a_{2n}}$ , as desired.

Similarly, we find $a_{2n+2}\ge a_{2n+1}+1$ with equality case $x_{2n+2} = \frac{x_1+\cdots +x_{2n+1}}{a_{2n+1}}$ . Now, the key insight is to realize that these two equality cases cannot both be true. If they were, then $x_{2n+1}$ is the average of $x_1, \ldots, x_{2n}$ and $a_{2n}-2n$ zeros. Meanwhile, since for equality case $a_{2n+1} = a_{2n}+1$ , then $x_{2n+2}$ is the average of $x_1, \ldots, x_{2n}$ and $a_{2n}-2n$ zeros and $x_{2n+1}$ , the average of these numbers, which is still just the average of these numbers. In other words, $x_{2n+2} = x_{2n+1}$ , which is disallowed. Thus, in actuality $a_{2n+2}\ge a_{2n+1}+2 \ge 3(n+1)$ as desired.

Bringing it back to the problem at hand, we get $a_{2023}\ge 3034$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

661 posts

cursed_tangent1434

#90 h Dec 6, 2024, 12:47 AM • 1 Y

Y by cubres

This is a really interesting problem, and I was pleasantly surprised when I managed to solve this in contest two years ago.

We proceed via induction to show that for all odd integers $n$ , $a_n \ge n + \frac{n-1}{2}$ .

First note that
$a_1 = \sqrt{x_1 \cdot \frac{1}{x_1}}=1$
Now, assume the claim is true for some odd integer $m=2k+1 \ge1$ . Throughout this proof, we will use the following key inequality,

Claim : For all positive real numbers $a$ and $b$ ,
$(a+b)\left(\frac{1}{a}+\frac{1}{b}\right) \ge 4$
Proof : This is simply Cauchy Schwarz. Note that,
$(\sqrt{a}^2 + \sqrt{b}^2)\left(\frac{1}{\sqrt{a}^2}+\frac{1}{\sqrt{b}^2}\right) \ge (1+1)^2 = 4$ as desired.

Now, we are ready for the induction. Note,
$\begin{align*} a_{m+2} &=\sqrt{(x_1+x_2+\dots+x_{m+2})\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_{m+2}}\right)}\\ a_{m+2}^2 & = (x_1+x_2+\dots+x_{m+2})\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_{m+2}}\right)\\ a_{m+2}^2 &= (x_1+x_2+\dots+x_m)\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_m}\right) + \left(\frac{1}{x_{m+1}} +\frac{1}{x_{m+2}}\right)(x_{m+1}+x_{m+2})\\ & + (x_1+x_2 + \dots + x_m)\left(\frac{1}{x_{m+1}}+\frac{1}{x_{m+2}}\right) + \left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_m}\right)(x_{m+1}+x_{m+2})\\ & \ge (3k+1)^2 + 4 + \frac{(3k+1)^2(x_{m+1}+x_{m+2})}{x_1+x_2+\dots + x_m} + \frac{4(x_1+x_2+\dots + x_m)}{x_{m+1}+x_{m+2}}\\ & \ge (3k+1)^2 +4 + 2 \sqrt{\frac{4(3k+1)^2(x_{m+1}+x_{m+2})(x_1+x_2+\dots + x_m)}{(x_1+x_2+\dots + x_m)(x_{m+1}+x_{m+2})}}\\ & \ge (3k+1)^2 + 4(3k+1) + 4\\ & \ge (3k+3)^2\\ a_{m+2} & \ge 3k+3 \end{align*}$ But, if $a_{m+2}=3k+3$ , equality must hold at each of the above inequalities. In particular we need
$\left(\frac{1}{x_{m+1}} +\frac{1}{x_{m+2}}\right)(x_{m+1}+x_{m+2})=4$ which requires $x_{m+1}=x_{m+2}$ which is impossible if $x_1,x_2,\dots,x_{m+2}$ are pairwise distinct positive reals. Thus equality does not hold and $a_{m+2}>3k+3$ . Further since $a_{m+2}$ is an integer we must have $a_{m+2} \ge 3k+4$ so,
$a_{m+2} \ge (m+2) + \frac{m+1}{2}$ which completes the induction. Thus,
$a_{2023} \ge 2023 + \frac{2022}{2} = 3034$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8880 posts

HamstPan38825

#91 h Dec 7, 2024, 12:04 AM • 1 Y

Y by cubres

Observe that $a_1 = 1 < a_2 < \dots$ . The crux of the problem is the following claim:

Claim: There does not exist an index $n$ such that $a_{n+1} - a_n = 1$ and $a_n - a_{n-1} = 1$ simultaneously.

Proof: Suppose such an index $n$ existed. Then observe that
$\begin{align*} a_n^2 &= a_{n-1}^2 + 1 + x_n\left(\frac 1{x_1} + \frac 1{x_2} + \cdots +\frac 1{x_{n-1}}\right) + \frac 1{x_n}\left(x_1+x_2+\cdots+x_n\right) \\ &\geq a_{n-1}^2 + 1 + 2\sqrt{(x_1+x_2+\cdots+x_n)\left(\frac 1{x_1} + \frac 1{x_2} + \cdots + \frac 1{x_n}\right)} \\ &= (a_n+1)^2. \end{align*}$ Importantly, equality only holds when $x_n = \sqrt{\frac{x_1+x_2+\cdots+x_{n-1}}{\frac 1{x_1} +\frac 1{x_2}+\cdots+\frac 1{x_{n-1}}}}$ . Let $A$ and $B$ be the numerator and denominator of this quantity. The same argument applied to the index $n+1$ yields $x_{n+1} = \sqrt{\frac{A+\sqrt{\frac AB}}{B+\sqrt{\frac BA}}} = \sqrt{\frac{A\sqrt{AB}+A}{B\sqrt{AB}+B}} = \sqrt{\frac AB} = x_n$ which is a contradiction. $\blacksquare$

So in particular, $a_{n+2} - a_n \geq 3$ for each $n$ . It follows that $a_{2023} \geq 1 + 1011 \cdot 3 = 3034$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aiden-1089

306 posts

Aiden-1089

#92 h Jan 6, 2025, 7:06 PM • 1 Y

Y by cubres

Note that $a_1=1$ . It suffices to show that $a_{n+2} \geq a_n+3$ for all $n$ .
Noting that $x_{n+1}, x_{n+2}$ are distinct,
$\begin{align*} a_{n+2}^2 &=\left(\sum_{i=1}^{n+2} x_i \right)\left(\sum_{i=1}^{n+2} \frac{1}{x_i} \right) \\ &=a_n^2 + (x_{n+1}+x_{n+2})\left(\sum_{i=1}^n \frac{1}{x_i} \right) + \left(\frac{1}{x_{n+1}} + \frac{1}{x_{n+2}} \right)\left(\sum_{i=1}^n x_i \right) + (x_{n+1}+x_{n+2})\left(\frac{1}{x_{n+1}} + \frac{1}{x_{n+2}} \right) \\ &> a_n^2 + (x_{n+1}+x_{n+2})\left(\sum_{i=1}^n \frac{1}{x_i} \right) + \left(\frac{4}{x_{n+1}+x_{n+2}} \right)\left(\sum_{i=1}^n x_i \right) + 4 \\ &\geq a_n^2 + 4 \sqrt{\left(\sum_{i=1}^n \frac{1}{x_i} \right)\left(\sum_{i=1}^n x_i \right)} + 4 =(a_n+2)^2. \end{align*}$ Since $a_{n+2}$ and $a_n$ are integers, $a_{n+2} > a_n+2 \implies a_{n+2} \geq a_n+3$ so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

1016 posts

AshAuktober

#93 h Jan 15, 2025, 4:44 AM • 1 Y

Y by cubres

Very beautiful problem, definitely one of the nicer algebra problems out there.
Claim 1: $a_{n+1} \ge a_n + 1$ with equality iff $x_{n+1} = \frac{x_1 + \dots + x_n}{a_n}$ .
Proof: We have
$a_{n+1} = \sqrt{a_n^2 + 1 + x_{n+1} \left(\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_n}\right) +\frac{ x_1 + x_2 + ... + x_n}{x_{n+1}}}$ $\stackrel{\textrm{AM-GM}}{\ge} \sqrt{a_n^2 + 1 + 2a_n} = a_n + 1.$ Equality holds iff equality holds in AM-GM, i. e.
$x_{n+1}^2 = \frac{x_1 + x_2 + ... + x_n}{\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_n}} = \frac{ x_1 + x_2 + ... + x_n}{\frac{a_n}{ x_1 + x_2 + ... + x_n}}$ $\iff x_{n+1} = \frac{x_1 + \dots + x_n}{a_n}$ as desired. $\square$

Claim 2: We cannot simultaneously have $a_{n+2} = a_{n+1} + 1, a_{n+1} = a_n + 1$ .
Proof: Note that for equality to hold in both cases, we need
$x_{n+2} = \frac{x_1 + x_2 + \dots + x_n + x_{n+1}}{a_n + 1} = \frac{\frac{a_n+1}{a_n} \times x_1 + \dots + x_n}{a_n+1} = \frac{x_1 + x_2 + \dots + x_n}{a_n} = x_{n+1}.$ But the sequence is composed of distinct terms, so this is impossible. $\square$

Note that due to Claim 2, we must have $a_{n+2} \ge a_n + 3$ . Therefore,
$a_{2023} \ge a_{2021} + 3$ $\ge a_{2019} + 6$ $\ge a_{2017} + 9$ $\vdots$ $\ge a_1 + 3 \times 1011 = 3034$ as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

complex2math

7 posts

complex2math

#94 h Jan 25, 2025, 2:28 AM • 1 Y

Y by cubres

Let $S_n := x_1 + \cdots + x_n$ and $T_n := \frac{1}{x_1} + \cdots + \frac{1}{x_n}$ , then
$\begin{aligned} a_{n + 2}^2 &= (S_n + x_{n + 1} + x_{n + 2})\left(T_n + \frac{1}{x_{n + 1}} + \frac{1}{x_{n + 2}}\right) \\ &= S_n T_n + \frac{S_n}{x_{n + 1}} + x_{n + 1}T_n + \frac{S_n}{x_{n + 2}} + x_{n + 2}T_n + \frac{x_{n+2}}{x_{n+1}} + \frac{x_{n + 1}}{x_{n+2}} + 2 \\ &\ge a_n^2 + 2a_n + 2a_n + 4 = (a_n + 2)^2 \end{aligned}$
The equality cannot hold because $x_{n + 1} \neq x_{n + 2}$ , thus $a_{n + 2} \ge a_n + 3$ and $a_{2n + 1} \ge 3n + 1$ follows easily by induction.

I am surprised that it is rated A3 on the shortlist, considering the difficulty of this problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pie854

246 posts

pie854

#95 h Mar 5, 2025, 6:38 PM • 1 Y

Y by cubres

Note that by CS: $a_n=\sqrt{(x_1+\dots+x_{n-2}+x_{n-1}+x_n)(1/x_1+\dots+1/x_{n-2}+1/x_{n-1}+1/x_n)} \geq \sqrt{(x_1+\dots+x_{n-2})(1/x_1+\dots+1/x_{n-2})}+\sqrt{x_{n-1}\cdot \frac{1}{x_{n-1}}}+\sqrt{x_n\cdot \frac{1}{x_n}}=a_{n-2}+2.$ If equality were to hold, then we would have $\frac{x_n}{1/x_n}=\frac{x_{n-1}}{1/x_{n-1}}$ i.e. $x_n=x_{n-1}$ , which is not possible. Thus, $a_n>a_{n-2}+2\implies a_n\geq a_{n-2}+3.$ By induction it follows that $a_{2023}\geq 3033+a_1=3034$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

685 posts

Ilikeminecraft

#97 h Mar 11, 2025, 3:58 AM • 1 Y

Y by cubres

We prove the following lower bound via induction:
Claim: $a_n\geq \frac{3n + 1}{2}$
Proof: We prove $a_n \geq a_{n - 2} + 2$ with induction. First, note that $a_1 = 1.$

Now, we prove the inductive step. Observe that
$\begin{align*} a_n^2 & = a_{n - 2}^2 + \left(\frac1{x_n} + \frac1{x_{n - 1}}\right)(x_{n - 2} + x_{n - 3} + \dots + x_1) + (x_n + x_{n - 1})\left(\frac1{x_{n - 2}} + \frac1{x_{n - 3}} + \dots + \frac1{x_1}\right) + \left(\frac1{x_n} + \frac1{x_{n - 1}}\right)(x_n + x_{n - 1})\\ & \geq a_{n- 2}^2 + 4 + 2\sqrt{(x_n + x_{n - 1})\left(\frac1{x_{n - 2}} + \frac1{x_{n - 3}} + \dots + \frac1{x_1}\right)\left(\frac1{x_n} + \frac1{x_{n - 1}}\right)(x_n + x_{n - 1})} \\ & \geq a_{n - 2}^2 + 4 + 4a_{n - 2} = (a_{n - 2} + 2)^2 \end{align*}$
This finishes.

This post has been edited 1 time. Last edited by Ilikeminecraft, Mar 11, 2025, 3:59 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Nari_Tom

117 posts

Nari_Tom

#98 h Apr 22, 2025, 6:25 AM • 1 Y

Y by cubres

Where is shortlist 2024 huh, some people in my country (including me) already have it and there is no reason to not post it in here cause it's potentially public now LOL

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sangsidhya

23 posts

sangsidhya

#99 h Apr 24, 2025, 10:39 AM

Y by

EthanWYX2009 wrote:

Motivation. It is obvious to see that $3034=2022\times\frac 32+1,$ which leads us to the lemma below $.$
Lemma. For $\forall n\in\mathbb Z_+,a_{n+2}\geq a_n+3.$

how does it intuitively lead to this?

Z K Y