This website uses cookies to ensure you get the best experience on the website.
111101010000011101
101110111111
010101
001110111011100011
100010001101
110001
 ¤ קונטקט ¤ 
 ¤ אפשרויות ¤ 
 ¤ עדכון ¤ 
 ¤ Stop potratům ¤ 
Rychlá řešení dlouho bolí
Čekáte-li nečekané dítě
 ¤ HEX מונה ¤ 
3 0 1 b c
 ¤ תעודה ¤ 
Valid HTML 4.01 Valid CSS Valid RSS 2.0

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

Zamčené dveře - difficulty 6.4 (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
 ¤ עשירייה ¤ 
 ¤ חיפוש ¤ 
 ¤ Biblenet ¤ 
פסוק:
חזרה למעלה
Copyright © 2004-2020 Tomáš Vala
אופטימלי עבור Firefox
מפת האתר | גירסה ניידת | A+ A A-