Suma x elementów ... = n

[bagienny]

Witajcie!

Mam problem z jednym zadaniem z matematyki dyskretnej, mianowicie muszę zadanie jest takie, że wśród n liczb całkowitych istnieją takie, których suma jest podzielna przez n. Doszedłem już do momentu, w którym mam n reszt z dzielenia ze zbioru {1,2,...,n-1} i muszę teraz pokazać, że znajdziemy wśród nich takie, że ich suma jest wynosi x*n (bądź suma mod n = 0). Ale zaciąłem się i nie wiem jak to wykazać - podejrzewam użycie Dirichleta, ale nie bardzo wiem w jaki sposób...

Pozdrawiam.

[klaustrofob]

Skoro jest do wyboru jest n-1 liczb, a wybierasz n, to co najmniej jedna musi się powtórzyć. Zatem masz co najmniej dwie równe reszty.

[Piotr Rutkowski]

To o wiele za mało, badasz tutaj podzielność przez n sumy, a nie różnicy liczb

[klaustrofob]

taa... przeoczyłem. ale można chyba tak: rozważmy zbiór wszystkich sum \(\displaystyle{ \{a_1, a_1+a_2, a_1+a_2+a_3,\ldots\,a_1+\ldots+a_n\}}\). jest ich n, dają n reszt z dzielenia przez n. albo któraś reszta jest równa 0 i odpowiednia suma jest podzielna, albo dwie sumy dają tę samą resztę (bo wtedy reszt jest n-1). różnica tych sum znów jest sumą - od dłuższej sumy odejmiemy krótszą - która już jest podzielna przez n. dowód wymaga umowy, że pojedynczy element też jest sumą - np. gdyby różnica \(\displaystyle{ (a_1+\ldots+a_5)-(a_1+\ldots+a_4)=a_5}\) była podzielna przez n.

[bagienny]

OK, ale to jakie w końcu jest rozwiązanie - bo fakt faktem na pewno byłyby dwie liczby o takiej samej reszcie z dzielenia - tylko co dalej? Mamy bowiem pokazać, że są dwie liczby których _suma_ jest podzielna przez n. Jakieś pomysły?

[edit]Jakby ktoś się zastanawiał dlaczego w zbiorze reszt z dzielenia nie ma 0 - zapomniałem dodać, że pojedynczą liczbę traktujemy jako sumę, więc 0 automatycznie kończy zadanie.

[klaustrofob]

rozwiązanie podałem wyżej - analizowałeś je?

[bagienny]

rozwiązanie podałem wyżej - analizowałeś je?

Prawdę mówiąc nie bardzo je zrozumiałem - byłbyś tak zacnym człowiekiem i jakoś przystępnie wyjaśnił?

[klaustrofob]

rozważamy zbiór n sum \(\displaystyle{ \{a_1, a_1+a_2, a_1+a_2+a_3, \ldots, a_1+a_2+\ldots+a_n\}}\). albo któraś z sum jest podzielna przez n (być może jest to "suma" \(\displaystyle{ a_1}\)) i koniec, albo nie i wtedy mamy n liczb-sum, które dają co najwyżej n-1 reszt, a wobec tego pewne dwie sumy dają taką samą resztę. odejmując od "dłuższej" sumy "krótszą" otrzymujemy znów sumę (być może jednoelementową, gdyby trafiło na sumy \(\displaystyle{ a_1+\ldots+a_k}\) oraz \(\displaystyle{ a_1+\ldots+a_k+a_{k+1}}\)), która jest już podzielna przez n.

[bagienny]

W sumie to jeszcze raz napisałeś prawie to samo, ale... pomogło! Dzięki