XXX OM - III - Zadanie 1

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 $.

Komentarze

Dodaj nową odpowiedź