Maths Olympiad Prep

Library / /3 of 7

Algebra Difficulty 5.6 AIME, harder Prove it Romania

Fix an integer n2n \ge 2 and let a1,a2,,ana_1, a_2, \dots, a_n be real numbers in the closed interval [1,2024][1, 2024]. Prove that
i=1n1ai(a1+a2++ai)>144n(n+33). \sum_{i=1}^{n} \frac{1}{a_i} (a_1 + a_2 + \dots + a_i) > \frac{1}{44} n(n + 33).

Solution

Let Aj={i:2j1ai<2j},j=1,2,,11A_j = \{i: 2^{j-1} \le a_i < 2^j\}, j = 1, 2, \dots, 11. The AjA_j form a partition of the index set {1,2,,n}\{1, 2, \dots, n\}.

Note that, for every jj in the range 1 through 11, if AjA_j is non-empty, then
iAj1ai(a1+a2++ai)=iAj(a1+a2++ai1ai+1)>k=0Aj1k2j12j+Aj=12k=0Aj1k+Aj=14Aj(Aj1)+Aj=14Aj(Aj+3); \begin{aligned} \sum_{i \in A_j} \frac{1}{a_i} (a_1 + a_2 + \dots + a_i) &= \sum_{i \in A_j} \left( \frac{a_1 + a_2 + \dots + a_{i-1}}{a_i} + 1 \right) \\ &> \sum_{k=0}^{|A_j|-1} \frac{k \cdot 2^{j-1}}{2^j} + |A_j| = \frac{1}{2} \sum_{k=0}^{|A_j|-1} k + |A_j| \\ &= \frac{1}{4} |A_j|(|A_j| - 1) + |A_j| = \frac{1}{4} |A_j|(|A_j| + 3); \end{aligned}

As the AjA_j form a partition of the index set {1,2,,n}\{1, 2, \dots, n\} and at least one AjA_j is non-empty,

\begin{aligned}
\sum_{i=1}^{n} \frac{1}{a_i} (a_1 + a_2 + \dots + a_i) &= \sum_{j=1}^{11} \sum_{i \in A_j} \frac{1}{a_i} (a_1 + a_2 + \dots + a_i) \\
&> \frac{1}{4} \sum_{j=1}^{11} |A_j|(|A_j| + 3) = \frac{1}{4} \left( \sum_{j=1}^{11} |A_j|^2 + 3n \right) \\
&\ge \frac{1}{4} \left( \frac{n^2}{11} + 3n \right) = \frac{1}{44} n(n + 33), \text{ by Cauchy-Schwarz.}
\end{aligned}

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 and solution reproduced as published; topic and difficulty added by this site.