Maths Olympiad Prep

Track / Stage 5 / 345 of 400 #945 of 1964

Problem 945

AIME late
Algebra Difficulty 5.7 Find the answer

6⋅118x1,x2,⋯ ,x19936 \cdot 118 \quad x_{1}, x_{2}, \cdots, x_{1993} satisfy
∣x1−x2∣+∣x2−x3∣+⋯+∣x1992−x1993∣=1993,yk=x1+x2+⋯+xkk,(k=1,2,⋯ ,1993) \begin{array}{l} \left|x_{1}-x_{2}\right|+\left|x_{2}-x_{3}\right|+\cdots+\left|x_{1992}-x_{1993}\right|=1993, \\ y_{k}=\frac{x_{1}+x_{2}+\cdots+x_{k}}{k},(k=1,2, \cdots, 1993) \end{array}

Then what is the maximum possible value of ∣y1−y2∣+∣y2−y3∣+⋯+∣y1992−y1993∣\left|y_{1}-y_{2}\right|+\left|y_{2}-y_{3}\right|+\cdots+\left|y_{1992}-y_{1993}\right|?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

[Solution]
∣yk−yk+1∣=∣x1+x2+⋯+xkk−x1+x2+⋯+xk+xk+1k+1∣=1k(k+1)∣ (x1−xk+1)+(x2−xk+1)+⋯+(xk−xk+1)∣⩽1k(k+1)(∣x1−x2∣+2∣x2−x3∣+⋯+k∣xk−xk+1∣)k(k+1)∑i=1ki∣xi−xi+1∣, \begin{array}{l} \left|y_{k}-y_{k+1}\right|=\left|\frac{x_{1}+x_{2}+\cdots+x_{k}}{k}-\frac{x_{1}+x_{2}+\cdots+x_{k}+x_{k+1}}{k+1}\right| \\ = \left.\frac{1}{k(k+1)} \right\rvert\,\left(x_{1}-x_{k+1}\right)+\left(x_{2}-x_{k+1}\right)+\cdots+\left(x_{k}-\right. \\ \left.x_{k+1}\right) \mid \\ \leqslant \frac{1}{k(k+1)}\left(\left|x_{1}-x_{2}\right|+2\left|x_{2}-x_{3}\right|+\cdots+k \mid x_{k}\right. \\ -\frac{\left.x_{k+1} \mid\right)}{k(k+1)} \sum_{i=1}^{k} i\left|x_{i}-x_{i+1}\right|, \end{array}

Thus, ∣y1−y2∣+∣y2−y3∣+⋯+∣y1992−y1993∣\left|y_{1}-y_{2}\right|+\left|y_{2}-y_{3}\right|+\cdots+\left|y_{1992}-y_{1993}\right|
=∑k=11992∣yk−yk+1∣=∑k=11992∑i=1kik(k+1)∣xi−xi+1∣=∑i=11992∑k=11992ik(k+1)∣xi−xi+1∣=∑i=11992i[1i(i+1)+1(i+1)(i+2)+⋯+11992⋅1993]⋅∣ xi−xi+11992∣⩽∑i=11992(1i−11993)⋅∣xi−xi+1∣=(1−11993)⋅∣xi−xi+1∣=(1−11993)⋅∑i=11992∣xi−xi+1∣=1992. \begin{aligned} & =\sum_{k=1}^{1992}\left|y_{k}-y_{k+1}\right| \\ = & \sum_{k=1}^{1992} \sum_{i=1}^{k} \frac{i}{k(k+1)}\left|x_{i}-x_{i+1}\right| \\ = & \sum_{i=1}^{1992} \sum_{k=1}^{1992} \frac{i}{k(k+1)}\left|x_{i}-x_{i+1}\right| \\ = & \left.\sum_{i=1}^{1992} i\left[\frac{1}{i(i+1)}+\frac{1}{(i+1)(i+2)}+\cdots+\frac{1}{1992 \cdot 1993}\right] \cdot \right\rvert\, x_{i}- \\ & x_{i+1}^{1992} \mid \\ \leqslant & \sum_{i=1}^{1992}\left(\frac{1}{i}-\frac{1}{1993}\right) \cdot\left|x_{i}-x_{i+1}\right| \\ = & \left(1-\frac{1}{1993}\right) \cdot\left|x_{i}-x_{i+1}\right| \\ = & \left(1-\frac{1}{1993}\right) \cdot \sum_{i=1}^{1992}\left|x_{i}-x_{i+1}\right| \\ = & 1992 . \end{aligned}

On the other hand, if we let x1=t+1993,x2=x3=⋯=x1993=tx_{1}=t+1993, x_{2}=x_{3}=\cdots=x_{1993}=t,
then
yk−yk+1∣=ik(k+1)⋅∣x1−x2∣ =1993k(k+1)∑k=11992∣yk−yk+1∣=1993⋅∑k=119921k(k+1)=1992. \begin{array}{l} \left.y_{k}-y_{k+1}\left|=\frac{i}{k(k+1)} \cdot\right| x_{1}-x_{2} \right\rvert\,=\frac{1993}{k(k+1)} \\ \sum_{k=1}^{1992}\left|y_{k}-y_{k+1}\right|=1993 \cdot \sum_{k=1}^{1992} \frac{1}{k(k+1)}=1992 . \end{array}

Therefore, the maximum value of ∑k=11992∣yk−yk+1∣\sum_{k=1}^{1992}\left|y_{k}-y_{k+1}\right| is 1992.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.