L OM - III - Zadanie 2

Zawody matematyczne:

L OM, 1998-1999

Etap:

III

Dane są liczby całkowite nieujemne $a_1 <a_2 <a_3 < \ldots < a_{101}$ mniejsze od $5050$ . Dowieść, że spośród nich można wybrać takie cztery różne $a_k$ , $a_l$ , $a_m$ , $a_n$ , że liczba $a_k + a_l -a_m -a_n$ jest podzielna przez $5050$ .

Rozwiązanie

Rozważamy wszystkie wyrażenia postaci $a_k + a_l$ , gdzie $1 \leq k<l \leq 101$ . Takich wyrażeń jest ${101 \choose 2}= 5050$ . Jeżeli znajdziemy wśród nich dwa, powiedzmy $a_k + a_l$ i $a_m + a_n$ , których wartości dają tę samą resztę z dzielenia przez 5050, to liczby $a_k$ , $a_l$ , $a_m$ , $a_n$ spełniają warunki zadania — liczby te są bowiem parami różne (jeśli np. $a_k = a_m$ , to także $a_l = a_n$ , gdyż $0 \leq a_l,a_n < 5050$ ).

Pozostaje do rozpatrzenia przypadek, w którym wszystkie powyższe sumy dają różne reszty z dzielenia przez $5050$ . Wykażemy, ze ten przypadek zachodzić nie może. Gdyby bowiem tak było, to rozważane sumy dawałyby wszystkie możliwe reszty z dzielenia przez $5050$ — każdą jeden raz. Stąd

$<br /> S=\sum_{1\leq k <l \leq 101}(a_k+a_l)\equiv \sum_{i=0}^{5049}i = \frac{5049\cdot 5050}{2} \equiv 2525\ (\mathrm{mod}\ 5050),<br />$

co dowodzi, że $S$ jest liczbą nieparzystą.

Z drugiej strony

$<br /> S=\sum_{1\leq k < l\leq 101}(a_k+a_l) = 100 \cdot \sum_{k=1}^{101} a_k,<br />$

co oznacza, że $S$ jest liczbą parzystą. Otrzymaliśmy sprzeczność.