Princip Dirichlet: problémy s řešeními

V matematice existuje mnoho principů. Některé z nich jsou poměrně jednoduché a srozumitelné i pro začátečníky a některé vyžadují určité vysvětlení a důkazy. Nicméně jsou všechny velmi účinné a lze je snadno aplikovat v praxi. Jedním z nich je princip Dirichlet (známý také jako princip holub / králík). Toto je poměrně jednoduché tvrzení, které může pomoci při řešení mnoha matematických problémů.

Dějiny

Tento princip byl formulován čestným německým matematikem Johannem Dirichlethem v roce 1834. Dnes se používá v kombinátori, stejně jako v matematické fyzice. Překlad z původního německého jazyka zní jako "princip krabic". Vědec provedl výzkum s králíky a kontejnery. Ukázal, že pokud uvedeme 5 králíků do 7 kontejnerů, pak alespoň v jednom kontejneru by bylo 5/7 od jednoho zvířete. Králík však nelze rozdělit na části, proto bude alespoň jedna buňka prázdná (5/7 je celé číslo). Stejným způsobem, v opačném směru, pokud je 7 králíků a 5 krabiček, pak alespoň jeden z nich má 2 králíky (7/5 je 2 neporušené). Počínaje tímto tvrzením se matematice podařilo formulovat princip, který po mnoho let zajišťuje úspěšné řešení problémů v matematice.

Moderní znění a důkaz

Dnes existuje několik různých formulací tohoto principu. Nejjednodušší a nejjednodušší znamená, že je nemožné zasadit 8 králíků ve 3 klecích tak, aby každá z nich neměla více než 2. Vědečtější a složitější formulace vysvětlující princip Dirichlet říká: pokud jsou v buňkách k buňky k + 1 králíci, pak alespoň Nejméně jedna buňka bude obsahovat více než jedno zajíc. A pokud jsou k-1 zajíci v buňkách k, pak alespoň 1 buňka bude obsahovat méně než jedno zajíc. Důkaz tohoto tvrzení je poměrně jednoduchý, takže mluvit, v rozporu. Pokud předpokládáme, že v každé buňce je méně zajíců než k-1 / k, potom k z buněk zajíců je menší než k * k-1 / k = k-1, což je v rozporu s počátečními podmínkami.

Ve skutečnosti takový jednoduchý a srozumitelný princip velmi usnadňuje řešení problémů v matematice a důkaz mnoha pracných vět. Je třeba jen vzít v úvahu, že zajíci a buňky lze snadno nahradit matematickými objekty a objekty (čísla, body, segmenty, postavy atd.).

Další formulace

Někdy úkoly na principu Dirichlet nejsou tak jednoduché a zřejmé jako u zvířat v krabicích. Je nutné převést tento princip na matematické množiny, abychom našli řešení. V takovém případě se můžete spolehnout na jinou, složitější formulaci.

Pokud namapujeme množinu S obsahující d + 1 prvky do množiny R s množinou d prvků, pak dva prvky ze sady S budou mít stejný obrázek.

Ačkoli moderní GEF v matematice kladou na studenty tvůrčí požadavky a nabízí nestandardní možnosti, řešení přes Dirichletovo tvrzení není vždy tak jednoduché a přímočaré. Někdy je velmi obtížné určit, kterou hodnotu považovat za zvíře, a která jako klec a jak to, že dvě zvířata v jedné kleci pomáhají vyřešit tento problém. A pokud se nám to podaří zjistit, je stále nemožné určit, ve které konkrétní buňce bude objekt. To znamená, že můžete prostě dokázat existenci takové buňky, ale nemůžete ji konkretizovat.

Příkladové číslo 1. Geometrie

Moderní příklady řešení problémů ukazují, že dokonalé různé matematické objekty mohou fungovat jako zvířata a buňky.

Úkol

Řádek k prochází rovinou trojúhelníku ABC, ale neprotíná žádný z jeho vrcholů. Je nutné prokázat, že nemůže překročit své tři strany.

Řešení

Představte si, jak linka k rozděluje trojúhelník na dvě roviny, nazveme je s1 a s2. Předpokládáme, že s1 a s2 jsou otevřené, to znamená, že neobsahují řadu k. No, teď je čas použít princip Dirichlet. Úkoly s řešením mohou ukázat, že v moderních podmínkách králíci a buňky znamenají různé objekty. Takže namísto zajíců nahrazujeme vrcholy trojúhelníku a namísto buněk - polovinu letadla. Vzhledem k tomu, že nakreslená čára k neprotíná žádný z vrcholů, každá z nich je v jedné nebo jiné rovině. Protože v trojúhelníku jsou tři vrcholy a máme pouze dvě roviny (s1 a s2), jedna z nich bude obsahovat dva vrcholy. Předpokládejme, že se jedná o vrcholy A a B a jsou v polovině roviny s2 (tj. Leží na stejné straně k). V tomto případě segment AB neprotíná přímku k. To znamená, že v trojúhelníku je strana, která k neprotíná.

Alternativní řešení

V tomto problému jsme předpokládali, že body A a B jsou ve stejné rovině, ale Dirichletův princip nenaznačuje určitou buňku, takže bychom mohli také poukázat na to, že vrcholy C a B nebo A a C byly umístěny ve stejné rovině. nezáleží na které straně trojúhelníku se protíná přímka k. Proto je tento princip ideální pro jeho řešení.

Příklad č. 2. Geometrie

Úkol

Ve středu rovnostranného trojúhelníku ABC (ve kterém AB = BC = AC = 1) bylo umístěno 5 bodů. Je nutné prokázat, že dva z nich jsou umístěny ve vzdálenosti menší než 0,5.

Řešení

Pokud nakreslíte středové čáry v pravém trojúhelníku ABC, rozdělí se na 4 malé pravé trojúhelníky s boky ½ = 0,5. Předpokládejme, že tyto trojúhelníky jsou buňky a body uvnitř nich jsou králíci. Ukazuje se, že máme 5 králíků a 4 buňky, proto v jednom z nich budou nejméně dva králíci. Vzhledem k tomu, že body nejsou vrcholy (protože jsou umístěny uvnitř trojúhelníku ABC a nikoli na jedné straně), budou umístěny uvnitř malých čísel. V důsledku toho bude vzdálenost mezi nimi menší než 0,5 (protože velikost segmentu uvnitř trojúhelníku nikdy nepřesahuje velikost jeho největší strany).

Příklad číslo 3. Combinatorics

V ostatních oborech lze také úspěšně aplikovat princip Dirichlet: kombinatorika a matematická fyzika jsou již dlouho založeny na řešení problémů.

Úkol

Například okolo zaobleného stolu jsou vlajky m různých zemí ve stejné vzdálenosti od sebe a m zastupitelé z každé země sedí u stolu, každý z nich je umístěn vedle vlajky někoho jiného. Je třeba prokázat, že s určitým otočením stolu budou nejméně dva zástupci blízko jejich vlajek.

Řešení

Ukazuje se, že existují m-1 způsoby, jak rozšířit tabulku tak, aby se změnilo vzájemné uspořádání zástupců a vlajek (pokud vyloučíme počáteční umístění tabulky), ale zůstávají m zástupci.

Aplikujeme Dirichletovo tvrzení na řešení a naznačujeme, že zástupci jsou králíci a určité pozice stolu při rotaci jsou buňky. V takovém případě je třeba analogicky porovnat umístění zástupce vedle příslušné vlajky a vyplněných buněk. To znamená, že pozitivní výsledek (1 zástupce je umístěn poblíž jeho vlajky) je ekvivalentní k výsledku "králík je v kleci". Chápeme, že máme jednu buňku méně, než je potřeba (m-1), což znamená, že jeden z nich bude mít alespoň 2 králíky. Současně není vyloučena situace, že nějaká klec bude prázdná (ani jeden zástupce se neshoduje s vlajkou), ale v nějaké kleci budou dva, tři nebo ještě více králíků (dva, tři nebo více zástupců se shodují s vlajkami). Takže s určitou rotací se alespoň dva zástupci ocitnou blízko svých vlajek (alespoň dva králíci padnou do jedné buňky).

Začátek řešení takového problému je důležité pochopit, že počáteční pozice je také buňka, ale podle stavu problému je zjevně prázdná, takže celkově snížíme o 1 (m-1).

Příklad číslo 4. Teorie čísel

Dirichletův princip v teorii čísel je také nesmírně důležitý.

Úkol

Předpokládejme, že na kusu notebooku v kleci studentem náhodně u uzlů buněk uhodili 5 bodů. Je nutné prokázat, že alespoň jeden segment s vrcholy v těchto bodech prochází uzlem buňky.

Řešení

Nejprve musíte na listu notebooku zobrazit souřadný systém, jehož základ se nachází v jednom z uzlů. Osy souřadnicového systému se shodují s čarami sítě a strana buňky se považuje za jeden segment. Ukazuje se, že všech 5 označených bodů bude v systému a jejich souřadnice budou pouze celé číslo (sudé nebo liché). Získáme tedy 4 možnosti souřadnic: (sudý, sudý), (lichý, vyrovnaný), (sudý, lichý) a (lichý, lichý). Takže 2 z 5 bodů budou odpovídat jedné variantě. Pokud se podíváte na situaci z pozice Dirichlet, pak musíte označit body jako zajíci a koordináty - jako buňky. Dostaneme 5 ptáků s jedním kamenem a 4 klecemi, v jednom z nich bude nejméně 2 zvířata. Předpokládejme, že jde o body P a A se souřadnicemi (x ₄ , y ₃ ) a (x ₅ , y ₆ ). Na středu segmentu, který spojuje tyto dva vrcholy, budou mít souřadnice ((x ₄ + x ₅ ) / 2), (y ₃ + y ₆ ) / 2)), které budou celá za podmínek odpovídající parity x ₄ a x _5, y ₃ a y ₆ . Ukazuje se, že střed segmentu je umístěn v buněčném uzlu.

Příklad číslo 5

Docela mnoho úkolů s různou složitostí lze vyřešit prostřednictvím principu Dirichlet. Problémy s řešeními různých matematických a logických otázek se často opírají o tento princip.

Úkol

Na přímé cestě vykopali malé příčné drážky. Vzdálenost mezi všemi drážkami je stejná a rovná Ö2 m. Je nutné dokázat, že bez ohledu na šířku drážky bude člověk, který prochází podél silnice v intervalu 1 m, jednou spadne do jednoho z nich.

Řešení

Aby se usnadnilo řešení, je třeba si představit, že silnice může být "navinuta" na kružnici o délce Ö2 metrů. Ukazuje se, že všechny drážky budou sloučeny do dvou protilehlých a kroky osoby budou zobrazeny ve formě oblouku rovného 1 m. Potřebujeme postupně označit všechny kroky, dokud jeden z nich není v oblouku, který označuje drážku, bez ohledu na to, jakou délku k oblouk (šířka drážky). Samozřejmě je zřejmé, že pokud by člověk kráčel na vzdálenost menší než k, pak by se dříve nebo později dostal do příkopu. Koneckonců, člověk nedokáže překročit vzdálenost k, jestliže jeho délka kroku je menší než k. Takže musíme najít dvě stopy, jejichž vzdálenost nepřesáhne hodnotu k. K tomu by bylo vhodné použít princip Dirichlet. My mentálně rozdělíme celý kruh na oblouky menší než k a budeme je považovat za buňky. Předpokládejme, že n je jich. Předpokládejme, že počet kroků je větší než počet oblouků (n + m), ačkoli žádné dva kroky se neshodují kvůli iracionalitě čísla Ö2, pak podle principu Dirichlet bude alespoň jedna z buněk obsahovat více než jeden krok. A protože délka oblouku je menší než k, bude vzdálenost mezi kroky menší. Tak jsme zjistili, jaké kroky jsou nezbytné pro důkaz.

Zobecnění zásady

Materiály na matematice kromě standardních (jednoduchých a ne velmi) formulací obsahují také jednu generalizovanou, která se používá k identifikaci více než dvou podobných objektů. Ona argumentuje, že jestliže dm + 1 králíci jsou umístěny v d buňkách, pak alespoň m + 1 králíci budou ve stejné buňce.

Příklad č. 6. Zobecnění

Úkol

Obdélník s rozsahem 5 x 6 buněk (30 buněk), jen stínovaný 19. Je možné najít čtverec o ploše 2 x 2 buňky, ve které budou naneseny alespoň tři vrstvy?

Řešení

Naše číslo musí být rozděleno na 6 bloků po 5 buňkách. Na základě výroku Dirichlet bude v jednom z nich vymalováno alespoň 4 buňky (19/6 = 4). Pak na jednom z čtverců o ploše 4 buňky, umístěné v jednom z bloků, budou naneseny alespoň 3 buňky.

Příkladové číslo 7

Třída, ve které je 25 osob. Ze všech 3 náhodně vybraných studentů budou dva přátelé. Je nutné prokázat, že ve třídě je školák, který má více než 11 přátel.

Dvě řešení

Za prvé, vezmeme dvě děti, které nejsou navzájem přátelské (protože jestliže jsou všichni přátelé, každá trojka bude mít tři kamarády a každý student bude s 24 dalšími přáteli). Zbývajících 23 spolužáků bude přátelé s jedním z našich dvou, protože jinak by byla troika bez přátel (a to je v rozporu s původním stavem problému). Ukazuje se, že jeden ze dvou studentů bude přátelé s alespoň 12 studenty. V tomto případě jsou studenti králíci a výrazy "přátelé nebo ne" jsou buňky. Máme 23 zvířat a pouze 2 klece. V jednom z nich je tedy nejméně 23/2 = 11,5, tj. 12 králíků. To znamená, že jeden z 2 vybraných studentů bude přátelé s nejméně 12 spolužáky (nebo dokonce více). Samozřejmě existují i ​​jiné způsoby řešení tohoto problému, ale je to jedna z nejrozumnějších a nejpohodlnějších.