Liczba dzieląca sumę elementów podzbiorów

[niunix98]

Cześć,

Mam proste zadanie:

Udowodnij, że wśród dowolnych pięciu liczb całkowitych można wybrać takie trzy, że ich suma jest podzielna przez trzy. Dowód:

Ukryta treść:    

Niech danymi liczbami będą liczby z ciągu \(\displaystyle{ (a_{1}, ..., a_{5})}\). Rozważmy ich reszty modulo 3 i dostańmy ciąg \(\displaystyle{ (b_{1}, ..., b_{5})}\). Są dwa przypadki:
\(\displaystyle{ \alpha}\)) Wśród liczb \(\displaystyle{ b_{i}}\) są trzy równe. Wtedy one są szukanymi liczbami.
\(\displaystyle{ \beta}\)) Żadne trzy nie są równe. Wtedy któraś z tych liczb będzie równa \(\displaystyle{ 1}\), inna \(\displaystyle{ 2}\) i jeszcze inna \(\displaystyle{ 0}\). Wtedy te liczby są szukanymi przez nas.

Zastanawiam się, czy jest metoda na uogólnienie tego zadania, to znaczy, wyznaczyć najmniejsze takie \(\displaystyle{ k}\), że dla dowolnych \(\displaystyle{ k}\) liczb całkowitych można wśród nich wybrać takie \(\displaystyle{ n}\), że ich suma jest podzielna przez \(\displaystyle{ m}\).

Zadanie wydaje się dość abstrakcyjne, ale chodzi mi o to, czy jest lepsze szacowanie na \(\displaystyle{ k}\) niż \(\displaystyle{ k \le (n-1)m + 1}\) w ogólnej sytuacji. Skąd to szacowanie?

Ukryta treść:    

Zauważmy, że wystarczy, żebyśmy mieli \(\displaystyle{ n}\) liczb, które dają taką samą resztę z dzielenia przez \(\displaystyle{ m}\). Wtedy to właśnie one będą szukanymi liczbami. Jest \(\displaystyle{ m}\) reszt z dzielenia przez \(\displaystyle{ m}\), więc abyśmy mieli pewność, że któraś reszta wystąpi \(\displaystyle{ n}\) razy, musimy wziąć \(\displaystyle{ (n-1)m + 1}\) liczb. Wtedy z zasady szufladkowej wynika, że któreś \(\displaystyle{ \lceil [(n-1)m + 1] : m \rceil = n}\) da tą samą resztę z dzielenia przez \(\displaystyle{ m}\). Z tego wynika, że najmniejszą liczbą spełniającą warunki będzie co najwyżej \(\displaystyle{ (n-1)m + 1}\).

Jednak szacowanie wskazywałoby, że dla \(\displaystyle{ m = 3}\) i \(\displaystyle{ n = 3}\), \(\displaystyle{ k = 3 \cdot 2 + 1 = 7}\), a jednak \(\displaystyle{ k = 5}\) wystarcza. Zauważmy też, że \(\displaystyle{ k = 4}\) nie działa, gdyż kontrprzykładem jest ciąg \(\displaystyle{ (1, 1, 2, 2)}\). Wybierając dowolne trzy liczby i sumując, możemy otrzymać liczbę \(\displaystyle{ 1 + 1 + 2 = 4 \equiv_{3} 1}\) lub \(\displaystyle{ 1 + 2 + 2 = 5 \equiv_{3} 2}\).