This website uses cookies to store your personal settings, to personalize advertisements (by hosting webzdarma.cz) and to analyze visit rate. By using this web you agree with it.
111101101100111001
110111000111
101001
010010000110010101
100100111001
001000
 ¤ Contact ¤ 
 ¤ Options ¤ 
 ¤ Actualization ¤ 
 ¤ Stop potratům ¤ 
Rychlá řešení dlouho bolí
Čekáte-li nečekané dítě
 ¤ HEX Counter ¤ 
2 e 2 2 b
 ¤ Certificate ¤ 
Valid HTML 4.01 Valid CSS Valid RSS 2.0

» Gallery » Logical puzzles  110010011100101001 

Zamčené dveře - difficulty 6.1 (former difficulty 4)
Průmyslový objekt je střežen soukromou agenturou. Hlídač má za úkol každý den projít celý objekt a pozamykat všechny dveře. Byla to pro něj hrozná otrava, a tak si to chtěl trochu oživit. Rozhodl se, že postupně projde všemi dveřmi a po projití je ihned za sebou zamkne (tzn. každými dveřmi projde právě jednou).
Půdorys domu je na následujícím obrázku. Proškrknutí zdí značí dveře ven nebo do sousední místnosti.
Půdorys
Jakou cestu zvolil, aby se mu to podařilo?
Poznámka: Po zamčení všech dveří nemusel nutně skončit vně objektu. Šlo mu jen o to si to vyzkoušet.
Hlídač nemá šanci vysněný úkol splnit.
Půjdeme na to přes teorii grafů. Jednotlivé místnosti označme vrcholy a spojíme je mezi sebou hranou právě tehdy, když mezi nimi vedou dveře. Dveře vedoucí ven z budovy budeme směřovat do jednoho venkovního uzlu. Abychom postihli dvoje dveře vedoucí ven a zachovali definici grafu (mezi každými dvěma vrcholy nejvýše jedna hrana), přidáme meziuzel pro druhou cestu ven. Každý vrchol je popsán číslem, kolik do něj vede hran (tzv. stupeň vrcholu). Výsledný graf viz obrázek.
Nalezení řešení znamená, že graf se dá nakreslit jedním tahem, přičemž nemusíme nutně začínat a končit ve stejném uzlu (tzv. otevřený Eulerův tah). V teorii grafů pak platí věta:
Graf je otevřeně Eulerovský (dá se nakreslit otevřeným Eulerovým tahem) právě tehdy, když je souvislý a má právě 2 vrcholy lichého stupně.
Důkaz této věty není nijak složitý. Náš graf má 4 vrcholy lichého stupně, a proto se nedá nakreslit otevřeným Eulerovým tahem.
Difficulty:12345678910
 ¤ TOP ¤ 
 ¤ Searching ¤ 
 ¤ Biblenet ¤ 
Verse:
Back to top
Copyright © 2004-2019 Tomáš Vala
Optimized for Firefox
Website map | Mobile version | A+ A A-