Dirichletův princip: Porovnání verzí

Smazaný obsah Přidaný obsah
m typo
Řádek 7:
:# Mějme koš s 8 černými a 10 bílými ponožkami. Poslepu z něj budeme vytahovat po jedné ponožce. Otázka zní, kolik budeme muset vytáhnout nejméně ponožek, abychom měli jistotu, že budeme mít alespoň jeden pár stejné barvy. Odpověď je tři, neboť máme dvě skupiny (přihrádky) – černé a bílé a po vytáhnutí třetí ponožky tak v jedné z těchto skupin již musí být dvě ponožky.
:# Ačkoliv zní princip jednoduše, může být použit k dokázání na první pohled nečekaných výsledků. Můžeme např. dokázat, že v [[Praha|Praze]] žijí dva lidé, kteří mají přesně stejný počet vlasů. Uvážíme-li, že počet vlasů jednoho člověka nikdy nepřesahuje 1 000 000 a v Praze žije více než 1 000 000 lidí – pak musí být alespoň dva, kteří mají stejný počet vlasů.
:# Máme-li skupinu ''n'' lidí, kde se někteří navzájem znají, pak vždycky existují dva takoví, kteří v této skupině znají stejný počet lidí. Rozdělova-li bychom jednotlivé lidi do skupin podle toho, kolik znají ostatních, pak těchto skupin bude ''n-1'', neboť nemůže zároveň existovat skupina, kde by byl někdo, kdo zná všechny ostatní a skupina, kde by byl někdo, kdo nezná nikoho. Když by někdo totiž znal všechny ostatní, musel by znát i tohoto člověka, a jelikož se dle zadání musí lidé znát navzájem, musel by ho znát i on. Máme tedy ''n'' lidí a ''n-1'' skupin, což znamená, že alespoň v jedné z nich musí být alespoň 2 lidé – ti tedy znají stejný počet lidí. (Místo toho, že se lidé znají, se dá příklad formulovat např. i tak, že si podávají ruce, hrají proti sobě zápasy apodatp.)
:# Měli bychom dokázat, že na vypuklém šestnáctistěnu s 9 vrcholy existuje vrchol, z kterého vychází alespoň 5 hran. Díky Eulerovu vztahu pro počet vrcholů (''v''), hran (''h'') a stěn (''s'') vypuklého mnohostěnu ''v&nbsp;-h&nbsp;+&nbsp;s&nbsp;=&nbsp;2'' spočítáme počet hran: ''21''. Rozdělíme každou na půl a vznikne nám 42 polohran. Rozřadíme je do devíti skupin podle toho, z kterého z 9 vrcholů vycházejí. Jelikož 4&times;9&nbsp;=&nbsp;36&nbsp;<&nbsp;42, musí alespoň v jedné skupině být 5 polohran, tudíž z jednoho vrcholu musí alespoň 5 polohran, tedy i hran, vycházet.
 
 
== Formulace principu a jeho zobecňování ==