Dowody - zasada pudełkowania

[Kacpro]

1. Udowodnij, że w dowolnym \(\displaystyle{ 52}\)-elementowym podzbiorze zbioru \(\displaystyle{ \{1,2,...,100\}}\) są 2 liczby, które różnią się dokładnie o \(\displaystyle{ 3}\).

2. Pokazać, że dla dowolnego zbioru złożonego z dwunastu różnych liczb naturalnych mniejszych od \(\displaystyle{ 120}\) istnieją 4 podzbiory, których elementy sumują się do tej samej liczby.

Pierwsze udało mi się udowodnić przez zaprzeczenie, ale nie wiem jak to zrobić używając zasady pudełkowania.

Z góry dzięki za pomoc

[Mruczek]

Zasada pudełkowania - fajna nazwa xD
Chyba chodziło o zasadę szufladkową Dirichleta (ZSD)

1.

Ukryta treść:    

Dzielimy ten zbiór w grupy - pary różniące się o \(\displaystyle{ 3}\) i samodzielne liczby.
Pary: \(\displaystyle{ \left\{ 1, 4\right\} ,\left\{ 7,10\right\} ,\left\{ 13,16\right\} ,...,\left\{ 97,100\right\}}\) - \(\displaystyle{ 17}\) par
\(\displaystyle{ \left\{ 2, 5\right\} ,\left\{ 8, 11\right\} ,...,\left\{ 92, 95\right\}}\) - \(\displaystyle{ 16}\) par
\(\displaystyle{ \left\{ 3, 6\right\} ,\left\{ 9, 12\right\} ,...,\left\{ 93, 96\right\}}\) - \(\displaystyle{ 16}\) par
(W każdej kolejnej szóstce liczb \(\displaystyle{ \left\{ 6k+1, 6k+2, 6k+3, 6k+4, 6k+5, 6k+6\right\}}\) dla \(\displaystyle{ 0 \le k \le 15}\) jest po jednej parze każdego z trzech rodzajów: \(\displaystyle{ \left\{ 6k+1, 6k+4\right\}, \left\{ 6k+2, 6k+5\right\}, \left\{ 6k+3,6k+6\right\}}\).)
Pozostają dwie niesparowane liczby: \(\displaystyle{ 98,99}\).
Mamy łącznie \(\displaystyle{ 51}\) grup, ale wybieramy \(\displaystyle{ 52}\) liczby, więc na mocy ZSD, z którejś pary muszą być wybrane obie liczby - te liczby różnią się dokładnie o \(\displaystyle{ 3}\).

2.

Ukryta treść:    

Mamy łącznie \(\displaystyle{ 2 ^{12} = 4096}\) różnych podzbiorów tych \(\displaystyle{ 12}\) liczb. Każda z liczb jest \(\displaystyle{ \le 119}\), są to różne liczby, więc każdy podzbiór ma sumę \(\displaystyle{ \le 108 + 109 + ... + 119 = 108 \cdot 12 + 1 + 2 + ... + 11 = 1296 + 66 = 1362}\)
Jednocześnie jest ona \(\displaystyle{ \ge 0}\), czyli podzbiór może mieć jedną z \(\displaystyle{ 1363}\) sum. Ponieważ \(\displaystyle{ 1363 \cdot 3 = 4089 < 4096}\) to z ZSD pewne \(\displaystyle{ 4}\) podzbiory muszą mieć tę samą sumę.

[Kacpro]

Dzięki wielkie, nareszcie to zrozumiałem

[arek1357]

Apropo zasady pudełkowania (której jeszcze nie znam) to ja znam zasadę puszkowania...

[Malarz44]

Dobre wytłumaczone, też zrozumiałem