algebra 2 keer

Opgave - IMO 2015 dag 2 vraag 3

De rij gehele getallen $a_1,a_2,\dots$ voldoet aan volgende voorwaarden:

(i) $1\le a_j\le2015$ voor alle $j\ge1$,
(ii) $k+a_k\neq \ell+a_\ell$ voor alle $1\le k<\ell$.

Bewijs dat er twee natuurlijke getallen $b$ en $N$ bestaan waarvoor geldt dat

\[\left\vert\sum_{j=m+1}^n(a_j-b)\right\vert\le1007^2\]

voor alle $m$ en $n$ zodat $n>m\ge N$.

Oplossing

Opmerking: wanneer ik het in dit bewijs heb over elementen uit een interval, bedoel ik altijd natuurlijke.

Definieer $b_n=a_n+n$.

We bewijzen eerst volgend lemma:

Lemma 1: $(b_n)_n$ bevat alle natuurlijke getallen behalve ten hoogste $2016$.

Bewijs: uit (i) en de definitie van $(b_n)_n$ volgt dat $n+1 \leq b_n \leq 2015+n$, en uit (ii) volgt dat geen twee elementen uit $(b_n)_n$ gelijk zijn. Omdat $\{b_1,b_2, \ldots ,b_n\}$ $n$ verschillende natuurlijke getallen zijn in het interval $[2,2015+n]$, kunnen er ten hoogste $2015+n+1-n=2016$ getallen uit $[0,2015+n]$ ontbreken in $(b_i)_i$ en dit voor elke $n \in \mathbb N$, waaruit Lemma 1 volgt.

We definiëren nu $b$ als het aantal ontbrekende strikt positieve natuurlijke getallen in de rij $(b_n)_n$. Dus $1 \leq b \leq 2015$. Zij nu $N$ om het even welk natuurlijk getal groter dan het grootste ontbrekende getal uit de rij.

Beschouw $b_{m+1},b_{m+2},...,b_n$. Elk getal in deze rij moet uit het interval $[m+2;n+2015]$ komen. Omwille van de keuze van $N$ moet elk van deze getallen ook minstens éénmaal in $(b_n)_n$ komen. We bewijzen nu volgend lemma:

Lemma 2: $b$ elementen uit $[m+1,n+2015]$ zitten in $b_1,b_2,...,b_m$.
Equivalent, $b-1$ elementen uit $[m+2,n+2015]$ zitten in $b_1,b_2,...,b_m$.

Bewijs:
Er zijn per definitie $b$ getallen in $[1,m]$ die niet in $b_1,b_2,...,b_m$ voorkomen, daar $m \ge N$.
Dit betekent dat er $m-b$ getallen in $[1,m]$ zitten en de overige $b$ zitten in $[m+1,m+2015] \subset [m+1,n+2015].$

Omdat er $2015$ getallen uit $[m+1,n+2015]$ ontbreken in $b_{m+1},b_{m+2},...,b_n$, moeten er ook nog $2015-b$ getallen in $b_{n+1},b_{n+2},...$ komen. Deze zullen in het interval $[n+2,n+2015]$ liggen.

Hieruit en uit Lemma $2$ (equivalente vorm) volgt dat $\sum^{n+2015}_{j=m+2}{j}-\sum_{j=m+2017-b}^{m+2015}{j} -\sum^{n+2015}_{j=n+b+1}{j}\leq \sum_{j=m+1}^n {b_j} \leq \sum^{n+2015}_{j=m+2}{j}-\sum_{j=m+2}^{m+b}{j}-\sum^{n+2016-b}_{j=n+2}{j}$

Nu kunnen we een boven-en ondergrens voor $\sum_{j=m+1}^n (a_j-b)$ vinden. Er geldt namelijk: $\sum_{j=m+1}^n (a_j-b)=\sum^{n}_{j=m+1}(b_j-j-b)$
$ \leq \sum^{n+2015}_{j=m+2}{j}-\sum_{j=m+2}^{m+b}{j}-\sum^{n+2016-b}_{j=n+2}{j}-\sum^{n}_{j=m+1}{j}-(n-m)b$
$= \sum^{n+2015}_{j=m+b+1}{j}-\sum^{n+2016-b}_{j=m+1}{j}+(n+1)-(n-m)b$
$=(n-m+2015-b)b-(n+2016-b)+n+1-(n-m)b$
$=(2015-b)(b-1)$
$\leq 1007^2$ (wegens AM-GM)

en als ondergrens: $\sum_{j=m+1}^n (a_j-b)=\sum^{n}_{j=m+1}(b_j-j-b)$
$\geq \sum^{n+2015}_{j=m+2}{j}-\sum_{j=m+2017-b}^{m+2015}{j} -\sum^{n+2015}_{j=n+b+1}{j}-\sum^{n}_{j=m+1}{j}-(n-m)b$
$=\sum^{m+b}_{j=m+2}{j}+\sum^{n+b}_{j=m+b+1}{j}-\sum^{n}_{j=m+1}{j}-(n-m)b-\sum_{j=m+2017-b}^{m+2015}{j}$
$=(b-1)(b-2015)+\sum^{n+b}_{j=m+b+1}{j}-\sum^{n}_{j=m+1}{j}-(n-m)b$
$=(b-1)(b-2015)+(n-m)b-(n-m)b$
$=(b-1)(b-2015)$
$\geq -1007^2$

zodat $-1007^2 \leq \sum_{j=m+1}^n (a_j-b) \leq 1007^2 \Leftrightarrow \left | \sum_{j=m+1}^n (a_j-b) \right | \leq 1007^2$. Q.E.D.