Variace na sedm mostů

22. března 2014 v 13:59 | Mlok |  Matematika
Sedm mostů města Königsbergu - slavný matematický problém spojovaný především se jménem pana Eulera jsem vám tu představila už před nějakou dobou. Dneska vám ukážu jednu z mnoha variací na tento proslavený problém. Základní princip a fungování problému bylo vysvětleno v minulém článku (Prokleté mosty města Königsbergu), proto upozorňuji, že kdo ho nečetl, bude se nejspíš trochu ztrácet - k základním pojmům jako je Eulerovský tah ap. už se totiž nebudu znovu vracet. No, pojďme se tedy podívat na novou situaci v Königsbergu:
Jak můžete na historické mapě výše vidět, severní břeh ovládá zelený princ, na jižním břehu se usídlil jeho bratr, červený princ. Na malém ostrově uprostřed je městská hospoda, na větším ostrově pak máme bikupství.
Následují tři malé problémy, které všechny vycházejí z toho původního. schválně si zkuste, zda se vám je podaří vyřešit.


Pro lepší přehled pomůže zjednodušený graf.

V Königsbergu nebylo neobvyklé, že se měšťani, po pár hodinách strávených v hospodě, rozhodli udělat si malou procházku a přejít všechny mosty (aniž by po jednom přešli dvakrát). Po návratu do hostince pro další občerstvení obvykle tvrdili, že se jim to podařilo, nicméně za denního světla svůj úspěch nikdy nebyli schopní zopakovat.

Osmý most
Zelený princ, který vzdělaně analyzoval situaci mostů, si uvědomil, že přejít všech sedm mostů najednou je nemožné. Rozhodl se proto postavit osmý most tak, aby mohl večer začít svou cestu ze svého zámku, přejít všechny mosty a skončit v hospodě, kde by mohl oslavovat své vítězství. Samozřejmě zelený princ postaví svůj most tak, aby červený princ nemohl jeho úspěch kopírovat.
Kde postaví zelený princ osmý most?

Devátý most
Červený princ, rozzuřený úspěchem svého bratra, se rozhodl že postaví devátý most tak, aby mu umožnil přejít všechny mosty najednou - začínaje ve svém zámku- a skončit v hostinci, kde se bude moci vysmát zelenému princi do tváře. Jako extra pomstu červený princ naplánoval, že stavbou devátého mostu svému bratru zabrání v přechodu všech mostů na jeho večerní trase.
Kde postaví červený princ devátý most?

Desátý most
Biskup, který ze svého ostrova celé šílenství a stavění mostů po celou dobu sledoval, je zhnusen chováním obou princů. Rozhodne se proto nechat vystavět desátý a poslední most, který umožní všem obyvatelům Königsbergu přejít všech deset mostů najednou a skončit opět ve svých domech.
Kde postaví biskup desátý most?

ŘEŠENÍ:

Osmý most
Eulerovský tah je možný, vychází-li z přesně dvou nebo žádného uzlu lichý počet spojnic. Cesta musí začít v zeleném uzlu a končit ve žlutém - tyto dva uzly tedy musí mít lichý počet spojnic. Protože v grafu jsou jen čtyři uzly, řešení je velmi jednoduché - stačí propojit fialový a červený uzel dalším mostem, tak aby měli oba tyto uzly sudý počet spojnic.
Devátý most
Určit pozici devátého mostu je jednudoché, jakmilie je postaven osmý most. Žlutý uzel zůstává koncem trasy (zůstává tedy lichým uzlem), fialový uzel zůstává nepozměněn. Stačí tedy prohodit pozici červeného a zeleného uzlu - z červeného udělat lichý uzel (tak aby tam cesta začínala) a ze zeleného sudý (tím bude mít zelený princ znemožněnou cestu).
Desátý most
Přání umožnit úplně všem aby mohli přejít všechny mosty a ještě se vrátit do svého výchozího bodu vyžaduje trochu jiné řešení než oba předchozí problémy. Jedná se o Eulerovský okruh - je potřeba aby všechny uzly měly sudou podstatu. Zelený i fialový uzel už mají sudý počet spojnic, stačí proto propojit červeného prince a hostinec tak, že všechny uzly se stanou sudými.

A jak teda město nakonec po tomto šíleném stavění vypadá? Protože jsou všechny tyto případy pouhá fikce, bohužel vám nemůžu ukázat pravou mapu z té doby. Mosty jsou ale naznačeny na této mapě, která se dochovala:

Použity informace z en.wikipedia.org
Mapy a ilustrační obrázky převzaty z historického archivu města Koenigsbergu.
 


Komentáře

1 Borůvka Borůvka | Web | 22. března 2014 v 15:23 | Reagovat

Tohle je perfektní. I když můj mozek nebyl vytvořen ke tvoření matematických problémů, tvoje rubrika Matematika se mi fakt líbí! Chválím. :)

2 Piks Piks | Web | 22. března 2014 v 16:27 | Reagovat

Toto je dôvod prečo milujem matematiku :D je tak krásne zložitá, zábavná a jej problémy vidím všade okolo seba :)
V hospode naberajú všetky matematické úlohy nový rozmer vďaka čomu sa vždy dajú vyriešiť :D (ako na to prišli spomínaní mešťania :D )

3 randolf randolf | Web | 17. června 2015 v 17:07 | Reagovat

jsem nadšená z Vašeho stylu :-|

Nový komentář

Přihlásit se
  Ještě nemáte vlastní web? Můžete si jej zdarma založit na Blog.cz.