Dirichletův princip: Porovnání verzí
Smazaný obsah Přidaný obsah
m přidána Kategorie:Ramseyovská teorie (CatCompleter via en:Category:Ramsey theory) za použití HotCat |
|||
Řádek 8:
# 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ělovali 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 atp.)
# Měli bychom dokázat, že na vypuklém šestnáctistěnu s 9 vrcholy existuje vrchol, z kterého vychází alespoň
== Formulace principu a jeho zobecňování ==
|