Dirichletův princip: Porovnání verzí
Smazaný obsah Přidaný obsah
m + označení přihrádkový princip |
rozšíření |
||
Řádek 1:
'''Dirichletův princip''' (někdy také označovaný jako '''zásuvkový princip''', '''přihrádkový princip''' nebo '''princip holubníku''') je matematické tvrzení tematicky patřící do oboru [[teorie množin]], případně [[Nekonečná kombinatorika|nekonečné kombinatoriky]]. Jeho nejjednodušší, „populární“ znění se dá formulovat např. tak, že pokud umístíme ''m'' předmětů do ''n'' přihrádek (''m'', ''n'' jsou [[přirozené číslo|přirozená čísla]]), kde ''m'' > ''n'', pak bude existovat alespoň jedna přihrádka ve které budou alespoň dva předměty. Umístíme-li tedy například deset holubů (''m'' = 10) do devíti holubníků (''n'' = 9), pak v alespoň jednom holubníku musí být alespoň dva holubi. V jeho silnější verzi pak můžeme říct, že pokud umístíme ''kn+1'' předmětů do ''n'' přihrádek, pak v alespoň jedné přihrádce bude alespoň ''k+1'' předmětů (pro 19 holubů a devět přihrádek bude existovat alespoň jedna, v které budou alespoň 3 holubi). Tato jednoduchá tvrzení jsou poté dále zobecněna a formálněji definována – viz níže.
Ačkoliv tento samozřejmý princip byl používán již dříve, za prvního kdo ho užíval vědomě k dokazování složitějších tvrzení je považován německý matematik [[Johann Peter Gustav Lejeune Dirichlet]] (1805-1859). Ten jej jako první výslovně uvedl v roce 1834 pod názvem ''Schubfachprinzip'' (zásuvkový princip). Pod označením zásuvkový princip (''principio dei cassetti'') je dodnes používán např. v [[italština|italštině]]. V [[angličtina|angličtině]] se používá zejména označení ''pigenhole principle'' (princip holubníku), v dalších jazycích (např. v [[ruština|ruštině]]) pak Dirichletův princip.
== Formulace principu ==▼
== Příklady ==
Několik jednoduchých příkladů pro ilustraci principu:
:# 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 apod.)
:# 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 -h + s = 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×9 = 36 < 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í ==
Dirichletův princip tvrdí, že pokud [[nekonečná množina]] vznikla jako [[sjednocení]] konečně mnoha množin, pak alespoň jedna z nich byla nekonečná.
Řádek 36 ⟶ 46:
== Použití principu ==
Nejužitečnější je i přes svou jednoduchost základní verze '''Dirichletova principu'''. V důkazu mnoha vět z [[matematická analýza|matematické analýzy]] narazíme na formulace typu „až na konečný počet hodnot“, v jejichž pozadí obvykle stojí nějaká forma '''Dirichletova principu''', často vnímaného jako něco samozřejmého
== Související články ==
| |||