Szemeredi, Erdos-Turan, Ellenberg- Gijswijt like it
Opgave - BxMO 2015 vraag 4
Een rekenkundige rij is een verzameling van de vorm $\{a,a+d,\ldots,a+kd\}$, waarbij $a,d,k$ gehele getallen zijn met $a$ $\ge $$1$, $d$ $\ge $ $1$ en $k$ $\ge $ $2$. Een rekenkundige rij heeft dus minstens drie elementen en de opeenvolgende elementen hebben verschil d, dat we de stapgrootte van de rekenkundige rij noemen.
Zij $n$>$1$ een geheel getal. Voor elke partitie (opdeling) van de verzameling $\{1,2,\ldots,3n\}$ in rekenkundige rijen, bekijken we de som $S$ van de respectievelijke stapgroottes van deze rekenkundige rijen. Wat is de maximale waarde die S kan bereiken? (Een partitie van een verzameling A is een collectie disjuncte deelverzamelingen van A waarvan de vereniging (unie) A is.)
- login om te reageren
Oplossing
Zij $N$ het aantal rekenkundige rijen waarin we de verzameling verdelen, waarbij voor $1 \leq i \leq N$; $k_i$ het aantal elementen van de $i^{de}$ rekenkundige rij (RR) is, $l_i$ de stapgrootte van bijbehorende RR, $b_i$ het kleinste element en $a_i$ het grootste element van de RR.
Merk op dat $N \leq n$, aangezien het minimale aantal elementen per opdeling $3$ is ($k_i \geq 3$).
Merk nu het volgende op: uit $k_i \geq 3$ volgt dat $2S=2 \cdot \sum_{i=1}^{N} {l_i}\leq \sum_{i=1}^{N} {(k_i-1)l_i} = \sum_{i=1}^{N} {a_i} -\sum_{i=1}^{N} {b_i}.$
Merk op dat $\sum_{i=1}^{N} {a_i} \leq 3n +(3n-1)+(3n-2)+\ldots+(3n-N+1)=3nN- \frac {N^2-N}{2}$ en $- \sum_{i=1}^{N} {b_i}\leq -(1+2+3+...+N)=-\frac{N^2+N}{2}$, dus $\sum_{i=1}^{N} {a_i} -\sum_{i=1}^{N} {b_i} \leq 3nN-N^2.$
We merken tot slot op dat $3nN-N^2 \leq 2 n^2$, want
$2n^2 + N^2 \ge 3 \sqrt[3]{n^4N^2} \ge 3nN$ wegens AM-GM en $n \ge N$ respectievelijk.
Hieruit volgt dat $S \leq n^2$.
We tonen aan dat het mogelijk is om zo'n opdeling te maken met $S=n^2$. Bekijk de partitie van de verzameling in de deelverzamelingen $\left\{1,n+1,n+2 \right\};\left\{2; n+2,2n+2 \right\};...;\left\{n,2n,3n\right\}$. Dit zijn allen rekenkundige rijen met stapgrootte $n$, en er zijn er $n$ in totaal aangezien ze allen uit drie elementen bestaan. Hierbij is de som van de stapgroottes dus $n^2$.