XL OM - II - Zadanie 4

Dane są liczby całkowite $ a_1, a_2, \ldots , a_{11} $ . Udowodnić, że istnieje taki niezerowy ciąg $ x_1, x_2, \ldots, x_{11} $ o wyrazach ze zbioru $ \{-1,0,1\} $, że liczba $ x_1a_1 + \ldots x_{11}a_{11} $ jest podzielna przez 1989.

Rozwiązanie

Każdemu $ 11 $ - elementowemu ciągowi $ (u_1,\ldots ,u_{11}) $ o wyrazach równych $ 0 $ lub $ 1 $ przyporządkujmy liczbę $ u_1a_1 + \ldots +u_{11}a_{11} $ . Wszystkich takich ciągów jest $ 2^{11} $, a zatem więcej niż $ 1989 $. Istnieje wobec tego taka para ciągów $ (u_1,\ldots, u_{11}) \neq (v_1, \ldots, v_n) $, $ u_i, v_i \in \{0,1\} $ , że przyporządkowane tym ciągom liczby

\[<br />
u_1a_1 + \ldots + u_{11}a_{11} \quad   \textrm{oraz} \quad      v_1a_1 + \ldots + v_{11}a_{11}<br />
\]

dadzą przy dzieleniu przez $ 1989 $ jednakowe reszty. A to znaczy, że liczba

\[<br />
(u_1 - v_1)a_1 + \ldots + (u_{11} - v_{11})a_11<br />
\]

jest podzielna przez $ 1989 $.

Wystarczy więc przyjąć $ x_i = u_i -v_i $ dla $ i = 1,\ldots , 11 $. Wyrazy ciągu $ (x_1, \ldots, x_{11}) $ są równe $ 0 $, $ 1 $ lub $ -1 $, przy czym nie wszystkie są zerami.

Komentarze

Dodaj nową odpowiedź