Na mozek
Přihlásit se
Na mozek (7/8) · 10:42

Hlavolam - Počítání cest Počítání cest v mřížce

Řekněme, že máme mřížku šest krát šest. Mám ji tady nakreslenou. Jeden, dva, tři, čtyři, pět, šest. Jeden, dva, tři, čtyři, pět, šest. A začneme v levém horním rohu. Takže tady. A náš cíl je dostat se do pravého dolního rohu. Chceme se dostat támhle do té hvězdy. Ale můžeme se hýbat jenom do dvou směrů. Můžeme jít doprava. Nebo můžeme jít dolů. Nesmíme jít šikmo. Nesmíme nahoru. Nesmíme doleva. Takže nikdy nesmíme jít šikmo. A každý krok nás trošku přiblíží k cílové hvězdě. Taky se nesmíme vracet. A moje otázka je: kolika různými způsoby se můžeme dostat ze startu na konec? To je úloha. Teď můžete video pozastavit a pokusit se ji vyřešit. A až odpauzujete, zkusím pomaličku ukázat, jak se dá řešit. A můžete mě zastavit kdykoli budete chtít. Můžete brát jednotlivé kroky jako tipy. Můžeme se na to podívat tak, že začneme od těch jednoduchých míst. Pojďme spočítat, kolika způsoby můžu jít odsud do každé buňky mezi startem a cílem, a možná nám to pomůže spočítat počet cest do konce. Vyberu si hezkou barvu. Kolika způsoby můžu jít ze startu do támhleté buňky? Můžu to udělat jenom jedním způsobem, ne? Můžu jít jenom tudy, přímo doprava. Je jenom jeden způsob. Napíšu si to sem. Jenom jeden způsob. A kolika způsoby se můžu dostat třeba sem? Zase jenom jedním způsobem. Můžu jít jenom přímo dolů. Vždyť nesmím třeba jít doprava, dolů, a pak doleva. Jít doleva se nesmí. Každý krok mě musí posunout blíž k cíli. Takže to vypadá, že jsme s tím trošku pokročili. Kolika způsoby se můžu dostat do téhle buňky? Můžu jít tady doprava. A pak můžu jít ještě jednou doprava. A to je vlastně jediný způsob jak se sem můžu dostat, ne? Jestli jdu dolů, nesmím se nikdy vrátit zpátky nahoru. Takže je jenom jeden způsob jak tam dojít. Analogicky je jenom jeden způsob jak jít tam. Jenom přímo. Je jenom jeden způsob jak dojít sem. Jeden způsob jak dojít sem. Je to vlastně tak trochu symetrické. Tím myslím, když jdu přímo doprava, je to to samé, jako když jdu přímo dolů. Takže taky je jenom jeden způsob. Jenom můžu jít přímo dolů. Jeden způsob. Jeden způsob. Jeden způsob. To bychom měli. Teď zkusíme trochu zajímavější buňku. Kolika způsoby se můžu dostat sem? Pojďme si to tentokrát nakreslit. Můžeme jít buď dolů a doprava, nebo doprava a dolů. Takže jsou dva způsoby jak se dostat do téhle buňky. OK. Tady bylo jednoduché všechny způsoby spočítat, protože jich není hodně. Ale možná jste si už všimli zajímavé pravidelnosti. Když mám buňku tady, pár jich nakreslím... Nakreslím to takhle. A takhle. A řekněme, že tohle je nějaká libovolná buňka úplně kdekoliv na téhle mřížce. Nemusí to ani být mřížka šest na šest. Může to být mřížka n na n. Můžeme tuhle úlohu řešit na mřížce 100 na 100. Ale potom bychom v tomhle videu dlouho dělali všechnu tu matematiku. Ale podívejme se, kolika způsoby se můžu dostat do téhle buňky Řekněme, že vím, že je N způsobů, jak se dostat sem, a M způsobů (ne N) -- M způsobů, jak se dostat do téhle buňky. Kolika způsoby se potom můžu dostat sem? Jediný způsob, jak se dostat do téhle buňky -- a nakreslím to jinou barvou -- jediný způsob, jak se sem dostat podle pravidel je buď jít přímo dolů, nebo jít přímo doprava. Můžeme tedy jít buď dolů z téhle buňky, nebo doprava z téhle buňky. Kolika způsoby se tedy celkem můžeme dostat sem? Jediné cesty, které sem vedou, jsou buď dolů odsud, a těchto cest je přesně N. Je N způsobů, jak se dostat do téhle buňky, a pak do téhle. A pak je M způsobů, jak se dostat do téhle buňky, a pak z ní přejít sem. Takže téhle buňce -- nebo téhle krabičce -- říkám tomu pořád buňka, možná protože můj mozek je fixovaný na Excel... Je N plus M způsobů, jak se sem dostat. Snad je to vidět. Protože jsou jenom dva způsoby, jak se sem dostat přímo: buď odsud, nebo odsud. A říkám, že sem vede N různých cest. Takže ze všech cest co vedou sem jich N vede nejdřív sem. A analogicky tuhle buňku. A to bylo před chvílí vidět. Dva se rovná jedna plus jedna. Takže jsou dva způsoby, jak se tam dostat. Podíváme se ještě jednou, jestli tahle úvaha je správná. Jenom abyste tomuhle opravdu věřili, aby to nevypadalo jako spadlé z nebe. Mělo by to dávat smysl. Takže kolika způsoby můžeme dojít sem? Podle toho, co jsem před chvílí řekl, bychom měli sečíst 1 a 2, a dostat 3. Ale podívejme se, jestli to funguje. Takže bychom mohli jít nejdřív úplně doprava. To je jedna. Potom tohle bude druhá. Pak bych mohl jít dolů a tudy. Tři. A všimněte si, že z těch tří cest co sem vedou, jedna vede odsud, a zbylé dvě vedou z téhle buňky. Vzhledem k tomu, čeho jsme si všimli, to dává smysl. Tak pojďme vyplnit tenhle čtvereček. Vyplňme tenhle čtvereček. Tohle bude jedna plus dva se rovná tři. Pojďme vyplnit -- změním barvy aby to bylo trochu zajímavější. Tohle je jedna plus tři se rovná čtyři. Tři plus tři je šest. Tři plus jedna jsou čtyři. A můžete si všimnout symetrie podél téhle diagonály. OK? Tady je tři a tři. Čtyři a čtyři. A jestli jste už viděli video o binomických koeficientech nebo o Pascalově trojúhelníku, měli byste si začít uvědomovat pravidelnost, nebo nějaká známá čísla, co tady jsou. Takže co je tohle? Tohle je pět. A tenhle čtverec obsahuje spoustu zajímavých věcí. Tady jsou všude jedničky. Tady je jedna, dva, tři, čtyři, pět, šest. Šest, že ano? Jedna plus pět. Tak. Čtyři, pět, šest. Šest plus čtyři je 10. Šest plus čtyři je 10. 10 plus 5 je 15. 15 plus 6 je 21. 10 plus 10 je 20. 10 plus 5 je 15. 21. Takže tohle je 35. 35. 70. 35 plus 21 je 56. 35 plus 21 je 56. 56 plus 70 je 126. A nakonec 126 plus 126 je 252. Udělám to jinou barvou. Takže tady je 200, že? Jo, 252 způsobů, jak se odsud dostat sem. Tohle byla docela pěkná úloha na hledání struktury. A mohli bychom to vyplnit. Mohli bychom to vlastně udělat pro libovolné N krát M. Nemusí to ani být N krát M. Mohl bych tu úlohu zadat tak, abychom zjistili kolika způsoby se dá dostat sem? A pořád by šla vyřešit. Jakmile je vidět tahle struktura, stačí jenom sčítání ke spočítání výsledku. Kdybychom tohle měli dělat jednu cestu po druhé, 252 cest by trvalo strašně dlouho. Mohlo by to vyplýtvat všechen váš čas. Ale děje se tu něco zajímavého. Jestli jste viděli video o binomických koeficientech, všimnete si, že tohle jsou binomická čísla. Něco přikreslím a možná si toho všimnete. Tohle je vzhledem k téhle úloze jenom bonus. Už je vyřešená. Jestli cíl byl jenom tohle spočítat, a nebyl najít propojení s jinou matematikou, můžete teď přestat sledovat. Ale ukážu teď něco pěkného. Řekněme, že chceme zjistit x plus y na ntou. A tohle jsme několikrát dělali ve videích o Pascalově trojúhelníku a o binomických koeficientech. Ale chci ukázat, že tady máme přesně to samé. Tohle je možná dokonce jednodušší způsob jak to udělat, než použít Pascalův trojúhelník. I když je to vlastně přesně to samé. Jestli napíšeme 1, x, x, x na druhou, x na třetí, x na čtvrtou, x na pátou. Tyhle mocniny přijdou na horní stranu toho čtverce. Ale chápu, že mi dochází místo. Teď se napíše 1, y, y na druhou, y na třetí, y na čtvrtou, y na pátou. A kdybych řekl "Kolik je x plus y třeba na čtvrtou?", můžeme si říct "OK, x plus y na čtvrtou bude vlastně x na čtvrtou plus něco, něco, něco, něco, spousta výrazů, až nakonec y na čtvrtou, a všechno mezi tím. Tak jak říkáme x na čtvrtou až do y na čtvrtou, to bude tahle diagonála. Nakreslím tuhle diagonálu. Takže tahle diagonála. A tahle čísla nám vpodstatě řeknou koeficienty. A nejen to. Dokonce nám řeknou i směs koeficientů. Co tím myslím? Něco tady smažu, ať mám místo. Tohle je bonus nad tuhle úlohu. Úloha už je vyřešená. Takže tohle můžu všechno smazat. Takže chceme zjistit x plus y na čtvrtou. A stačí nám jenom -- a nechám vás si ještě hrát s touhle mřížkou, abyste si všimli všech těch pravidelností, které jsou v každém řádku a sloupci a každé diagonále... Ale když chceme spočítat x plus y na čtvrtou, nebo vlastně tohle je x na čtvrtou. Nebo bychom mohli říct x na čtvrtou. Jedno x na čtvrtou krát jedna, což je jedna x na čtvrtou, plus čtyři krát x na třetí, krát y. OK? To je jenom tohle. Pak můžeme říct, plus šest x na druhou y na druhou. A pak jsme na plus čtyři x y na třetí. A nakonec plus y na čtvrtou krát jenom jedna. A mohli byste říct: "To je úžasné, Sale, jak tohle fungovalo?" A dá se nad tím uvažovat ta, že když násobíme tohle x plus y na čtvrtou-- a je zajímavé si to vyzkoušet jestli se jednou budete nudit --je ve skutečnosti šest způsobů jak tam dostat výraz x na druhou y na druhou. Uvidíte to, když to všechno pronásobíte. A to jsme tady udělali trochu v té intuici za videi o binomické větě. Je šest způsobů jak se dostat sem, což je ten samý problém, jako ta úloha, co jsem dal předtím. Kolika způsoby můžeme dosáhnout tohohle čtverečku? Zjistili jsme, že je šest způsobů. Doufám, že to bylo trochu zajímavé.
video