2014 IMO Problems/Problem 1

Revision as of 23:43, 7 February 2015 by Suli (talk | contribs) (Solution)

Problem

Let $a_0<a_1<a_2<\cdots \quad$ 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)

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

2014 IMO (Problems) • Resources
Preceded by
First Problem
1 2 3 4 5 6 Followed by
Problem 2
All IMO Problems and Solutions

Solution