soal olimpiade

Day 1 (July 8th, 2014)

Problem 1

Let $a_0< a_1< a_2< \cdots$ be an infinite sequence of positive integers. Prove that there exists a unique integer $n\geq 1$ such that $$a_n< \frac{a_0+a_1+\cdots+a_n}n\leq a_{n+1}.$$

For $k\geq 1$ we will say that the term $a_k$ is large if $a_k\geq \frac{a_0+a_1+\cdots+a_k}k$. Notice that the last inequality is equivalent to $a_k\geq \frac{a_0+a_1+\cdots+a_{k-1}}{k-1}$ for $k\geq 2$. If $a_k$ is not large we say that it is small. We need to prove that there exists a unique $n\geq 1$ such that $a_n$ is small and $a_{n+1}$ is large. Since $a_0> 0$ we have that $a_1$ is small. We will first prove that there is an integer $n$ such that $a_n$ is large. Assume the contrary, that $a_k$ is small for all $k\geq 1$. Then for $k\geq 2$ we have $$\begin{eqnarray*}a_k&<&\frac1{k-1}\left(a_0+a_1+\cdots+a_{k-1}\right)\\&<& \frac1{k-1}\left(a_0+a_1+\cdots+a_{k-2}+\frac1{k-2}\left(a_0+a_1+\cdots+a_{k-2}\right)\right)\\ &=&\frac1{k-2}\left(a_0+a_1+\cdots+a_{k-2}\right). \end{eqnarray*}$$ Continuing in the same way we obtain $$a_k< \frac1{k-2}\left(a_0+a_1+\cdots+a_{k-3}\right)< \cdots< \frac13\left(a_0+a_1+a_2+a_3\right),$$ which means that $a_k$ is a bounded sequence. This contradiction proves that there is at least one $n$ for which $a_n$ is large. Let us assume that there are two positive integers $n$ and $m$ such that $1\leq n< m$ for which the given two inequalities are satisfied. Then we have $$\begin{eqnarray*} a_m&<& \frac{\left(a_0+\cdots+a_n\right)+\left(a_{n+1}+\cdots+a_m\right)}{m}\leq \frac{na_{n+1}+\left(a_{n+1}+\cdots+a_m\right)}{m}\\ &<& \frac{na_{m}+\left(a_{m}+\cdots+a_m\right)}{m}=a_m. \end{eqnarray*}$$ This completes the proof of the required statement.

Tweet