Zasada szufladkowa Dirichleta

Zasada szufladkowa Dirichleta

Zasada szufladkowa Dirichleta, sformułowana przez Petera Dirichleta w 1834 roku, to twierdzenie matematyczne, które stwierdza, że jeśli $m$ przedmiotów umieścimy w $n$ różnych szufladkach, gdzie $m\; >\; n\; >\; 0$, to w co najmniej jednej szufladce znajdą się co najmniej dwa przedmioty. Formalnie: jeśli zbiór $X\; =\; X\_1\; \backslash cup\; X\_2\; \backslash cup\; \backslash dots\; \backslash cup\; X\_k$ ma $n$ elementów, gdzie $n\; >\; k$, to przynajmniej jeden zbiór $X\_i$ zawiera co najmniej dwa elementy.

Uogólnienie na zbiory nieskończone

Zasadę szufladkową można również uogólnić na zbiory nieskończone. Twierdzenie brzmi: jeśli zbiór $X\; =\; X\_1\; \backslash cup\; X\_2\; \backslash cup\; \backslash dots\; \backslash cup\; X\_k$ zawiera nieskończoność elementów, to przynajmniej jeden zbiór $X\_i$ jest nieskończony.

Przykłady zastosowania zasady

• Znajomi w grupie: Wśród $N$ osób (gdzie $N\; \backslash geqslant\; 2$) istnieją co najmniej dwie osoby, które mają tę samą liczbę znajomych. Dowód opiera się na tym, że każda osoba może mieć najwyżej $N-1$ znajomych.
• Koloryzacja płaszczyzny: Jeśli płaszczyzna jest pomalowana na dwa kolory, istnieje prostokąt, którego wierzchołki mają ten sam kolor. Dowód polega na skonstruowaniu prostokąta 2×8 i analizie punktów kratowych.
• Potęgi liczby 7: Wśród kolejnych potęg liczby $7$ istnieje taka, której zapis dziesiętny kończy się na 001. Dowód polega na rozważeniu reszt z dzielenia przez 1000.

Przypisy i Bibliografia

Informacje na temat zasady szufladkowej można znaleźć w literaturze dotyczącej kombinatoryki i teorii mnogości.

Linki zewnętrzne

Więcej informacji można znaleźć na kanale PBS Infinite Series na YouTube: [https://www.youtube.com/watch?v=HMpSKjK9clA How Many Humans Have the Same Number of Body Hairs?].