XL OM - II - Zadanie 4

Zawody matematyczne:

XL OM, 1988-1989

Etap:

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.