Na stronie używamy cookies. Korzystanie z witryny oznacza zgodę na ich wykorzystywanie. Szczegóły znajdziesz w Regulaminie.
ZAMKNIJ X

Zasada szufladkowa Dirichleta – dowód, przykłady

Ostatnio komentowane
lol gitara siema
wojskowy • 2016-12-11 07:41:40
W tym artykule jest błąd merytoryczny. Otóż edykt mediolański, wydany przez cesarza K...
Nicodemus • 2016-12-10 22:33:06
głupie do rzeczy na drugi raz
felisityfornow • 2016-12-10 17:19:44
Spoko?
DOWNN • 2016-12-10 15:00:50
Jest ok
Uczeń2002 • 2016-12-10 13:39:29
Autor:
Drukuj
Drukuj
Rozmiar
AAA

Zasada szufladkowa Dirichleta – dowód, przykłady

Zwróćmy uwagę na następujące twierdzenie:

Jeśli zbiór X = X_1 \cup X_2 \cup ... \cup X_n ma więcej niż n elementów to istnieje i \in \left \{ 1,2,...,n \right \} takie, że X_i ma więcej niż 1 element.

Innymi słowy, jeśli do n szuflad włożymy n+1 przedmiotów, to z całą pewnością będzie szuflada, w której znajdą się co najmniej dwa elementy.

To twierdzenie jest banalne w swej oczywistości, a jednak jego konsekwencje są dalekosiężne.

 

Przykład:

Czy we wnętrzu trójkąta równobocznego o boku 4 można umieścić 17 punktów tak, by odległość między każdymi dwoma była większa niż 1?

Podzielmy każdy z boków trójkąta na 4 odcinki długości 1, a następnie poprowadźmy przez punkty podziału proste równoległe do boków trójkąta.

W ten sposób otrzymaliśmy 16 małych trójkątów o boku 1. To będą nasze szufladki. Jeśli rozmieścimy w nich 17 punktów, to przynajmniej dwa znajdą się w jednym trójkącie, a wówczas ich odległość będzie mniejsza niż 1. Zatem na postawione w zadaniu pytanie odpowiedź jest przecząca.

 

Przykład:

Przy okrągłym stole jest sto miejsc odpowiednio oznakowanych flagami stu różnych państw. Ambasadorowie tych państw zajęli miejsca w sposób losowy tak, że żaden nie zajął przygotowanego dlań miejsca. Czy można tak obrócić stół, aby co najmniej dwóch ambasadorów siedziało przy swojej fladze?

Zauważmy, że dla każdego ze stu ambasadorów istnieje tylko jedno dobre miejsce. Stąd jeśli wyjściowa sytuacja nie jest dobra dla nikogo, to któreś z 99-ciu pozostałych ustawień stołu musi odpowiadać przynajmniej dwóm osobom. Zatem odpowiedź na podstawione w zadaniu pytanie jest pozytywna.

 

Sformułowana przez Dirichleta zasada jest przykładem prostej idei o istotnych i poważnych konsekwencjach. Istnieje bardzo wiele kontekstów kombinatorycznych, w których bywa ona użyteczna.

Polecamy również:

Komentarze (0)
1 + 4 =