XXX OM - III - Zadanie 1

Zawody matematyczne:

XXX OM, 1978-1979

Etap:

III

Dany jest zbiór $\{r_1, r_2, \ldots, r_k\}$ liczb naturalnych, które przy dzieleniu przez liczbę naturalną $m$ dają różne reszty. Udowodnić, że jeżeli $k > \frac{m}{2}$ , to dla każdej liczby całkowitej $n$ istnieją takie $i$ oraz $j$ ( $n$ niekoniecznie różne), że liczba $r_i + r_j - n$ jest podzielna przez $m$ .

Rozwiązanie

Zbiór $A$ reszt, jakie dają przy dzieleniu przez $m$ liczby $n-r_1, n-r_2, \ldots, n-r_k$ , zawiera więcej niż $\displaystyle \frac{m}{2}$ elementów. Również zbiór $B$ reszt, jakie dają przy dzieleniu przez $m$ liczby $r_1, r_2, \ldots, r_k$ , zawiera więcej niż $\displaystyle \frac{m}{2}$ elementów. Zbiory $A$ i $B$ są zawarte w zbiorze $m$ -elementowym wszystkich reszt, jakie dają przy dzieleniu przez $m$ liczby całkowite.

Wobec tego zbiory $A$ i $B$ nie są rozłączne, to znaczy dla pewnych $i$ oraz $j$ liczba $r_i$ daje tę samą resztę przy dzieleniu przez $m$ , co liczba $n-r_j$ . Różnica tych liczb, równa $r_i + r_j - n$ , jest więc podzielna przez $m$ .