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