kilka zadań z zasady szufladkowej

[Galactico]

Witam! Bardzo prosiłbym o pomoc w rozwiązaniu tych kilku zadań z zasady szufladkowej Dirichleta. Będzie to dla mnie nieoceniona pomoc przed egzaminem!
1. Pokaż, że w zbiorze wybranych 100 liczb ze zbioru {1,2,3...200}, z których jedna z wybranych liczb jest mniejsza niż 16, są takie dwie, że jedna dzieli drugą.
2. Pokaż, że wśród jakichkolwiek 52 liczb całkowitych istnieją dwie, których suma, lub których różnica jest podzielna przez 100.
3. W pokoju jest 10 osób, które nie są starsze niż 60 lat i nie są młodsze niż 1 rok. Udowodnij, że można znaleźć dwa rozłączne zbiory osób, w których suma wieku będzie taka sama.
4. Dziecko ogląda TV przynajmniej godzinę dziennie przez 7 tygodni ale nigdy więcej niż 11 godzin na tydzień. Udowodnij, że jest pewien okres kolejnych dni, w których dziecko ogląda TV dokładnie 20 godzin. (oczywiście mówimy o godzinach jako o liczbach całkowitych)
5. Student ma 37 dni na przygotowanie do egzaminu. Potrzebuje 60 godzin nauki. Chce także uczyć się przynajmniej godzinę dziennie. Pokaż, że zawsze istnieje taki ciąg kolejnych dni, w których będzie się on uczył (w sumie) dokładnie 13 godzin.
Z góry bardzo bardzo dziękuję!!!

[jgarnek]

2. Niech naszymi szufladkami będą wartości bezwzględne reszt mod 100; tzn. w pierwszej szufladce znajdą się liczby dające resztę 0 przy dzieleniu przez 100, w drugiej 1 lub 99, w trzeciej 2 lub 98, itd. Mamy więc 51 takich szufladek i 52 liczby, więc znajdą się dwie, których suma, lub których różnica jest podzielna przez 100.
3. liczba niepustych podzbiorów: \(\displaystyle{ 2^{10}-1=1027}\)
najniższa suma lat: \(\displaystyle{ 1}\)
najwyższa suma lat: \(\displaystyle{ 60 \cdot 10=600}\)
ilość możliwych sum: 600
Nasze szufladki to możliwe sumy, kulki to podzbiory.

[Galactico]

Dzięki wielkie za odpowiedź! Nie rozumiem tylko tego:

Nasze szufladki to możliwe sumy, kulki to podzbiory.

Jakie kulki?
Ma ktoś jeszcze pomysł na pozostałe zadania?

[Szemek]

Jakie kulki?

To w końcu zasada szufladkowa, więc jakoś to trzeba sobie wyobrażać.
Szufladki i kulki, które wrzucamy do szufladek.

5)
\(\displaystyle{ a_i}\) - łączny czas przygotowywania się od początku z \(\displaystyle{ i}\)-tym dniem włącznie

\(\displaystyle{ 1 \le a_1 < a_2 < .... < a_{37} \le 60 \\
14 \le \underbrace{a_1 + 13}_{b_1} < \underbrace{a_2 + 13}_{b_2} < .... < \underbrace{a_{37} + 13}_{b_{37}} \le 73}\)

Mamy 74 liczb: \(\displaystyle{ \{a_1, a_2, a_3, ..., a_{37}, b_1, b_2, b_3, ..., b_{37} \}}\)
Wrzucamy je do 73 szufladek (\(\displaystyle{ \forall\limits_{i \in \{1,...,37\}} 1 \le a_i, b_i \le 73}\))
Okazuje się, że istnieją 2 takie liczby, których różnica jest równa 13,
więc istnieje taki ciąg kolejnych dni w których będzie się on uczył (w sumie) dokładnie 13 godzin.

[Galactico]

Dziękuję bardzo! Jakby ktoś jeszcze miał jakieś pomysły na 1. i 4. to bardzo proszę o pomoc...

[Szemek]

4) analogicznie do zadania 5)
\(\displaystyle{ a_i}\) - ilość godzin (całkowita) spędzonych przed telewizorem do \(\displaystyle{ i}\)-tego dnia włącznie
\(\displaystyle{ 1 \le a_1 < a_2 < ... < a_{48} < a_{49} \le 77 \\
21 \le \underbrace{a_1 + 20}_{b_1} < \underbrace{a_2 + 20}_{b_2} < ... < \underbrace{a_{48} + 20}_{b_{48}} < \underbrace{a_{49} + 20}_{b_{49}} \le 97}\)

Mamy 98 liczb: \(\displaystyle{ \{a_1, a_2, a_3, ..., a_{49}, b_1, b_2, b_3, ..., b_{49} \}}\)
Wrzucamy je do 97 szufladek (\(\displaystyle{ \forall\limits_{i \in \{1,...,49\}} 1 \le a_i, b_i \le 97}\))
Okazuje się, że istnieją 2 takie liczby, których różnica jest równa 20,
więc istnieje taki pewien okres kolejnych dni, w których dziecko ogląda TV dokładnie 20 godzin.


PS: Galactico, studiujesz może na AGH

[Galactico]

Tak, a czemu pytasz?

[Szemek]

pierwszego zadania nie potrafię rozwiązać, a rozwiązania, które znalazłem w internecie nie są dla mnie zbyt jasne

ale podaję źródła
zadanie 91, strony 169-170
... oblem-Book

Section 2.4, 2.


PS:

Tak, a czemu pytasz?

Studiuje informatykę na EAIiE, I rok i identyczne zadania mam na zestawach z dyskretnej.
Pozdrowienia dla kolegi z AGH

[karolina668]

Jakie kulki?

\(\displaystyle{ 1 \le a_1 < a_2 < .... < a_{37} \le 60 \\
14 \le \underbrace{a_1 + 13}_{b_1} < \underbrace{a_2 + 13}_{b_2} < .... < \underbrace{a_{37} + 13}_{b_{37}} \le 73}\)

Mamy 74 liczb: \(\displaystyle{ \{a_1, a_2, a_3, ..., a_{37}, b_1, b_2, b_3, ..., b_{37} \}}\)
Wrzucamy je do 73 szufladek (\(\displaystyle{ \forall\limits_{i \in \{1,...,37\}} 1 \le a_i, b_i \le 73}\))
.

Chyba mi powoli mózg koroduje czy coś Niby rozumiem schemat, ale powiedzcie mi - dlaczego tam się AKURAT DODAJE 13, a potem bierze wszystkie liczby a i b i wrzuca AKURAT DO TYCH 73 szufladek?

[pproc]

Wyjaśnienia do zad. 5

Treść:
Student na przygotowanie się do egzaminu miał 37 dni i potrzebował 60 godzin nauki. Codziennie uczył się co najmniej 1 godzinę (i zawsze wielokrotność pełnej godziny). Udowodnij, że były takie kolejne dni, w których uczył sie łącznie dokładnie 13 godzin.

Rozw.

Oznaczając \(\displaystyle{ S_{i}}\) jako suma godzin, jakie student spędził na nauce od początku do danego dnia włącznie, otrzymujemy:

\(\displaystyle{ 1\leqslant S_{1}\leqslant S_{2}\leqslant...\leq S_{37}\leqslant60}\)

Zakładając, że nasza teza jest fałszywa dochodzimy do wniosku, że jeśli do którejkolwiek elementu tego ciągu dodamy 13h to nie otrzymamy innego el. z tego samego ciągu.

Zatem:

\(\displaystyle{ 1\leqslant S_{1}<S_{2}<...<S_{37}=60}\) - dany ciąg ma 37 el.

\(\displaystyle{ 1+13\leqslant S_{1}+13<S_{2}+13<...<S_{37}+13=60+13}\)

\(\displaystyle{ 14\leqslant S_{1}+13<S_{2}+13<...<S_{37}+13=73}\) - dany ciąg również posiada 37 el.


Jeśli teraz zsumuje te ciągi to otrzymamy 1 ciąg różnowartościowy, posiadający 74 el., ale mieszczący się w granicach [1,73]. Z zasady Dirichleta wynika, iż jest to sprzeczne, a więc były takie kolejne dni, w których student uczył sie łącznie dokładnie 13 godzin (ponieważ jakaś różnica sum (lub jakaś \(\displaystyle{ S_{i}}\) ) wynosiła dokł. 13). Co należało dowieść.