Dnes sa pri jednom dôkaze objavilo použitie niečoho takéhoto - môžete sa skúsiť zamyslieť nad tým, prečo to funguje. (Je to pomerne jednoduché, napriek tomu sa takéto jednoduché pozorovanie dá veľmi často využiť na dôkaz celkom užitočných vecí.)
Holubníkový princíp. Ak má nejaká množina $k$ prvkov a rozdelím ju na $n$ častí, pričom $n>k$, tak v niektorej z týchto častí budú aspoň dva prvky. (Ak mám $k$ krabičiek a do nich chcem rozdeliť $k+1$ objektov, tak v niektorej z krabičiek budú aspoň dva z nich.)
Niekedy sa hodí aj v silnejšej podobe: Ak by sme mali $n>k\cdot r$, tak vieme povedať, že v jednej z častí bude aspoň $(r+1)$ prvkov.
Spomínali ste, že ste sa takýmto niečím nestretli. (Aspoň väčšina z vás.) Na matfyze na to úplne nepochybne ešte veľakrát narazíte.
Skúsim tu spísať aspoň pár miest, kde sa o tom dá nájsť niečo viac. (Samozrejme, ak nájdete nejaké zaujímavé linky alebo literatúra aj vy, tak sem tiež môžete napísať.)
Holubníkový princíp (a.k.a. Dirichletov princíp)
Moderators: Martin Sleziak, Ludovit_Balko, Martin Niepel, Tibor Macko
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Holubníkový princíp (a.k.a. Dirichletov princíp)
Zopár liniek:
Ak ste sa na strednej škole venovali matematickým súťažiam, tak tam ste sa mohli s niečím takýmto stretnúť. Nie je asi teda prekvapivé, že v literatúre takéhoto typu sa s Dirichletovým princípom dá stretnúť pomerne bežne. V angličtine je veľa takejto literatúry. V slovenčine nájdete napríklad ŠMM 25 Dirichletov princíp. A kapitolu venovanú Dirichletovmu princípu nájdete aj v Hecht-Sklenáriková: Metódy riešenia matematických úloh alebo Larson: Metódy riešenia matematických problémov.
- Wikipédia: Pigeonhole principle. Niečo sa dá nájsť aj na českej Wikipédii.
- AoPS wiki: Pigeonhole principle
Ak ste sa na strednej škole venovali matematickým súťažiam, tak tam ste sa mohli s niečím takýmto stretnúť. Nie je asi teda prekvapivé, že v literatúre takéhoto typu sa s Dirichletovým princípom dá stretnúť pomerne bežne. V angličtine je veľa takejto literatúry. V slovenčine nájdete napríklad ŠMM 25 Dirichletov princíp. A kapitolu venovanú Dirichletovmu princípu nájdete aj v Hecht-Sklenáriková: Metódy riešenia matematických úloh alebo Larson: Metódy riešenia matematických problémov.