Zasada szufladkowa Dirichleta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja bez powtórzeń
permutacja z powtórzeniami


kombinacja bez powtórzeń
kombinacja z powtórzeniami


wariacja bez powtórzeń
wariacja z powtórzeniami


liczby Bella
liczby Catalana
liczby Stirlinga
liczby Eulera


zasada szufladkowa Dirichleta
zasada włączeń i wyłączeń


Zasada szufladkowa Dirichleta – twierdzenie matematyczne, którego sformułowanie przypisuje się Dirichletowi, stwierdzające, iż jeżeli przedmiotów włoży się do różnych szufladek (gdzie , oraz ), to co najmniej w jednej szufladce znajdą się co najmniej dwa przedmioty[1].

Formalna treść twierdzenia:

  • jeżeli zbiór liczy elementów (gdzie ), to któryś ze zbiorów musi liczyć co najmniej dwa elementy[1][2].

Inna wersja formalna brzmi następująco:

  • Jeżeli moc zbioru wynosi , a zbioru i , to nie istnieje funkcja różnowartościowa ze zbioru do zbioru [1].

Wydaje się, że ta oczywista obserwacja nie może mieć poważnych zastosowań, ale jest akurat przeciwnie. Zasada szufladkowa bywa wykorzystywana w dowodach wielu głębokich twierdzeń matematycznych i często samo zauważenie, że można ją zastosować, jest kluczem do rozwiązania problemu[1].

Uogólnienie na nieskończoność[edytuj]

Zasadę szufladkową Dirichleta można uogólnić na zbiory nieskończone. Brzmi ona wtedy następująco:

Jeśli zbiór ma nieskończenie wiele elementów, to któryś ze zbiorów jest nieskończony[1].

Przypisy

  1. a b c d e Wojciech Kryszewski: Wykład analizy matematycznej. T. 1: Funkcje jednej zmiennej. Wydawnictwo Naukowe Uniwersytetu Mikołaja Kopernika, 2014, s. 67. ISBN 8323123527.
  2. Mariusz Swornóg, Liniowe Stałe Harbourne'a dla konfiguracji rzeczywistych na płaszczyźnie rzutowej, Uniwersytet Pedagogiczny im. KEN w Krakowie, 2016, s.18, lemat 2.22

Bibliografia[edytuj]

  • K. Cegiełka, E. Stachowski, K. Szymański: Encyklopedia dla wszystkich. Matematyka. Warszawa: Wydawnictwo Naukowo-Techniczne, 2000. ISBN 83-204-2334-1. str. 213