2014 IMO Problems/Problem 1

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} < 0$ from our inequality, and so $g(k) < 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.

Solution

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

Page

Toolbox

Search

2014 IMO Problems/Problem 1

Contents

Problem

Solution

See Also

Solution