podzielność w 39-elementowym zbiorze

[ZFC]

Witam serdecznie,
czy ktoś mógłby mi dać wskazówkę lub przedstawić część rozumowania w następującym zadaniu:

Niech A będzie 39-elementowym zbiorem takim, że
\(\displaystyle{ \bigwedge\limits_{x\in A}x\in \left\{ {0, 1, 2, ..., 19 \right\}.}\)
Wykaż, że istnieje 20-elementowy zbiór B taki, że
\(\displaystyle{ \bigvee\limits_{a_{1}, a_{2}, ..., a_{20}\in B}20}| a_{1} + a_{2} +...+ a_{20}}\).

Pozdrawiam.

Ps. Niestety w Poradniku LaTex-u nie znalazłem symbolu podzielności, więc użyłem miast jego \(\displaystyle{ \backslash}\).

-- 7 paź 2014, o 21:10 --

[norwimaj]

Niech A będzie 39-elementowym zbiorem takim, że
\(\displaystyle{ \bigwedge\limits_{x\in A}x\in \left\{ {0, 1, 2, ..., 19 \right\}.}\)

Zbiór zawarty w zbiorze 20-elementowym nie może być 39-elementowy. Zatem z powyższego wynika dowolna teza.

[ZFC]

Moim zdaniem (poprawcie mnie jeżeli się mylę) to zadanie mówi, że każdy element \(\displaystyle{ A}\) jest równy \(\displaystyle{ 0, \ 1, \ 2, \ \ldots}\),
\(\displaystyle{ 18}\) lub \(\displaystyle{ 19}\). Nie jest to jednak równoważne ze zdaniem - "Zbiór \(\displaystyle{ A}\) jest 20-elementowy".

-- 8 paź 2014, o 17:26 --

Innymi słowy:
Udowodnij, że wśród \(\displaystyle{ 39}\) liczb równych \(\displaystyle{ 0, \ 1, \ 2, \ \ldots, \ 18}\) lub 19 istnieje 20 liczb, których suma jest podzielna przez \(\displaystyle{ 20}\).

Myśle, myśle i nic wymyślić nie mogę

[Ponewor]

Mylisz się, pierwotne sformułowanie zadania jest jak mówił norwimaj niepoprawne.

Wskazówka jest taka:
Po pierwsze to z jakiego przedziału są te liczby nie ma najmniejszego znaczenia. Wystarczy nam, że są całkowite.
Po drugie udowodnij następujący fakt: wśród dowolnych dwudziestu liczb całkowitych istnieje pewna ich ilość której suma podzielna jest przez \(\displaystyle{ 20}\).

[ZFC]

Stawiam hipotezę, że fakt ten jest prawdziwy dla dowolnej liczby liczb (oczywiście dodatnich całkowitych), jednak w głowie mam pustkę; nie wiem jak go udowodnić ani jak wykorzystać w zdaniu. Próbowałem dowodzić nie wprost, jednak moje próby spełzły na niczym. Wiem, że problem jest dla Pana trywialny, lecz proszę o cierpliwość i wyrozumiałość . Tymczasem próbuję dalej...

[Ponewor]

Przyjrzyj się takim liczbom:
\(\displaystyle{ a_{1} \\ a_{1}+a_{2} \\ a_{1}+a_{2}+a_{3} \\ \vdots \\ a_{1}+a_{2}+a_{3}+\ldots +a_{20}}\)
Ile ich jest? Jakie mogą dawać reszty w dzieleniu przez \(\displaystyle{ 20}\)?
Oczywiście masz rację - ten fakt jest prawdziwy dla dowolnej innej liczby niż \(\displaystyle{ 20}\).

[ZFC]

Jest ich \(\displaystyle{ 20}\), ale dają chyba dowolne reszty. Chyba, że mówisz w ogóle; wówczas to z dwumianu Newtona.

[Ponewor]

A ile jest reszt w dzieleniu przez \(\displaystyle{ 20}\)?

[ZFC]

No \(\displaystyle{ 20}\).

[a4karo]

@Ponewor
chyba dryfujesz w złym kierunku: pokażesz w ten sposób, że znajdzie się pewna ilośc liczb, których suma jest podzielna przez 20. W zadaniu masz pokazać, że znajdzie się dokładnie 20 takich liczb.

[Ponewor]

Z tego można potem wykazać tezę, ten fakt jest niezbędny.

ZFC, załóż, że żadna z tych \(\displaystyle{ 20}\) liczb nie jest podzielna przez \(\displaystyle{ 20}\) i skorzystaj z zasady szufladkowej.

[ZFC]

No tak, wtedy dwie dają tą samą resztę, więc ich różnica jest podzielna.

[Ponewor]

A nie, jednak ta metoda nie zadziała, w ten sposób mogę pokazać, że pewna ich ilość nie mniejsza niż \(\displaystyle{ 20}\) dzieli się przez \(\displaystyle{ 20}\). Mogę pokazać więcej niż Pan a4karo sugerował, że mogę, stąd odruchowo zaprzeczyłem, ale to i tak nie wystarczy.

Przepraszam.

[ZFC]

Ale mimo wszystko dzięki za wysiłek.

-- 9 paź 2014, o 18:25 --

a4karo, a czy Pan ma pomysł?

[Ponewor]

No bo jak masz takie dwie sumy które dają tą samą resztę w dzieleniu przez \(\displaystyle{ 20}\), to można je odjąć i otrzymujesz pewną ich ilość nie większą niż \(\displaystyle{ 20}\), której suma jest podzielna przez \(\displaystyle{ 20}\). To jest dowód naszego lematu.

Teraz zastosujemy lemat do naszego "zbioru" i wyjmiemy z niego sobie te liczby których suma jest podzielna przez \(\displaystyle{ 20}\) na półkę. Jeśli w "zbiorze" zostało nie mniej niż \(\displaystyle{ 20}\) liczb, to stosujemy lemat aż do skutku, to jest gdy w "zbiorze" zrobi się ich mniej niż \(\displaystyle{ 20}\), ale wtedy na półce będzie ich nie mniej niż \(\displaystyle{ 20}\) (bo łącznie liczb jest \(\displaystyle{ 39}\)) i ich suma jest podzielna przez \(\displaystyle{ 20}\).