# 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
7 years ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

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 } 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 } And because $S_{ q-1 }(q-1)+{ a }_{ q }(q-1) Excactly as done beofre we must have $a_q < a_0 + a_1$. That is true. And we are done.

- 7 years ago

Beautiful solution

- 4 years, 1 month ago

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

- 7 years 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 - 7 years 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

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.

- 7 years 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.

- 7 years 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...

- 7 years ago