# 2014 IMO Problems/Problem 1

## Problem

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

## Solution

Define $f(n) = a_0 + a_1 + \dots + a_n - n a_{n+1}$. (In particular, $f(0) = a_0.$) Notice that because $a_{n+2} \ge a_{n+1}$, we have $$a_0 + a_1 + \dots + a_n - n a_{n+1} > a_0 + a_1 + \dots + a_n + a_{n+1} - (n+1) a_{n+2}.$$ Thus, $f(n) > f(n+1)$; i.e., $f$ is monotonic decreasing. Therefore, because $f(0) > 0$, there exists a unique $N$ such that $f(N-1) > 0 \ge f(N)$. In other words, $$a_0 + a_1 + \dots + a_{N-1} - (N-1) a_N > 0$$ $$a_0 + a_1 + \dots + a_N - n a_{N+1} \le 0.$$ This rearranges to give $$a_N < \frac{a_0 + a_1 + \dots + a_N}{N} \le a_{N+1}.$$ Define $g(n) = a_0 + a_1 + \dots + a_n - n a_n$. Then because $a_{n+1} > a_n$, we have $$a_0 + a_1 + \dots + a_n - n a_n > a_0 + a_1 + \dots + a_n + a_{n+1} - (n+1) a_{n+1}.$$ Therefore, $g$ is also monotonic decreasing. Note that $g(N+1) = a_0 + a_1 + \dots + a_{N+1} - (N+1) a_{N+1} \le 0$ from our inequality, and so $g(k) \le 0$ for all $k > N$. Thus, the given inequality, which requires that $g(n) > 0$, cannot be satisfied for $n > N$, and so $N$ is the unique solution to this inequality.

--Suli 22:38, 7 February 2015 (EST)

## Alternative Solution

It is more convenient to work with differences $d_i=a_i-a_{i-1}$, $i\ge 1$. $d_i\ge 1$. Instead of using $a_i=a_0+d_1+\ldots+d_i$ the inequalities can be rewritten in terms of $d_i$ as $$0 < V_n \le nd_{n+1}$$ where $V_n=a_0-d_2-2d_3-3d_4-\ldots - (n-1)d_n$. $V_n$ is strictly monotonically decreasing. $V_1=a_0 >0$. That is the left inequality is satisfied for $n=1$. Lets take a look at the time step $(n+1)$ which is right after $n$: $n \rightarrow n+1$ $$0< V_n-nd_{n+1}\le (n+1)d_{n+2}$$ The condition $V_n \le nd_{n+1}$for breaking the left inequality at some step $n+1$ is exactly the condition for satisfying the right inequality at step $n$. Once left inequality is broken at step $(n+1)$ it will remain broken for future steps as $V_n$ is strictly decreasing. The right inequality will be satisfied for some $n$ as $V_n$ is strictly decreasing integer sequence and the right hand side $nd_{n+1}$ of the right inequality is bounded by $1$ from below. In summary, the left inequality is satisfied initially and as soon as the right inequality is satisfied, which will happen for some $n$, the left inequality will break at the very next step and will remain broken for all future steps. That is $n$ when both inequalities are satisfied exists and unique.

--alexander_skabelin 9:24, 7 July 2023 (EST)