Maths Olympiad Prep

Library / /22 of 383

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 n1n \geqslant 1 such that
zn<z0+z1++znnzn+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+10d_{n+1} \leqslant 0. Therefore, we have to prove that there is a unique index n1n \geqslant 1 that satisfies dn>0dn+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)1z1=z0>0. d_{1} = \left(z_{0} + z_{1}\right) - 1 \cdot z_{1} = z_{0} > 0 .
From
dn+1dn=((z0++zn+zn+1)(n+1)zn+1)((z0++zn)nzn)=n(znzn+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>0dn+1d_{n} > 0 \geqslant d_{n+1}.

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.