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.

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.

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.

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.

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

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestLet'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.

Log in to reply

Beautiful solution

Log in to reply

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

Log in to reply

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.

Log in to reply

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

Log in to reply

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.

Log in to reply

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.

Log in to reply

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

Log in to reply