Převážení přes řeku

Převážení přes řeku je skupina logických úloh, ve kterých máme vždy skupinu, která se potřebuje dostat na druhou stranu řeky. K dispozici mají pouze malou loďku, do které se vejde jen omezený počet cestujících, a navíc je potřeba při přepravě dodržovat rozličná omezení, aby cestování dopadlo bez problémů.

Tyto úlohy se přímo nabízí k provedení naživo. Každý z účastníků představuje jednoho cestujícího, na louce vyznačíme řeku, a loďku můžeme udělat čistě symbolicky nebo použijeme třeba kolečka. Můžeme však samozřejmě také použít kostýmy, opravdovou loď a převážet přes opravdovou řeku.

Řešení úloh lze najít v mé knize Hlavolamikon.

Úlohy také využít pro ilustraci zajímavých informatických konceptů. To je rozebráno pro změnu v knize Jak to vyřešit? a stručně to ilustruje následující video:

Zadání úloh

Vlk, koza a zelí

Převozník chce převézt přes řeku hlávku zelí, kozu a vlka. Loďka je malá a hlávka zelí veliká, takže s převozníkem se do loďky vejde pouze jeden spolucestující. Nechá-li převozník na břehu samotnou kozu a zelí, koza zelí sežere. Nechá-li na břehu samotného vlka a kozu, vlk sežere kozu. Jak se může převozník dostat na druhý břeh i s celým nákladem?

Rodinka

Tatínek s dcerou a synem přijdou k řece. Není tam most, pouze převozník s loďkou. Do loďky se vejde buď jeden dospělý, nebo dvě děti. Jak se může rodinka dostat na druhou stranu? Převozník pochopitelně požaduje, aby mu loďku vrátili, tj. na konci celé operace musí být převozník u své lodi.

Kanibalové a misionáři

Tři misionáři se vydali na osvětovou misii a jako průvodce mají tři kanibaly. Potřebují překonat řeku, ovšem loďka uveze nejvýše dva lidi. Kanibalové zatím nejsou dostatečně poznamenáni misionářskou osvětou, takže pokud se kdykoli vyskytne na jednom místě více kanibalů než misionářů, budou misionáři snědeni. Jinak však kanibalové spolupracují a udělají, co jim misionáři řeknou. Jak se může celá skupina dostat na druhý břeh? Problém můžeme dále zkomplikovat. Co když umí pádlovat pouze jeden jeden z misionářů a jeden z kanibalů?

Žárliví manželé

Tři manželské páry vyrazily na výlet. Opět potřebují překonat řeku pomocí loďky, do které se vejdou nejvýše dva lidé. Problém tentokrát tkví v tom, že všichni manželé jsou děsně žárliví. Manžel nikdy nechce nechat svou ženu ve společnosti dalšího muže bez svého dozoru (a to ani kdyby u toho byli jiní lidé). Pokud by na výlet vyrazilo více párů, pak už se jim řeku za uvedené podmínky překonat nepodaří. Leda, že by byl uprostřed řeky ostrov nebo by se do loďky vešli alespoň 3 lidé…

Velká výprava

Tentokrát dorazila k řece opravdu zajímavá výprava: otec, matka, dva synové, dvě dcery, policista a zloděj. K dispozici je opět loď, která uveze dvě osoby. Navíc máme celou řadu omezení:

• Otec nemůže být sám ani s jednou dcerou bez přítomnosti matky.
• Matka nemůže být sama ani s jedním synem bez přítomnosti otce.
• Zloděj nesmí být s nikým z příslušníků rodiny bez přítomnosti policisty.
• Pouze otec, matka a policista umí pádlovat.

Zranění muži

Na závěr tu máme úlohu, ve které máme místo loďky most. Na jedné straně mostu jsou čtyři ranění muži. Je tma a most je rozbitý, takže po mostě mohou jít nanejvýš dva současně a potřebují k tomu baterku, kterou ovšem mají pouze jednu. Baterku nemohou házet. Míra zranění se liší, takže přechod mostu trvá každému muži jinou dobu: 5 min, 10 min, 20 min a 25 min. Pokud jdou dva společně, jdou samozřejmě tempem pomalejšího. Je docela jednoduché najít postup, jak se mohou všichni dostat na druhou stranu za 65 minut. Úkolem však je najít lepší řešení – jde to totiž i za 60 minut.