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}$
- login om te reageren
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$