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+a_2+\cdots+a_n}{n} \leq a_{n+1}.\]
Proposed by Gerhard Wöginger, Austria.
IMO 2014 - Day 1 Problem 1
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: IMO 2014 - Day 1 Problem 1
Rewrite as
\[na_n -\sum_{k=1}^n a_k<a_0\le na_{n+1}-\sum_{k=1}^n a_k.\]
Notice that
\[na_n -\sum_{k=1}^n a_k < (n+1)a_{n+1}-\sum_{k=1}^{n+1} a_k~~~\Longleftrightarrow ~~~na_n < na_{n+1} ~~~\Longleftrightarrow~~~ a_n < a_{n+1}\] which is true. So monotonicity holds on the left and right expressions. Hence our desired \(n\) is \[\max\left\{n: na_n -\sum_{k=1}^n a_k<a_0\right\}\] which satisfies our conditions and clearly is unique. Such an \(n\) exists because \(a_0\) is constant.
\[na_n -\sum_{k=1}^n a_k<a_0\le na_{n+1}-\sum_{k=1}^n a_k.\]
Notice that
\[na_n -\sum_{k=1}^n a_k < (n+1)a_{n+1}-\sum_{k=1}^{n+1} a_k~~~\Longleftrightarrow ~~~na_n < na_{n+1} ~~~\Longleftrightarrow~~~ a_n < a_{n+1}\] which is true. So monotonicity holds on the left and right expressions. Hence our desired \(n\) is \[\max\left\{n: na_n -\sum_{k=1}^n a_k<a_0\right\}\] which satisfies our conditions and clearly is unique. Such an \(n\) exists because \(a_0\) is constant.
- What is the value of the contour integral around Western Europe?
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- Fatin Farhan
- Posts:75
- Joined:Sun Mar 17, 2013 5:19 pm
- Location:Kushtia,Bangladesh.
- Contact:
Re: IMO 2014 - Day 1 Problem 1
$$a_n < \dfrac{a_0+a_1+a_2+\cdots+a_n}{n} \leq a_{n+1}$$
$$na_n < a_0+a_1+a_2+\cdots+a_n \leq na_{n+1}.$$
For uniqueness:
Let $$n={n_1,n_2,....n_k}$$ satisfies $$a_0+a_1+a_2+\cdots+a_n \leq na_{n+1}$$ where $$n_1<n_2<\cdots<n_k$$.
Let $$n_1+m_i=n_i$$ $$ $$
Now,
$$\sum_{k=0}^n a_k\leq n_1a_{n+1}$$.
$$\Rightarrow \sum_{k=0}^{n+1} a_k \leq (n+1)a_{n+1}$$
$$\Rightarrow \sum_{k=0}^{n+1} a_k \leq (n+1)a_{n+1}<(n+1)a_{n+2}$$
$$\Rightarrow \sum_{k=0}^{n+2} a_k<(n+2)a_{n+2}$$.
$$\cdots$$ $$\cdots$$ $$\cdots$$
$$\Rightarrow \sum_{k=0}^{n+i} a_k <(n+i)a_{n+i}$$.
$$\therefore n$$ is unique .
For existence:
Assuming that $$n$$ does not exist,
$$\therefore a_n \nless \dfrac{\sum_{k=0}^n a_k}{n} \nleq a_{n+1}$$
$$\Rightarrow a_1 \nless a_0+ a_1 \nleq a_{2}$$
But $$a_1<a_0+a_1$$.
$$\therefore a_0+a_1>a_2 $$,
$$\Rightarrow a_0+a_1+a_2>2a_2$$
Again,
$$ 2a_2 \nless a_0+a_1+a_2 \nleq 2a_3$$
$$\Rightarrow 2a_3<a_0+a_1+a_2 \leq a_0+a_1+a_0+a_1=2(a_0+a_1) $$.
$$\Rightarrow a_3<a_0+a_1$$.
Repeating the process $$a_i<a_0+a_1$$ For every $$i=2,3, \cdots$$
But $$a_0<a_1<a_2 \ldots$$ is an infinite sequence of positive integers, there will be a very large $$a_k$$ such that $$a_0+a_1 \leq a_k$$.
So there is a contradiction.
$$\therefore \text{ there exists a }n$$ .
$$na_n < a_0+a_1+a_2+\cdots+a_n \leq na_{n+1}.$$
For uniqueness:
Let $$n={n_1,n_2,....n_k}$$ satisfies $$a_0+a_1+a_2+\cdots+a_n \leq na_{n+1}$$ where $$n_1<n_2<\cdots<n_k$$.
Let $$n_1+m_i=n_i$$ $$ $$
Now,
$$\sum_{k=0}^n a_k\leq n_1a_{n+1}$$.
$$\Rightarrow \sum_{k=0}^{n+1} a_k \leq (n+1)a_{n+1}$$
$$\Rightarrow \sum_{k=0}^{n+1} a_k \leq (n+1)a_{n+1}<(n+1)a_{n+2}$$
$$\Rightarrow \sum_{k=0}^{n+2} a_k<(n+2)a_{n+2}$$.
$$\cdots$$ $$\cdots$$ $$\cdots$$
$$\Rightarrow \sum_{k=0}^{n+i} a_k <(n+i)a_{n+i}$$.
$$\therefore n$$ is unique .
For existence:
Assuming that $$n$$ does not exist,
$$\therefore a_n \nless \dfrac{\sum_{k=0}^n a_k}{n} \nleq a_{n+1}$$
$$\Rightarrow a_1 \nless a_0+ a_1 \nleq a_{2}$$
But $$a_1<a_0+a_1$$.
$$\therefore a_0+a_1>a_2 $$,
$$\Rightarrow a_0+a_1+a_2>2a_2$$
Again,
$$ 2a_2 \nless a_0+a_1+a_2 \nleq 2a_3$$
$$\Rightarrow 2a_3<a_0+a_1+a_2 \leq a_0+a_1+a_0+a_1=2(a_0+a_1) $$.
$$\Rightarrow a_3<a_0+a_1$$.
Repeating the process $$a_i<a_0+a_1$$ For every $$i=2,3, \cdots$$
But $$a_0<a_1<a_2 \ldots$$ is an infinite sequence of positive integers, there will be a very large $$a_k$$ such that $$a_0+a_1 \leq a_k$$.
So there is a contradiction.
$$\therefore \text{ there exists a }n$$ .
"The box said 'Requires Windows XP or better'. So I installed L$$i$$nux...:p"