Kouzelníkův hlavolam - řešení



Úloha je ekvivalentní nalezení eulerovského tahu (nakreslení jedním tahem) v doplňkovém grafu. Ten vypadá následovně:



Jedna z vět teorie grafů říká, že v souvislém neorientovaném grafu existuje eulerovský tah právě tehdy, když graf obsahuje 0 nebo 2 vrcholy lichého stupně. (Stupeň vrcholu je počet hran, které do něj vedou.) Věta platí i pro tzv. multigrafy, ve kterých může mezi dvěma vrcholy vést i více hran, a to je náš případ. Když se dobře podíváte na červený graf, zjistíte, že obsahuje 4 vrcholy lichého stupně. Z toho plyne, že úloha nemá řešení a kouzelník si svoje tajemství zase nechá pro sebe.

Možná vás napadlo, že jsme šli trochu s kanónem na vrabce. Teorie grafů je složitá věc, nešlo by totéž vyjádřit i bez jejích termínů? Co uvedená věta vlastně říká? Stupeň vrcholu v místnosti odpovídá počtu dveří, které z ní vedou. A věta říká, že smíme mít nejvýše dvě místnosti, ze s lichým počtem dveří. Proč to tak musí být? Do místnosti, která má sudý počet dveří, řekněme 2k, musíme při naší cestě právě k-krát vstoupit a právě k-krát z ní vyjít. To znamená, že místnost s lichým počtem dveří může být jedině na začátku nebo na konci cesty. Ale náš dům má 3 místnosti s pěti dveřmi. Z toho je hned vidět, že taková cesta neexistuje. Však také základní pravidlo iluzionisty je uchvání triků v tajnosti. :-)

Special thanx goes to Martin Mareš. Připomínky posílejte mailem na adresu egg@matfyz.cz.
Můžete se vrátit zpět na homepage anebo tam, odkud jste přišli.