IMO 2014 problem 1

This is an exercise proposed by Timothy Gowers: Write down all you think of while trying to solve a math problem.

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

Brain dump. First, it's curious that the sum of $n+1$ numbers is divided by $n$, instead of $n+1$. Second, the fact that the sequence is strictly increasing is clearly important. These two seem to indicate that I might want to look at differences: (1) there are $n$ differences between $n+1$ numbers, and (2) these differences are positive. So, let's set $b_n=a_{n+1}-a_n$. Then $a_0+\cdots+a_n$ is $b_0+\cdots+b_{n-1}$ (just $n$ numbers!).

Hmm $\ldots$ I need some way to express the $a_n\lt\cdots\lt a_{n+1}$ part of the inequality. It seems convenient to set $a_{-1}=0$ and change the definition of $b_n$ to $a_n-a_{n-1}$. Then the initial inequality is $\ldots$

(Oh, dear: I just noticed that I made a terrible mistake earlier. The sum $a_0+\cdots+a_n$ is not what I said. Anyway, now I changed the definition of $b_n$, so let's see what is it supposed to be using the new definition.)

$\ldots$ so, the initial inequality is $$b_0+\cdots+b_n \le \frac{(n+1)b_0+nb_1+(n-1)b_2+\cdots+b_n}{n} \le b_0+\cdots+b_{n+1}$$ This one can be rearranged as $$0 \le (n+1)b_0+nb_1+\cdots+b_n \le nb_{n+1}$$ OK, it looks like the left part always hold. I need to compile this and look at the equations to check if they're OK $\ldots$ Seems fine.

Right. On to the second part of the inequality. We have two parts here. First, to show that the inequality eventually holds, as $n$ increases. Second, to show that once it holds, it cannot hold for bigger $n$. Let's unpack the inequality for a few small values of $n$: $$\begin{align} b_0 &\le 0 \\ 2b_0 + b_1 &\le b_2 \\ 3b_0 + 2b_1 + b_2 &\le 2b_3 \\ 4b_0 + 3b_1 + 2b_2 + b_3 &\le 3b_4 \end{align}$$ The first inequality can't be true because $b$s are positive. The second could be so let's suppose it is. How does this imply that the third inequality doesn't hold?

(OK. I'm just terrible. Earlier I said I need to check some inequalities, said I did, and all is well. They are wrong! They are so wrong. I'm very tempted to find excuses and blame my family who keeps interrupting, asking questions about the history of the coffee machine, whether I really want to sit on the floor instead of going to the table, and whatnot.)

Anyway, for the third time $\ldots$ the initial inequality, expressed in terms of $b$s, is: $$0\le b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n) \le nb_{n+1}$$ The left part does not always hold. In fact, it's clear that it holds in the beginning ($0\le b_0$) but will eventually fail, because its right side keeps decreasing. So, let's look at what happens at that step. That is, we pick $n$ such that $$0\le b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n)$$ and $$0 \gt b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n + nb_{n+1})$$ Or, rewritten $$(b_2+2b_3+\cdots+(n-1)b_n) \le b_0 \le (b_2+2b_3+\cdots+nb_{n+1})$$ The first question is what happens with the other inequality at this $n$. The second question is what happens in general with the other inequality, not only at this $n$. Actually, part of the second question is very easy to answer: for bigger $n$ the right inequality holds, because the middle term is negative, while the right one is positive. For $n$ itself, the right inequality still holds: just add $nb_{n+1}$ to both sides of $0>b_0-(\ldots)$.

All that is left to do at this point is to show that for smaller $n$ than the picked one, the right inequality fails.

(I should say that at this point I feel close to the answer, and I let myself be distracted by what people talk around me. Now that I think about it, I may not be close to the answer. What I did so far feels rather easy, so the perhaps all I did was to reach the hard part. Let's continue.)

What happens at $n-1$? $$0\le b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-2)b_{n-1}) \le (n-1)b_n$$ Subtract $(n-1)b_n$: $$-(n-1)b_n \lt 0\le b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n) \le 0$$ This is not immediately a contradiction, although it would've been if I would've looked at $n-2$ instead of $n-1$. I'm a bit confused as to why this doesn't seem like a contradiction, so let's look at an example. I pick $b$s to be $3, 1, 1, 1, \ldots.$ Then $$\begin{align} &b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n) &&\text{is} &&3,2,0,-3,-7,\ldots \\ &nb_{n+1} &&\text{is} && 0,2,2,\phantom{-}2,\phantom{-}2,\ldots \end{align}$$ It looks like indeed there are two $n$s such that both inequalities hold. What mistake did I do? Let me check in terms of the original statement. $$\begin{align} &n &&0 &&1 &&2 &&3 &&4 \\ &a_n &&3 &&4 &&5 &&6 &&7 \\ &\sum_{k\le n} a_k &&3 &&7 &&12 &&18 &&25 \\ &\sum/n && &&7 &&6 &&6 &&6.25 \end{align}$$ I'm confused: It seems both $n=2$ and $n=3$ work. I will now go and brush my teeth.

Update: My mistake was in the copying of the problem statement. This was revealed in comments back at the original post.