Mosty

Text zadání:

Vyznačte jednoduché a dvojité čáry (= mosty) mezi kroužky s čísly (= ostrovy). Z každého ostrova vede tolik mostů, kolik udává číslo na něm. Mosty musí vést vodorovně nebo svisle a nesmí se křižovat. Všechny ostrovy navíc musí být propojeny navzájem, tj. z existuje nějaká cesta z libovolného ostrova na každý jiný.

Příklad zadání a řešení:

Ukázka postupu řešení:

Úvaha číslo jedna: První ostrov v druhém řádku mají napojovat 4 mosty. Nějaký sousedící ostrov vidíme pouze vpravo a dole. Mezi dvojicí ostrovů vedou nejvýše 2 mosty. Suma sumárum z tohoto ostrova doprava i dolů povedou dva mosty.

Úvaha číslo dva: Druhý ostrov v prvním řádku má napojovat 5 mostů. Nějaký sousedící ostrov vidíme vlevo, dole a vpravo. Mezi dvojicí ostrovů vedou nejvýše 2 mosty. Proto z tohoto ostrova doleva, dolů i doprava vede alespoň jeden most. Jinak by nám zůstalo 5 mostů a jen dva směry (tj. maximálně 4 mosty).

Analogickou úvahu můžeme udělat pro všechny další ostrovy s 5 mosty na okraji rastru (čtvrtý ostrov v prvním řádku, šestý ostrov ve druhém řádku, první ostrov v šestém řádku a první ostrov v desátém řádku).

Povšimněme si ještě jedné věci. Na třetí ostrov v první řádku po aplikaci výše uvedených úvah již byly napojeny oba požadované mosty. Tento ostrov je tedy „hotový“. Zavedeme užitečné značení toho faktu; ostrov, k němuž již nelze napojit další mosty si podbarvíme. (Týká se to i ostrova z prvního kroku.)

Právě proto, že třetí ostrov v prvním řádku je již „hotový“, zbývající mosty ze sousedních ostrovů musí být napojeny jinam. Napojíme tedy dvojité mosty od obou pětek v prvním řádku, a tím také tyto ostrovy a některé jejich sousedy dokončíme.

Vzhledem k uzavření posledního ostrova v prvním řádku, můžeme dokončit pětku pod ním. Dvojité mosty povedou doleva i dolů.

Druhý a pátý ostrov ve druhém řádku a první ostrov v pátém řádku již mají jediný volný směr, kam napojíme zbývající mosty.

Ještě jeden, třetí, nejpokročilejší způsob uvažování bych chtěl vyložit. Zaměříme se na první ostrov v sedmém řádku. Je to dvojka. Kdyby oba mosty z tohoto ostrova byly napojeny doprava, vzniklo by souostroví, dokončené, ale zároveň izolované od zbytku světa. A to pravidla zapovídají. Proto alespoň jeden most z prvního ostrova v sedmém řádku musí vést dolů.

V dalších krocích si již téměř bez výhrady vystačíme s nejjednodušším způsobem řešení. Budeme vyhledávat ostrovy, u nichž zbývá právě tolik směrů a mostů, kolik je potřeba k jednoznačnému napojení.

Nyní to jsou: čtvrtý ostrov¨ve třetím řádku (1), první ostrov ve čtvrtém řádku (3), první ostrov v osmém řádku (4) a první ostrov v jedenáctém řádku (2).

Přecijen ještě jednou jiný způsob řešení, je to „model 2“. Podíváme se na třetí ostrov v druhém řádku, je to dvojka. Doprava můžeme napojit nejvýše jeden ostrov, proto alespoň jeden most z tohoto ostrova bude napojen dolů. Podobně druhý ostrov v posledním řádku je trojka. Zbývají dva volné směry (na 3 mosty), proto na každou stranu napojíme alespoň jeden most.

Další skupina ostrovů k dokončení: třetí ostrov ve druhém řádku (2), poslední ostrov v pátém řádku (3), první ostrov v devátém řádku (4), první ostrov v desátém řádku (5) a druhý ostrov v posledním řádku (3).

Další dva ostrovy k dokončení: druhý ostrov v osmém řádku (4) a třetí ostrov v devátém řádku (4).

Další dva ostrovy k dokončení: druhý ostrov v šestém řádku (4) a pátý ostrov v devátém řádku (1).

A z jiného soudku: Druhý ostrov v devátém řádku (4) má ještě dva volné mosty, dolů můžeme napojit nejvýše jeden, proto alespoň jeden most musíme napojit doprava. Podobně třetí ostrov jedenáctém řádku (2) má ještě dva volné mosty, doleva můžeme napojit nejvýše jeden, a proto alespoň jeden most musíme napojit nahoru. A do třetice poslední ostrov v posledním řádku (2) má ještě dva volné mosty, nahoru můžeme napojit nejvýše jeden, a proto alespoň jeden most musíme napojit doleva.

Další dva ostrovy k dokončení: druhý ostrov v pátém řádku (3) a třetí ostrov v šestém řádku (5).

A z jiného soudku: čtvrtý ostrov v devátém řádku má tři mosty na dva směry, proto alespoň jeden most napojíme dolů a alespoň jeden nahoru.

A do třetice ona „nejpokročilejší“ technika: Třetí ostrov  v devátém řádku je čtyřka. Kdybychom z ní napojili dva mosty nahoru a dva vlevo, vznikla by izolovaná skupina pěti ostrovů. To nesmí nastat, a tak musíme alespoň jeden most napojit z tohoto ostrova dolů.

Další dva ostrovy k dokončení: čtvrtý ostrov v osmém řádku (4) a druhý ostrov v jedenáctém řádku (3).

A z jiného soudku: čtvrtý ostrov v pátém řádku (3) má tři volné most, nahoru můžeme napojit nejvýše jeden a zároveň doleva můžeme napojit také nejvýše jeden. Proto alespoň jeden most z tohoto ostrova musíme napojit dolů. Podobně čtvrtý ostrov v sedmém řádku (5) má ještě dva volné mosty, doprava můžeme napojit nejvýše jeden z nich. Proto musíme alespoň jeden most z tohoto ostrova napojit doleva.

Další tři ostrovy k dokončení: čtvrtý ostrov v šestém řádku (6), pátý ostrov v šestém řádku (1) a druhý ostrov v sedmém řádku (2).

Další ostrovy k dokončení: třetí ostrov v pátém řádku (2) a třetí ostrov v posledním řádku (4), pak třetí ostrov ve třetím řádku (3).

Poslední ostrovy k dokončení: čtvrtý ostrov v pátém řádku (3), čtvrtý ostrov v devátém řádku (3) a poslední ostrov v posledním řádku (2), pak poslední ostrov v sedmém řádku (3).

A je to!

zpět na seznam úloh