Zasada szufladkowa

[foxbuur]

Zadanie 1.
Bolek wybrał 300 różnych podzbiorów trójelementowych ze zbioru \(\displaystyle{ \left\{ 1, . . . ,100\right\}}\). Pokaż, że pewne dwa z tych podzbiorów mają tą samą sumę elementów.

Zadanie 2.
W pewnym kraju jest dokładnie 100 lotnisk. Pokaż, że wśród nich istnieją dwa lotniska, które mają połączenia z taką samą liczbą lotnisk w tym kraju. (Zakładamy, że pewne lotnisko może być nieczynne oraz że lotnisko A ma połączenie z B tylko wtedy, gdy B ma połączenie z A).

Zadanie 3.
Do każdej z 72 różnych urn wkładamy 3 piłki, z których każda może być czerwona lub niebieska, lub zielona (piłki tego samego koloru są nierozróżnialne). Pokaż, że istnieje 8 urn zawierających taką samą kombinację piłek.


Czy mógłbym poprosić o jakieś wskazówki do zadania 2. i 3., oraz o sprawdzenie zadania 1.?

Zadanie 1.
Chłopiec wybiera 300 podzbiorów trójelementowych ze zbioru \(\displaystyle{ \left\{ 1, . . . ,100\right\}}\).
Najbardziej skrajne wartości sumy elementów to 6 oraz 297, więc wszystkie podzbiory mają swoje sumy leżące pomiędzy \(\displaystyle{ \left[ 6; 297\right]}\), więc możliwych wartości jest 292.
Chcemy przyporządkować każdy podzbiór do odpowiedniej sumy, ale \(\displaystyle{ 300 > 292}\), więc istnieją co najmniej dwa podzbiory mające identyczną sumę elementów.

[Medea 2]

Pierwsze okej. W drugim załóż nie wprost, że każde ma inną liczbę połączeń. Każde może mieć \(\displaystyle{ 0, \cdot, 99}\) sąsiadów. Czy możliwe jest, by było lotnisko bez sąsiadów i z 99 sąsiadami?

[Milczek]

Co do zadanie drugiego, jest to inny wariant zadania ze znajomymi które pewnie robiłeś, a jak nie robiłeś to zrób te a potem na pewno uda się zrobić drugie :
Wykaż że w każdej grupie osób są dwie osoby które mają taką samą liczbę znajomych. Oczywiście jeśli A zna B to B zna A

[foxbuur]

Zadanie:
wykaż że w każdej grupie osób są dwie osoby które mają taką samą liczbę znajomych. Oczywiście jeśli A zna B to B zna A.
Rozwiązanie:
dana jest grupa n-osobowa, a każda osoba może znać \(\displaystyle{ \left[ 1,...,n-1\right]}\) osób.
Czyli tworzymy funkcję \(\displaystyle{ f: \left[ 1,...,n \right] \rightarrow \left[ 1,...,n-1\right]}\).
Funkcja odwzorowuje zbiór n-elementowy w zbiór (n-1)elementowy.
Zatem \(\displaystyle{ \exists _{A,B \in [1,...,n]} A \neq B \wedge f(A) = f(B)}\), czyli istnieją dwie osoby, które mają taką samą liczbę znajomych.

Zanim rozpiszę w podobny sposób zadanie 2., czy ktoś mógłby powiedzieć, czy to jest poprawnie rozpisane?

[Medea 2]

Poprawne, ale przesadnie formalne. Po prostu osób jest \(\displaystyle{ n}\), zaś zbiór liczb znajomych ma moc co najwyżej \(\displaystyle{ n-1}\) (bo nie może być jednocześnie ktoś samotny i ktoś wszechznający), więc można użyć zasady.

[Milczek]

Cóż , jeśli mamy być bardzo formalni to oczywiście - Źle
A to dlatego że z góry założyłeś że jest osoba która zna wszystkich , to nie musi być prawdą.

Edit. i rozpisz w mniej podobny sposób , ja wiem że matematyka ma być formalna itd. itp. ale jako że nie piszemy pracy naukowej to pierwowzory piszmy w języku zrozumiałym dla każdego. Tak <- ja nie rozumiem całego zapisu w 100 % choć ogólny sens wyłapałem

[a4karo]

Cóż , jeśli mamy być bardzo formalni to oczywiście - Źle
A to dlatego że z góry założyłeś że jest osoba która zna wszystkich , to nie musi być prawdą.

Oczywiście dobrze. Gdyby było stwierdzenie, że funkcja jest "na" \(\displaystyle{ [1,2,\dots,n-1]}\), to byłoby źle. Ale jest napisane "w".

[Milczek]

a4karo, czy nie uważasz że foxbuur, powinien rozważyć jeszcze funkcjie gdzie \(\displaystyle{ f: \left[ 1,...,n \right] \rightarrow \left[ 0,...,n-2\right]}\)? Bo mi się wydaje że tego brakuje przez co rozwiązanie zadania jest wybrakowane. Ale to może przez ten zapis gdzie coś ważnego faktycznie mi umknęło. Jeśli tak to wytłumacz mi łopatologicznie dlaczego rozwiązanie jest na 100% poprawne, powtarzam że moim zdaniem przy takim zapisie jaki zaprezentował foxbuur powinno się rozważyć dodatkowo to co ja napisałem.

Edit. W co do poprzedniego postu : foxbuur założył możliwość istnienia osoby która zna wszystkich. Tak czy siak brakuje tego co napisałem wyżej.

[a4karo]

A czemu nie \(\displaystyle{ f: \left[ 1,...,n \right] \rightarrow \left[ 3,8,9,...,n-3\right]}\)?

Zapis \(\displaystyle{ f: \left[ 1,...,n \right] \rightarrow \left[ 0,...,n-2\right]}\) oznacza dowolną funkcję, której argumentami sa liczby \(\displaystyle{ 1,..,n}\) a wartości są w zbiorze \(\displaystyle{ 0,...,n-1}\), ale nie znaczy, że wartościami muszą być wszystkie liczby z tego zbioru.