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.
110010110000111011
110011111111
101100
001010001111100010
100011000101
000001
 ¤ Contact ¤ 
 ¤ Options ¤ 
 ¤ Actualization ¤ 
 ¤ Stop potratům ¤ 
Rychlá řešení dlouho bolí
Čekáte-li nečekané dítě
 ¤ HEX Counter ¤ 
2 e 6 0 8
 ¤ Certificate ¤ 
Valid HTML 4.01 Valid CSS Valid RSS 2.0

» Gallery » Logical puzzles  110111011010000000 

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-