nr 1 altijd doenbaar
Opgave - IMO 2007 dag 1 vraag 1
Gegeven zijn reele getallen $a_1,a_2,\cdots,a_n$. Definieer
$d_i=max\{a_j|1\le j \le i\}- min \{ a_j| i\le j \le n\}$ voor elke $i$ tussen $1$ en $n$ en laat $d=max\{d_i|1\le i \le n\}.$
(a) Bewijs dat voor alle getallen $x_1\le x_2 \le \cdots \le x_n \in \mathbb{R}$ geldt dat
$max \{ |x_i-a_i| | 1 \le i \le n \} \ge \frac{d}{2}$ $[1]$
(b) Bewijs dat er zo'n rij $(x_n)_n$ was zodat er gelijkheid geldde in $[1]$
- login om te reageren
Oplossing
(a)
Merk op dat $d=max\{a_i-a_j\mid 1\leq i\leq j\leq n \}$. Zij $s,t$ indices waarvoor $d=a_s-a_t$. We onderscheiden 2 gevallen:
Geval 1: $x_s\geq \frac{a_s+a_t}{2}$:
Uit $s\leq t$ volgt $x_s\leq x_t$ en dus $x_t\geq \frac{a_s+a_t}{2}$ waaruit $x_t-a_t\geq \frac{a_s-a_t}{2}=\frac{d}{2}$. We zijn klaar omdat $x_t-a_t\leq \mid x_t-a_t \mid \leq max\{\mid x_i-a_i\mid\mid1\leq i \leq n\}$
Geval 2: $x_s\leq \frac{a_s+a_t}{2}$:
We hebben ongelijkhedenketen $max\{\mid x_i-a_i\mid\mid1\leq i \leq n\}\geq \mid a_s-x_s\mid\geq a_s-x_s \geq a_s-\frac{a_s+a_t}{2}=\frac{d}{2}$
(b)
we construeren de rij $x_i$ volgens dit algoritme, bestaande uit 4 stappen:
1)Bekijk indices $s,t$ (met $s\le t$) waarvoor $d=a_s-a_t$. Bepaal nu de kleinste $r$ en de grootste $u$ zodat $1\leq r \leq s\leq t\leq u\leq n$ en $a_i\geq a_t$, $a_j\leq a_s$ voor alle $r\leq i < s$, $t< j \leq u$.
2)Kies $x_{i}=\frac{a_s+a_t}{2}$ voor alle $i\in\{r,r+1,\dots,u-1,u\}$.
3)Verwijder nu alle $a_i$ voor $r\leq i\leq u$ van je verzameling van $n$ getallen.
4) - Als alle $x_i$ een waarde hebben toegekend gekregen, KLAAR.
- Zijn er nog enkele getallen over (en zijn er dus nog enkele $x_i$ zonder toegekende waarde), ga naar stap 1 en herhaal.
Merk op dat stappen 1-3 een waarde geven aan één of meerdere $x_i$ en dat stap 4 een controlestap vormt, die het algoritme doet stoppen wanneer we klaar zijn. We moeten nu twee dingen bewijzen, nl. dat het algoritme stopt, en dat het werkt.
Merk op dat $d\geq 0$, omdat $0=a_i-a_i\in\{a_i-a_j\mid 1\leq i\leq j\leq n \}$ en $d=max \{a_i-a_j\mid 1\leq i\leq j\leq n \}$. Omdat $a_s$ en $a_t$ telkens verwijderd worden bij stap 3 van het algoritme, zal het aantal elementen dus telkens met minimaal 1 (als $a_s=a_t$) afnemen. Omdat je begint met een eindig aantal elementen zal het algoritme dus ooit moeten stoppen.
$x_1\leq x_2\leq \dots \leq x_n$ volgt eigenlijk direct uit het feit dat iedere keer bij stap 1 er een minimale $r$ en maximale $u$ wordt gekozen: als $x_i\geq x_{i+1}$ voor een zekere $i$, dan moet er gelijkheid optreden daar voor een zekere herhaling van het algoritme anders $r$ niet minimaal was of $s$ maximaal.
tenslotte geldt dat $\mid x_i-a_i \mid\leq \frac{d}{2}$ voor alle $i$, waardoor er gelijkheid moet optreden bij (a):
We hebben immers voor alle $d$ die in het algoritme bepaald worden, dat die $d$ kleiner of gelijk is aan de originele $d$, voor een deelverzameling $S$ van $\{1,2, \dots n\}$ geldt uiteraard $max\{a_i-a_j\mid i\leq j, \text{ en }i,j\in S\}\leq max\{a_i-a_j\mid i\leq j\}$. Aangezien per constructie $\mid x_i-a_i\mid=\mid\frac{a_s+a_t}{2}-a_i\mid \le max( \mid\frac{a_s+a_t}{2}-a_t\mid, \mid\frac{a_s+a_t}{2}-a_s\mid )= \frac{d}{2}$ waarbij $d,s,t$ genomen zijn uit een willekeurige herhaling van het algoritme.
QED