Komentarz

L OM - III - Zadanie 2

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ść.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz