zasada szufladkowa dirichleta

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matind
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 kwie 2016, o 19:17
Płeć: Mężczyzna
Lokalizacja: polska

zasada szufladkowa dirichleta

Post autor: matind »

Witam, mam proste zadanie:

Pokaż, że wśród mieszkańców Poznania (500 000) są co najmniej 4 osoby, które mają taką samą ilość włosów na głowie. Liczba włosów ok. 140 tyś.

Mogę to wykazać po prostu pisząc?

\(\displaystyle{ \frac{500000}{140 000} = 4}\) w zaokrągleniu do góry.
Janpostal
Użytkownik
Użytkownik
Posty: 144
Rejestracja: 7 gru 2015, o 17:20
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 17 razy
Pomógł: 16 razy

zasada szufladkowa dirichleta

Post autor: Janpostal »

Aby zachodziła ta zależność mieszkańców musi być co najmniej 560 tys.
freeszpak
Użytkownik
Użytkownik
Posty: 72
Rejestracja: 13 gru 2014, o 14:26
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 10 razy
Pomógł: 5 razy

zasada szufladkowa dirichleta

Post autor: freeszpak »

matind pisze: Mogę to wykazać po prostu pisząc?

\(\displaystyle{ \frac{500000}{140 000} = 4}\) w zaokrągleniu do góry.
Nic nie wykazałeś. Podałeś jakieś cyferki z których nie wiadomo co wynika, jakbyś to skomentował to by było lepiej. Liczba włosów to około 140tyś? A nie jest w zadaniu, że maksymalnie tyle może być? Ewentualnie jakieś sprecyzowanie co znaczy "około", jakie może być odchylenie
Janpostal pisze:Aby zachodziła ta zależność mieszkańców musi być co najmniej 560 tys.
Udowodnij to. Nie wiem czy Ci sie uda bo moim zdaniem musi ich być co najmniej 420 001. Przyjmując, że w zadaniu chodziło o to, że 140tyś to maksymalna liczba włosów a nie "około". Dodatkowo trzeba dodać, że jest to minimalna liczba mieszkańców dla której zdanie "Istnieje 4 mieszkańców o tej samej liczbie włosów" jest prawdziwe zawsze. Bo przecież może się zdarzyć że byłoby tylko czterech łysych mieszkańców i zdanie z zadania również jest prawdziwe i to tylko dla czterech mieszkańców.
Janpostal
Użytkownik
Użytkownik
Posty: 144
Rejestracja: 7 gru 2015, o 17:20
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 17 razy
Pomógł: 16 razy

zasada szufladkowa dirichleta

Post autor: Janpostal »

freeszpak, Masz całkowitą rację, nie wiem co myślałem pisząc ten post. Oczywiście, że 420 001.
matind
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 kwie 2016, o 19:17
Płeć: Mężczyzna
Lokalizacja: polska

zasada szufladkowa dirichleta

Post autor: matind »

Dobra, a jakbym napisał następująco:

X = 500 000 (liczba mieszkańców)
Y = 140 000 (liczba włosów na głowie)

\(\displaystyle{ |X| > r \cdot |Y|}\)

\(\displaystyle{ 500 000 > 3 \cdot 140 000}\)

\(\displaystyle{ r = 3}\)
dec1
Użytkownik
Użytkownik
Posty: 714
Rejestracja: 21 mar 2016, o 21:42
Płeć: Mężczyzna
Pomógł: 191 razy

zasada szufladkowa dirichleta

Post autor: dec1 »

Liczba szufladek to liczba włosów - \(\displaystyle{ 140000}\). W każdej będą trzy osoby, jeśli osób będzie \(\displaystyle{ 140000\cdot 3=420000}\). Zatem umieszczenie 420001. osoby sprawi, że jedna szufladka będzie zawierała cztery osoby.
freeszpak
Użytkownik
Użytkownik
Posty: 72
Rejestracja: 13 gru 2014, o 14:26
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 10 razy
Pomógł: 5 razy

zasada szufladkowa dirichleta

Post autor: freeszpak »

matind, a Ty dalej równości, nierówności, cyferki... Chodzi o udowodnienie, masz przekonać osobę czytającą rozwiązanie że muszą istnieć takie 4 osoby. Naprawdę nie chodzi o wypisanie mądrych znaczków, tylko o pokazanie swojego rozumowania. Tzn znaczki mogą być ok pod warunkiem że je skomentujesz. Właśnie coś takiego co zrobił dec1 jest dobre, bo przedstawił rozumowanie, do którego też można się jeszcze troche przyczepić ale już jest o wiele lepiej
matind
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 kwie 2016, o 19:17
Płeć: Mężczyzna
Lokalizacja: polska

zasada szufladkowa dirichleta

Post autor: matind »

Okey, po prostu to robiłem sobie w głowie. Następnym razem dopiszę do tego jakąś słowną odpowiedź.
ODPOWIEDZ