חידות לוגיות

Trianglie je poněkud zvláštní země ležící na samostatném velkém ostrově. Žádná cesta zde není slepá, ale pokračuje stále dál a každá křižovatka je ve tvaru písmene Y.
Mladý princ této země se jednoho dne rozhodl, že se vydá na průzkum své vlasti. Osedlal svého věrného koně a chtěl vyrazit. V tom ale přiběhla jeho matka královna: "Ale synáčku, co když zabloudíš a nenajdeš cestu zpátky?". "Neměj strach, matko", odpověděl princ, "na každé druhé křižovatce se dám vpravo a jinak vlevo. Tak mám jistotu, že se dříve či později dostanu zpět do paláce."
Má princ pravdu?

Show/hide solution:

Princův výrok je pravdivý.
Shrňme si předpoklady o trianglii do matematického vyjádření. Cesty tvoří rovinný graf, kde každý vrchol (křižovatka) je stupně tři (vedou do něho tři hrany = cesty). Počet cest a křižovatek je konečný. Žádná cesta není slepá.
Z toho vyplývá, že pokud by se neměl dostat zpět do výchozího bodu, musí skončit někde na nekonečné smyčce (která tento bod neobsahuje).
Sporem: Pokud se na konci jeho cesty nevyskytuje nekonečná smyčka a žádná cesta není slepá, tak musí postupně vyčerpat všechny různé kombinace, kterými se dá jedna křižovatka projít. Dá se do ní vejít třemi cestami a pokaždé s jiným pravidlem (jít vlevo nebo jít vpravo) - tzn. 6 kombinací (konečný počet). Pokud se kombinace v daném vrcholu zopakuje, pak jsme se dostali do smyčky, což je spor.
Takže na konci každé cesty je nekonečná smyčka. Nechť tedy sporem počáteční úsek cesty (a tedy i výchozí bod) leží mimo tuto smyčku. To znamená, že existuje křižovatka, kterou jsme se na tuto smyčku napojili. Nekonečná smyčka je tvořena střídavým odbočováním vlevo a vpravo (ze zadání). Když se podíváme na bod napojení na smyčku, tak neexistuje způsob, jak se na ni napojit, abych ji hned v dalším kroce neopustil na další křižovatce (při dodržení pravidla střídání směrů). To je spor a tedy celá cesta (včetně výchozího bodu) leží na uzavřené nekonečné smyčce.

» גלריה » חידות לוגיות 010011010000100011