de oneliner van 2014

Opgave - IMO 2014 dag 1 vraag 1

Zij $a_0 < a_1 < a_2 < \dots $ een oneindige rij van (strikt) positieve gehele getallen. Bewijs dat er een uniek geheel getal $n \geq 1$ bestaat zodat
$a_n<\frac1n(a_0+a_1+\dots+a_n)\leq a_{n+1}$

Oplossing

Eerst bewijzen we dat er zo'n $n$ bestaat:

Stel nu dat er geen zo'n $n$ bestaat.
Merk eerst op dat $a_1 < a_0+a_1$ en laat $a_2 < a_0+a_1$ omdat we anders klaar zijn.

Stel nu dat voor alle $i$ geldt dat $a_i < a_{i+1}<\frac{a_0+a_1+...+a_i}{i}$ en er dus geen zo'n $n$ bestaat en stel ook $a_0+a_1=x$.
Merk op dat $a_{i+1}<\frac{a_0+a_1+...+a_i}{i}$ betekent dat ook $$a_{i+1}<\frac{i}{i+1}\frac{a_0+a_1+...+a_i}{i}+\frac{a_{i+1}}{i+1}$$ en dus zal terug moeten gelden dat $$a_{i+2}<\frac{i}{i+1}\frac{a_0+a_1+...+a_i}{i}+\frac{a_{i+1}}{i+1}$$ zal moeten gelden en die uitdrukking dus geldt voor iedere index.

LEMMA Voor alle $i$ geldt dat $a_i < x$:

Basis
Voor $i=1$:$a_2 < a_0+a_1=x$

Hypothese
Het geldt voor alle $i\leq k$:$a_{i+1} < x$

Stap
Dan geldt voor $i=k+1$:

$$a_{k+2} < \frac{a_0+a_1+...+a_{k+1}}{k+1}=\frac{x+a_2+...+a_{k+1}}{k+1} < \frac{x+x+...+x}{k+1}=x$$

$\blacksquare$

Maar als elke $a_i < x$ dan zouden er oneindig veel natuurlijke getallen kleiner zijn dan een eindig natuurlijk getal, wat absurd is.

Dus moet er minstens één $l$ bestaan waarvoor

$\frac{a_0+a_1+...+a_l}{l} < a_l < a_{l+1}$

Nemen we nu de kleinste $m$ waarvoor
$a_m<\frac{a_0+a_1+...+a_m}{m} $ en
$a_{m+1}\ge \frac{a_0+a_1+...+a_m+a_{m+1}}{m+1}\ge \frac{a_0+a_1+...+a_m}{m}$
dan voldoet deze waarde als oplossing voor het vraagstuk.

Voor de uniciteit:

We hebben een $n$ gevonden zodat $a_n < \frac{a_0+a_1+...+a_n}{n}\leq a_{n+1}$.

Dan geldt echter ook dat $\frac{a_0+a_1+...+a_{n+1}}{n+1}\leq a_{n+1}$ zodat de uitdrukking niet geldt voor $n+1$. We kunnen nu ook bewijzen met inductie dat als

$\frac{a_0+a_1+...+a_{n+1}}{n+1}\leq a_{n+1}$ dat dan ook $\frac{a_0+a_1+...+a_{b}}{b} < a_{b}$ voor alle $b > n+1$.

Basis
Het geldt voor $i=n+1$ : $\frac{a_0+a_1+...+a_{n+1}}{n+1}\leq a_{n+1}$.

Hypothese
Het geldt voor $i=k\geq n+1$ : $\frac{a_0+a_1+...+a_k}{k}\leq a_{k}$

Stap
Dan geldt dat $\frac{a_0+a_1+...+a_k}{k}\leq a_{k}$

$\Leftrightarrow a_0+a_1+...+a_k\leq k\cdot a_k$

$\Leftrightarrow a_0+a_1+...+a_{k+1}\leq k\cdot a_k+a_{k+1} < (k+1)a_{k+1}$

$\Leftrightarrow \frac{a_0+a_1+...+a_{k+1}}{k+1} < a_{k+1}$

Hiermee is de inductie compleet.

Startend met de kleinste $n$ waarvoor de uitdrukking geldde, weten we dus dat er geen grotere $n$ bestaat en ze bijgevolg uniek is.

$QED$