Dirichletův princip
From Wikipedia, the free encyclopedia
Dirichletův princip (někdy také označovaný jako zásuvkový princip, přihrádkový princip, princip králíků a kotců nebo princip holubníku) je matematické tvrzení z teorie množin, případně nekonečné kombinatoriky.
Nejjednodušší, „populární“ znění principu se dá formulovat například, že pokud umístíme m předmětů do n přihrádek (m, n jsou 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 přihrádek v holubníku (n = 9), pak v alespoň jedné přihrádce musí být alespoň dva holubi. V jeho obecnější verzi pak lze ří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štině. V angličtině se používá zejména označení pigeonhole principle (princip holubníku), v dalších jazycích (např. v ruštině) pak Dirichletův princip. Princip holubníku není úplně přesný překlad, protože slovo pigeonhole se v angličtině používá prakticky už jen v přeneseném významu, kdy znamená buď přihrádku, typicky v nějakém třídicím regálu na poštu, nebo i sloveso zaškatulkovat, zařadit do kategorie. Přesto se tento překlad používá (podobně i do němčiny zpětně pronikl pojem Taubenschlagprinzip) a holubi jsou oblíbeným příkladem, na kterém se tento princip ilustruje.