Maths Olympiad Prep

Library / IMO Shortlist /22 of 365

IMO Shortlist

Algebra Difficulty 7.6 National Olympiad, round 2 Prove it IMO

Let z0<z1<z2<⋯z_{0} < z_{1} < z_{2} < \cdots be an infinite sequence of positive integers. Prove that there exists a unique integer n⩾1n \geqslant 1 such that
zn<z0+z1+⋯+znn⩽zn+1. z_{n} < \frac{z_{0} + z_{1} + \cdots + z_{n}}{n} \leqslant z_{n+1} .

Solution

For n=1,2,…n = 1, 2, \ldots define
dn=(z0+z1+⋯+zn)−nzn d_{n} = \left(z_{0} + z_{1} + \cdots + z_{n}\right) - n z_{n}
The sign of dnd_{n} indicates whether the first inequality in (1) holds; i.e., it is satisfied if and only if dn>0d_{n} > 0.
Notice that
nzn+1−(z0+z1+⋯+zn)=(n+1)zn+1−(z0+z1+⋯+zn+zn+1)=−dn+1, n z_{n+1} - \left(z_{0} + z_{1} + \cdots + z_{n}\right) = (n+1) z_{n+1} - \left(z_{0} + z_{1} + \cdots + z_{n} + z_{n+1}\right) = -d_{n+1},
so the second inequality in (1) is equivalent to dn+1⩽0d_{n+1} \leqslant 0. Therefore, we have to prove that there is a unique index n⩾1n \geqslant 1 that satisfies dn>0⩾dn+1d_{n} > 0 \geqslant d_{n+1}.
By its definition the sequence d1,d2,…d_{1}, d_{2}, \ldots consists of integers and we have
d1=(z0+z1)−1⋅z1=z0>0. d_{1} = \left(z_{0} + z_{1}\right) - 1 \cdot z_{1} = z_{0} > 0 .
From
dn+1−dn=((z0+⋯+zn+zn+1)−(n+1)zn+1)−((z0+⋯+zn)−nzn)=n(zn−zn+1)<0d_{n+1} - d_{n} = \left(\left(z_{0} + \cdots + z_{n} + z_{n+1}\right) - (n+1) z_{n+1}\right) - \left(\left(z_{0} + \cdots + z_{n}\right) - n z_{n}\right) = n\left(z_{n} - z_{n+1}\right) < 0
we can see that dn+1<dnd_{n+1} < d_{n} and thus the sequence strictly decreases.
Hence, we have a decreasing sequence d1>d2>…d_{1} > d_{2} > \ldots of integers such that its first element d1d_{1} is positive. The sequence must drop below 0 at some point, and thus there is a unique index nn, that is the index of the last positive term, satisfying dn>0⩾dn+1d_{n} > 0 \geqslant d_{n+1}.

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

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