Maths Olympiad Prep

Library / /2 of 3

Algebra Difficulty 6.7 National Olympiad Prove it Canada

Problem:
Suppose that the real numbers a1,a2,,a100a_{1}, a_{2}, \ldots, a_{100} satisfy
a1a2a1000a1+a2100a3+a4++a100100 \begin{gathered} a_{1} \geq a_{2} \geq \cdots \geq a_{100} \geq 0 \\ a_{1}+a_{2} \leq 100 \\ a_{3}+a_{4}+\cdots+a_{100} \leq 100 \end{gathered}
Determine the maximum possible value of a12+a22++a1002a_{1}^{2}+a_{2}^{2}+\cdots+a_{100}^{2}, and find all possible sequences a1,a2,,a100a_{1}, a_{2}, \ldots, a_{100} which achieve this maximum.

Solution

Solution:
We have a1+a2++a100200a_{1}+a_{2}+\cdots+a_{100} \leq 200, so
a12+a22++a1002(100a2)2+a22+a32++a1002=1002200a2+2a22+a32++a10021002(a1+a2++a100)a2+2a22+a32++a1002=1002+(a22a1a2)+(a32a3a2)+(a42a4a2)++(a1002a100a2)=1002+(a2a1)a2+(a3a2)a3+(a4a2)a4++(a100a2)a100 \begin{aligned} a_{1}^{2}+a_{2}^{2}+\cdots+a_{100}^{2} & \leq (100-a_{2})^{2}+a_{2}^{2}+a_{3}^{2}+\cdots+a_{100}^{2} \\ & = 100^{2}-200 a_{2}+2 a_{2}^{2}+a_{3}^{2}+\cdots+a_{100}^{2} \\ & \leq 100^{2}-(a_{1}+a_{2}+\cdots+a_{100}) a_{2}+2 a_{2}^{2}+a_{3}^{2}+\cdots+a_{100}^{2} \\ & = 100^{2}+(a_{2}^{2}-a_{1} a_{2})+(a_{3}^{2}-a_{3} a_{2})+(a_{4}^{2}-a_{4} a_{2})+\cdots+(a_{100}^{2}-a_{100} a_{2}) \\ & = 100^{2}+(a_{2}-a_{1}) a_{2}+(a_{3}-a_{2}) a_{3}+(a_{4}-a_{2}) a_{4}+\cdots+(a_{100}-a_{2}) a_{100} \end{aligned}
Since a1a2a1000a_{1} \geq a_{2} \geq \cdots \geq a_{100} \geq 0, none of the terms (aiaj)ai(a_{i}-a_{j}) a_{i} is positive. Thus a12+a22++a100210,000a_{1}^{2}+a_{2}^{2}+\cdots+a_{100}^{2} \leq 10,000 with equality holding if and only if
a1=100a2 and a1+a2++a100=200 a_{1}=100-a_{2} \quad \text{ and } \quad a_{1}+a_{2}+\cdots+a_{100}=200
and each of the products
(a2a1)a2,(a3a2)a3,(a4a2)a4,,(a100a2)a100 (a_{2}-a_{1}) a_{2}, \quad (a_{3}-a_{2}) a_{3}, \quad (a_{4}-a_{2}) a_{4}, \cdots, (a_{100}-a_{2}) a_{100}
equals zero. Since a1a2a3a1000a_{1} \geq a_{2} \geq a_{3} \geq \cdots \geq a_{100} \geq 0, the last condition holds if and only if for some i1i \geq 1 we have a1=a2==aia_{1}=a_{2}=\cdots=a_{i} and ai+1==a100=0a_{i+1}=\cdots=a_{100}=0. If i=1i=1, then we get the solution 100,0,0,,0100,0,0,\ldots,0. If i2i \geq 2, then from a1+a2=100a_{1}+a_{2}=100, we get that i=4i=4 and the second optimal solution 50,50,50,50,0,0,,050,50,50,50,0,0, \ldots, 0.

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.