×

# IMO 2014/1

Let $$a_0 < a_1 < a_2 \ldots$$ 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 + \ldots + a_n } { n} \leq a_{n+1} .$

Note by Calvin Lin
3 years, 6 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Let's call $$S_k = a_0 + a_1 + ... + a_k$$ and suppose $\frac { { S }_{ k } }{ k } >{ a }_{ k+1 } \; \forall m \leq k$ Then we have $k\cdot { S }_{ k }+{ S }_{ k }>k\cdot { a }_{ k+1 }+k\cdot{ S }_{ k }\quad \Leftrightarrow \quad \frac { { S }_{ k } }{ k } >\frac { { S }_{ k+1 } }{ k+1 }\\ \quad \Leftrightarrow \quad \frac { { S }_{ k+1 } }{ k+1 } <\frac { { S }_{ k } }{ k } <\frac { { S }_{ k-1 } }{ k-1 } <...<{ S }_{ 1 }={ a }_{ 0 }+{ a }_{ 1 }$ Hence, we prove by induction $2(a_{ 0 }+{ a }_{ 1 })>{ a }_{ 0 }+{ a }_{ 1 }+{ a }_{ 2 }\quad \Leftrightarrow \quad { a }_{ 0 }+{ a }_{ 1 }>{ a }_{ 2 }\\ k{ a }_{ k+1 }<{ S }_{ k }<k(a_{ 0 }+{ a }_{ 1 })\quad \Leftrightarrow \quad { a }_{ k+1 }<(a_{ 0 }+{ a }_{ 1 })$ Because $$a_{ 0 }+{ a }_{ 1 }$$ is a sum of integer number, there must be a unique number in the sequence for which $$a_{q+1} \geq a_{ 0 }+{ a }_{ 1 }$$ and $$a_{q} < a_{ 0 }+{ a }_{ 1 }$$. We now show that $$q$$ is the required number. We have alredy proved that $\frac { { S }_{ q } }{q } \leq { a }_{ q+1 }$ by contraddiction! Thus we have only to show that ${ a }_{ q }<\frac { S_{ q } }{ q } \quad \Leftrightarrow \quad q{ \cdot a }_{ q }-a_{ q }<S_{ q }-a_{ q }\quad \Leftrightarrow \quad { a }_{ q }<\frac { S_{ q-1 } }{ q-1 }$ And because $S_{ q-1 }(q-1)+{ a }_{ q }(q-1)<S_{ q-1 }+S_{ q-1 }(q-1)\quad \Leftrightarrow \quad \frac { S_{ q } }{ q } <\frac { S_{ q-1 } }{ q-1 }\\ \quad \Leftrightarrow \quad \frac { S_{ q } }{ q } <\frac { S_{ q-1 } }{ q-1 } <\frac { S_{ q-2 } }{ q-2 } <...<S_{ 1 }={ a }_{ 0 }+{ a }_{ 1 }$ Excactly as done beofre we must have $$a_q < a_0 + a_1$$. That is true. And we are done.

- 3 years, 6 months ago

Beautiful solution

- 7 months, 1 week ago

Question 1 was way easier than I expected it to be. Bummed that there were no proper number theory problems.

- 3 years, 6 months ago

In recent years, they have made question 1 (and sometimes 4) pretty easy and direct to approach, so that all of the participants (who come from a wide range of ability level) have something to do, and have a chance of geting a HM.

Staff - 3 years, 6 months ago

This was indeed very nice, but also pretty easy, even for an IMO P1. I have posted my solution in AoPS.

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=3542324&#p3542324

- 3 years, 6 months ago

Here's a conjecture:

The last possible $$n$$ that satisfies $$a_n < \dfrac{a_0+a_1+\cdots +a_n}{n}$$ also satisfies $$\dfrac{a_0+a_1+\cdots +a_n}{n}\le a_{n+1}$$. This is just a guess though.

These later posts will be what I have came up with.

- 3 years, 6 months ago

Update: letting $$a_0=x$$ and $$a_1=y$$, we find that in order for $$a_k < \dfrac{a_0+a_1+\cdots +a_k}{k}$$, we must have $$a_k < x+y$$. However, since $$x+y$$ is finite, and the sequence is strictly increasing, we must have that there is a maximum $$k$$ that satisfies this condition.

So let $$k$$ be the maximum such that it still satisfies the condition. Thus, $$a_{k+1} \ge x+y$$. However, $$\dfrac{a_0+a_1+\cdots +a_k}{k} < \dfrac{x+y+(x+y)+\cdots +(x+y)}{k}=x+y$$. Thus, $$\dfrac{a_0+a_1+\cdots +a_k}{k} < a_{k+1}$$.

This seems really sketchy though. Something seems wrong... one of my inequalities was strict when forming the right inequality, but the inequality in the problem is not strict...

EDIT: found out why mine was strict and the problem's wasn't. As long as the maximum $$k$$ satisfies $$k\ge 2$$, then the upper bound inequality is strict, just like my result. However, the special case of the maximum $$k$$ is $$k=1$$ yields a non-strict inequality.

TO DO: prove uniqueness of satisfying both inequalities.

- 3 years, 6 months ago

I realize that I have to tighten the bound for each $$a_k < x+y$$ to something more strict, or something like that in order to prove the uniqueness of that one $$k$$ that satisfies both inequalities. I feel like I'm almost there, but just can't get over the last little bump. I need to somehow use the $$a_k < a_{k+1}$$ to my advantage...

- 3 years, 6 months ago