Hádanka o ragnarokuTED-Ed

„Neuvěříte, že nebesa padají, dokud kousek nespadne na vás.“ – M. Atwood, Svědectví Ragnarok, bájný konec světa, kdy obři, příšery a severští bohové bojují o budoucnost. Bohové s přehledem vítězili, dokud se nevynořil obří had Jörmungandr. Spolkl Valhallu, zkroutil se přes celou zem a pak se spojil do souvislého těla bez hlavy i ocasu. Když začal Valhallu trávit, ohlásil vyčerpaný Ódin, že má dostatek síly akorát na to, aby příšeru zasáhl jedním bleskem.

Pokud zvětšíte jeho úder bájným kladivem Mjölnirem, měl by masivního hada protít. Poběžíte super rychlostí podél hadího těla. Když pozvednete kladivo, Ódin ho zasáhne bleskem a Jörmungandra v daném místě rozetne. Poté dál poběžíte podél jeho těla, dokud nebudou všechny jeho části zničeny.

Nemůžete však přes jeden úsek běžet dvakrát, protože byste se propadli již rozervanou částí hadího těla. Můžete však opakovaně proběhnout místa, kde se jednotlivé části jeho těla kříží. Pokud jakoukoliv část vynecháte, Jörmungandr se pomocí magie zregeneruje, Ódinova poslední síla přijde nazmar a Valhalla padne jednou provždy. Jakou cestou se vydáte, abyste hada zničili? ZASTAVTE VIDEO, POKUD CHCETE NA ŘEŠENÍ PŘIJÍT SAMI.

ODPOVĚĎ ZA 2. ODPOVĚĎ ZA 1. Jedním z efektivních způsobů řešení problémů je zjednodušování. V tomto případě se můžeme zaměřit na dvě věci, které jsou pro nás podstatné: průsečíky a úseky hada mezi nimi. Nebo jak se jim říká v teorii grafů, uzly a hrany. Hrany jsou důležité, protože po nich se pohybujeme.

A uzly zase spojují hrany a právě na nich se musíme rozhodnout, kudy se vydat dál. Zjednodušením na uzly a hrany získáme všudypřítomný a významný matematický objekt známý jako graf nebo síť. Musíme jen zjistit, kudy se vydat. Matematici na to mají tzv. eulerovský tah, který každou hranu grafu využívá právě jednou. Místo abychom řešili cestu jako celek, zaměřme se na konkrétní uzel. V určitém momentu vašeho běhu na něj vstoupíte a pak z něj vystoupíte.

Tím nám odpadnou dvě hrany. Pokud na něj vstoupíte znovu, budete muset zase i vystoupit, k čemuž jsou zapotřebí další dvě hrany. Každý bod na vaší cestě tak bude mít hrany, které vždy tvoří pár. Jedna hrana v každém páru funguje jako vstup, další jako výstup. To znamená, že počet hran ústících z každého uzlu musí být sudý. Existují jen dvě výjimky: počáteční a koncový bod, kde můžete vystoupit bez vstupu a obráceně.

Když se znovu podíváme na síť vytvořenou hadem a na počet hran ústících z každého uzlu, všimneme si vzoru, který odpovídá tomu, co jsme právě viděli. Z každého uzlu vystupuje sudý počet hran, s výjimkou dvou. Jeden z nich tak musí být počátkem vaší cesty a druhý cílem. Pro zajímavost, jakákoliv síť, kde jsou přesně dva uzly s lichým počtem hran, obsahuje eulerovský tah. Totéž platí, pokud nemá žádné uzly s lichým počtem hran.

V tom případě tah začíná a končí v tom samém místě. Když už to všechno známe, vraťme se k původnímu grafu. Můžeme začít touto hranou a pak kličkovat cikcak tam a zpátky podél celého hada, až dorazíme na konec. Tohle je jen jedno z řešení. Pomáhá být systematický, určitě ale narazíte na spoustu dalších, když už víte, kde začít a skončit váš běh.

Ve vhodný moment tak kladivo zvednete do výše a Ódin na vás sešle svět zachraňující blesk. Pak poběžíte tak jako nikdy předtím. Pokud zvládnete tohle, severské bohy už určitě nic neporazí. A kdyby se něco takového k vám přece jen plížilo… no, to si necháme na jindy. Překlad: marysol www.videacesky.cz