Dirichletův princip (kombinatorika)

Dirichletův princip je jednoduchá, intuitivní a často užitečná metoda pro dokazování tvrzení konečných množin . Tento princip se často používá v diskrétní matematice , kde za určitých podmínek vytváří spojení mezi předměty ("králíky") a nádobami ("buňkami") [1] . V angličtině a některých dalších jazycích je toto tvrzení známé jako princip holubů , kdy předměty jsou holubi a nádoby jsou krabice [ 2] .

Nejběžnější je nejjednodušší formulace Dirichletova principu [3] :

Pokud jsou králíci usazeni v klecích a počet králíků je větší než počet klecí, pak alespoň jedna z klecí obsahuje více než jednoho králíka.

Existuje pro to také běžný výraz:

Pokud je počet buněk větší než počet králíků, pak je alespoň jedna buňka prázdná.

Další, obecnější formulace, viz níže .

První formulaci tohoto principu našli historici v populární sbírce Récréations Mathématiques ( francouzsky Récréations Mathématiques , 1624, pod jménem H. van Etten ), kterou vydal (pravděpodobně) francouzský matematik Jean Leurechon [4] . Tento princip se rozšířil po jeho aplikaci Dirichletem (od roku 1834) v oblasti teorie čísel [5] .

Dirichletův princip, v té či oné formě, je úspěšně aplikován v důkazu teorémů, díky čemuž jsou tyto důkazy jednodušší a jasnější. Mezi jeho oblasti použití patří diskrétní [6]atd.systémů lineárních nerovnic, analýza řešitelnostidiofantických aproximacímatematika, teorie [3] .

Jiné znění

Důkaz

Dirichletův princip v nejjednodušší formulaci: " je-li počet králíků větší než počet buněk, pak alespoň jedna z buněk obsahuje více než jednoho králíka " lze dokázat metodou "rozporem" . Ať jsou tam klece a králíci, navíc . Označit. počet králíků v -té buňce ( ). Předpokládejme, že v každé kleci je nejvýše jeden králík: $n$ $m$ $m>n$ $k_i$ $i$ $i=1,2,\tečky n$

$k_{1}\leqslant 1$ (počet králíků v 1. kleci je menší nebo roven 1);
$k_{2}\leqslant 1$ (počet králíků ve 2. kleci je menší nebo roven 1);
...
$k_{n}\leqslant 1$ (počet králíků v -té buňce je menší nebo roven 1). $n$

Pak celkový počet králíků Odtud Ale podle stavu problému . Mám rozpor, ■ . $m=k_{1}+k_{2}+\ldots +k_{n}\leqslant 1+1+\ldots +1=n.$ $m\leqslant n$ $m>n$

Podobně se dokazuje párový výrok: " pokud je počet buněk větší než počet králíků, pak je alespoň jedna buňka prázdná ."

Kromě výše uvedených dvou formulací existují dvě další užitečné, které lze také snadno dokázat [7] :

Pokud jsou králíci usazeni v klecích a nejsou tam žádné prázdné klece, pak je v každé kleci přesně jeden králík. $n$ $n$
Pokud jsou králíci umístěni v klecích a žádná klec neobsahuje více než jednoho králíka, pak je v každé kleci přesně jeden králík. $n$ $n$

Možnosti pro obecnější formulace [8] :

Při jakékoli distribuci nebo více položek v krabicích nebude v žádné krabici méně než jedna položka. $kn+1$ $n$ $k+1$
Pokud jsou králíci usazeni v klecích, pak alespoň jedna klec obsahuje alespoň králíky a alespoň jedna klec obsahuje maximálně králíků. Zde Iversonovy rohy a zaokrouhlit výraz v nich uzavřený na celek, respektive nahoru a dolů. $m$ $n$ $\left\lceil {\frac {m}{n}}\right\rceil$ $\left\lfloor {\frac {m}{n}}\right\rfloor$ $\lceil \dots \rceil$ $\lfloor \dots \rfloor$
Nechť je dána funkce definovaná na konečné množině a její mapování na konečnou množinu : kde je nějaké přirozené číslo a konstrukce tvaru znamená počet prvků konečné množiny ( kardinalita množiny ). Pak funkce nabude alespoň jednou nějakou hodnotu. $F,$ $A$ $B$ $f\colon A\rightarrow B,$ $\left|A\right|>n\cdot \left|B\right|,$ $n$ $\left|X\right|$ $X$ $F$ $n+1$

Příklady aplikací

Věta 1 . Pro libovolnou volbu pěti bodů uvnitř jednotkového čtverce existuje pár bodů, které jsou od sebe odděleny maximálně ${\frac {\sqrt {2}}{2}}.$

Důkaz . Věta se na první pohled zdá složitá a nesrozumitelná, ale pomocí Dirichletova principu je bez potíží dokázána [9] . Rozdělte čtverec na 4 čtvrtiny, jak je znázorněno na obrázku. Podle Dirichletova principu budou alespoň dva z pěti vybraných bodů spadat do jedné čtvrtiny a pak vzdálenost mezi nimi nebude větší než úhlopříčka čtvrtiny, rovna ■ ${\sqrt {{\left({\frac {1}{2}}\right)}^{2}+{\left({\frac {1}{2}}\right)}^{ 2}}}={\frac {\sqrt {2}}{2}}.$

Věta 2 . Část společnosti lidí potřást rukou. Dokažte, že ve firmě jsou alespoň dva lidé, kteří provedli stejný počet podání rukou [10] . $N$ $\left(N>1\right)$

Důkaz . Nechte - "krabice". Dejme do krabice ty členy společnosti, kteří si podali ruku. Pokud krabice není prázdná, pak jeden nebo více členů společnosti nepodali žádné handshake, a proto je krabice prázdná, protože počet podání ruky je pak menší . Z toho vyplývá, že neprázdných je vždy méně krabice než , a proto alespoň jedna krabice odpovídá dvěma nebo více lidem. ■ $\{H_{0},H_{1},\tečky H_{N-1}\}$ $N$ $H_{k}$ $k$ $H_{0}$ $H_{N-1}$ $N.$ $N,$

Věta 3 . Pro každé kladné iracionální číslo existuje nekonečně mnoho zlomků lišících se od méně než o (toto je jedna z verzí Dirichletovy věty o diofantických aproximacích ) [11] [12] . $A$ ${\frac {p}{q)),$ $A$ ${\displaystyle {\frac {1}{q^{2))))$

Důkaz . Pro libovolné přirozené číslo udělejme sadu hodnot: $N$ $(N+1)$

d_{1}=1\cdot a-[1\cdot a],

d_{2}=2\cdot a-[2\cdot a],

d_{3}=3\cdot a-[3\cdot a],

\tečky,

d_{N+1}=(N+1)\cdot a-[(N+1)\cdot a],

kde označuje celočíselnou část čísla.

[X]

Všechna tato čísla patří do intervalu od 0 do 1 včetně. Rozdělíme je do krabic: do prvního pole vložíme čísla od 0 včetně do nezahrnutého, do druhého - od včetně do nezahrnutého atd., do th - od včetně do nezahrnutého. Ale protože počet čísel je větší než počet polí, pak podle Dirichletova principu budou v jednom z polí alespoň dva rozdíly: a kdy $N$ $1/N$ $1/N$ $2/N$ $N$ $(N-1)/N$ $N/N$ $\left(N+1\right)$ $\left(N\right),$ $d_{i}=\left(i\cdot a-[i\cdot a]\right)$ $d_{j}=\left(j\cdot a-[j\cdot a]\right)$ $i<j.$

Hodnoty rozdílů podle konstrukce se liší o méně než Za předpokladu a dostáváme: ${\frac {1}{N}}:$ $d_{j}-d_{i}<{\frac {1}{N)).$ $q=ji$ $p=[j\cdot a]-[i\cdot a],$

|q\cdot ap|<{\frac {1}{N)),

nebo: (protože ).

\left|a-{\frac {p}{q}}\right|<{\frac {1}{q\cdot N}}\leqslant {\frac {1}{q^{2}} }

q\leqslant N

Kvůli libovolnosti čísla může být blízkost zlomku k číslu libovolně malá (v tomto případě je jistě nenulová, protože je iracionální podmínkou). Proto je počet zlomků odpovídajících stále bližším aproximacím nekonečný. ■ $N$ $p/q$ $A$ $A$ ${\frac {p}{q)),$

Další příklady lze nalézt v následujících zdrojích.

Článek Čínská věta o zbytku .
Kniha N. B. Alfutové a A. V. Ustinova [13] .
Kniha M. Aigner M. a G. Ziegler [14] .
Kniha od A. A. Andreeva et al [15]

Geometrické aplikace

V geometrii se používá několik variant Dirichletova principu, týkajících se délek, ploch a objemů [16] .

Pokud na délkovém segmentu existuje několik segmentů se součtem délek větším než , pak alespoň dva z těchto segmentů mají společný bod. $L$ $L$
Zobecnění . Pokud je na délkovém segmentu několik segmentů, jejichž součet délek je větší než , pak je alespoň jeden bod pokryt alespoň jedním z těchto segmentů. $L$ $kL$ $k+1$
Pokud je součet délek segmentů menší než , pak nemohou zcela pokrýt segment délky . $L$ $L$
Pokud je uvnitř obrazce oblasti, jejíž součet ploch je větší než , několik obrazců , pak alespoň dva z nich mají společný bod. $S$ $S$
Pokud je součet ploch několika obrazců menší , nemohou pokrýt plošný obrazec . $S$ $S$

Podobná tvrzení lze formulovat i pro svazky.

Příklad [17] . Několik kruhů je náhodně umístěno v kruhu o průměru 6, součet jejich průměrů je roven 50. Dokažte, že existuje přímka, která protíná alespoň devět těchto kruhů.

Důkaz . Nechť je libovolný průměr původní kružnice (o délce 6). Promítneme všechny vnitřní kruhy na průměr . Součet délek výstupků je zjevně roven součtu průměrů kruhů, tj. 50, a pokrývají (ne nutně úplně) průměr . Od , tedy podle 2. verze Dirichletova principu existuje na úsečce AB bod, který patří k průmětům alespoň devíti kružnic. Pak je přímka procházející tímto bodem a kolmá k průměru požadovaná, protíná všech těchto devět kružnic. ■ $D$ $D$ $D$ $50>8\cdot D$ $D$

Variace a zobecnění

Jeden způsob, jak zobecnit Dirichletův princip, jej rozšiřuje na reálná čísla [18] .

Pokud králíci sežrali kg trávy, tak alespoň jeden králík snědl alespoň kg trávy. $m$ $n$ $n\over m$

Důsledky [18] .

Pokud je součet čísel větší, pak alespoň jedno z těchto čísel je větší $n$ $S$ ${\frac {S}{n}}.$
Pokud je aritmetický průměr několika čísel větší než , pak alespoň jedno z těchto čísel je větší $A$ $A.$

Existuje zobecnění Dirichletova principu na případ nekonečných množin : neexistuje žádná injekce výkonnější množiny do méně výkonné [19] .

Příklady [19] .

Pokud je v konečné sadě buněk obsažen nekonečný počet holubů, pak alespoň jedna buňka bude obsahovat více než jednoho holuba. Navíc je snadné ukázat, že alespoň v jedné buňce bude nekonečný počet holubů.
Pokud je v spočitatelných krabicích obsažena nespočetná sada holubů , pak alespoň jedna buňka bude obsahovat více než jednu holubici. Navíc lze prokázat, že alespoň v jedné buňce bude nespočetné množství holubů.

Výše uvedené zobecnění je založeno například na důkazu Siegelova lemmatu navrženého Axelem Thue [20] .

Řada moderních zobecnění Dirichletova principu je uvedena v článku Ramsey Theory .

Dirichletův pravděpodobnostní princip. Předpokládejme, že králíci sedí v náhodných klecích z a králíci sedí v náhodných klecích ze stejných klecí. Označte pravděpodobností, že králík s králíkem sedí v nějaké kleci.

m

k

n

k

p(m,n,k)

Pokud pro některé pevné , tak pro .

m\cdot n>k^{1+\varepsilon }

\varepsilon >0

p(m,n,k)\to 1

k\to \infty

Pokud pro některé pevné , tak pro .

m\cdot n<k^{1-\varepsilon }

\varepsilon >0

p(m,n,k)\to 0

k\to \infty

Poznámky

↑ Andreev a kol., 1997 , s. 3.
↑ V němčině se tento výrok nazývá „princip krabice“ ( německy: schubfachprinzip )
↑ 1 2 Uspensky, V. A. Předmluva k matematice [sborník článků]. - Petrohrad. : LLC "Obchodní a vydavatelský dům Amphora", 2015. - S. 336-338. — 474 s. — (Populární věda, č. 12). - ISBN 978-5-367-03606-0 .
↑ Rittaud, Benoît; Heeffer, Albrecht (2014). „Princip rozškatulkování, dvě století před Dirichletem“ . Matematický zpravodaj . 36 (2): 27-29. DOI : 10.1007/s00283-013-9389-1 . HDL : 1854/LU-411526 . MR 3207654 . Archivováno z originálu dne 25. 12. 2021 . Získáno 2021-10-01 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ Jeff Miller, Peter Flor, Gunnar Berg, Julio González Cabillon . Princip Pigeonhole Archivováno 12. února 2010 na Wayback Machine // Jeff Miller (ed.) Nejstarší známá použití některých slov z matematiky Archivováno 4. března 2009 na Wayback Machine . Elektronický dokument, staženo 11. listopadu 2006
↑ Mat. encyklopedie, 1982 .
↑ Brualdi, Richard A. (2010), Introductory Combinatorics (5. ed.), Prentice Hall , s. 70, ISBN 978-0-13-602040-0
↑ Alfutová N. B., Ustinov A. V., 2009 , s. 17.
↑ Rue, Juanjo. Věčný poutník // Umění počítat. Kombinatorika a výčet (kapitola 3). - M. : De Agostini, 2014. - S. 87. - 144 s. — (Svět matematiky: ve 45 svazcích, svazek 34). - ISBN 978-5-9774-0729-8 .
↑ Foxford .
↑ Duran, Antonio. Poezie čísel. Fajn a matematika. - M. : De Agostini, 2014. - S. 57. - 160 s. — (Svět matematiky: ve 45 svazcích, svazek 27). — ISBN 978-5-9774-0722-9 .
↑ Alfutová N. B., Ustinov A. V., 2009 , s. 19.
↑ Alfutová N. B., Ustinov A. V., 2009 , s. 17-20.
↑ Aigner, Ziegler, 2006 .
↑ Andreev a kol., 1997 .
↑ Andreev a kol., 1997 , s. 13-16.
↑ Andreev a kol., 1997 , s. čtrnáct.
↑ 1 2 Andreev a kol., 1997 , str. 16-18.
↑ 12 Francis Su . Princip rozškatulkování . Získáno 3. října 2021. Archivováno z originálu dne 3. října 2021. (neurčitý)
↑ čtvrtek , A. (1909), Über Annäherungswerte algebraischer Zahlen , Journal für die reine und angewandte Mathematik T. 1909 (135): 284–305, ISSN 0075-4102 , doi : 10.1515,5 < 291resolver. .uni-goettingen.de/purl?PPN243919689_0135 > Archivováno 30. října 2020 na Wayback Machine

Literatura

Aigner M. , Ziegler G. Dirichletův princip a dvojí počítání () kapitola 22) // Důkazy z knihy . Nejlepší důkaz od dob Euklida až po současnost. — M .: Mir, 2006. — 256 s. — ISBN 5-03-003690-3 .
Alfutova N. B., Ustinov A. V. Algebra a teorie čísel. Sbírka úloh pro matematické školy. - 3. vydání, Rev. přidat .. - M . : MTSNMO, 2009. - 336 s. - ISBN 978-5-94057-550-4 .
Andreev A. A., Gorelov G. N., Lyulev A. I., Savin A. N. Dirichletův princip. Vzdělávací vydání. - Samara: Pythagoras, 1997. - 21 s. - (Řada A: Matematika. Vydání 1).
Glibichuk A. A., Dainyak A. B., Ilyinsky D. G., Kupavsky A. B., Raigorodsky A. M., Skopenkov A. B., Chernov A. A. Prvky diskrétní matematiky v problémech. - M. : MTSNMO, 2016. - S. 12-14. — 174 str. — ISBN 978-5-4439-3024-4 .
Dirichletův princip, krabice // Mathematical Encyclopedia (v 5 svazcích). - M .: Sovětská encyklopedie , 1982. - T. 2. - S. 182.
Znak E. I. Rozdělení celočíselných svazů a Dirichletův princip // Matematické vzdělávání . - 2015. - Vydání. 19 (třetí série) . - S. 241-248 .

Odkazy

Boltyansky V. Šest zajíců v pěti klecích // Kvant . - 1977. - č. 2. - S. 17-20, 37, 42.
Bugaenko V. O. Matematický kroužek. 9. třída Lekce číslo 2. Dirichletův princip . Datum přístupu: 18. listopadu 2020. (neurčitý)
Dirichletův princip . Staženo: 30. března 2020. (neurčitý)

Slovníky a encyklopedie	velká čínština Britannica (online)