Převoznické-úlohy

Převoznické úlohy

Motivace

Koza, vlk a zelí je klasická matematická úloha, kterou poprvé publikoval Alkuin z Yorku asi v 8. století ve sbírce Úlohy k bystření mladíků. Jedno z jejích možných zadání:

Převozník chce převézt z jednoho břehu na druhý hlávku zelí, kozu a vlka. Do loďky s sebou může vzít buď zelí, nebo kozu, nebo vlka, ale víc se tam nevejde. Nechá-li na břehu hlávku zelí a kozu, koza zelí sežere. Nechá-li na břehu kozu a vlka, pak vlk sežere kozu. Přijdete na to, jak tedy převozník tuto situaci vyřeší?

V prvním kroku můžeme zkusit metodou pokus-omyl a „převážet“ jednotlivé pasažéry.

Tuto úlohu ale lze řešit i graficky. Nejprve se zamyslíme,

jaké stavy při převážení mohou nastat. Zjistíme, že všech možných uzlů je 16. Proč?

Protože máme 4 cestující (převozník, vlk, zelí a koza) a mohou nastat pouze 2 situace, buď daný

cestující na břehu je, nebo není. Máme tedy 24= 16.

Další postup, včetně dvou možných řešení, jsem vypsala ručně.

Příklad založený na podobném principu se jmenuje mniši a kanibalové.

Zadání může znít třeba takto:

Na prvním břehu řeky máme tři mnichy a tři kanibaly. Všechny musíme bezpečně dostat na druhý břeh

pomocí lodičky, bez převozníka. Dobrý pozor si musíme dát na počet osob na

jednotlivých březích. V případě, že by se na jednom břehu objevilo či zůstalo více kanibalů než mnichů, kanibalové mnicha sežerou. Zkuste najít postup, jak bezpečně tuto skupinu dostat přes řeku.

Řešení:

Tato úloha je velice podobná předchozímu příkladu a má také dvě řešení.

1. řešení:

Do loďky nastoupí kanibal a mnich, mnich se vrátí zpět a vystoupí.

Dva kanibalové jedou na druhý břeh a jeden z nich vystoupí, druhý dopraví loďku zpět k prvnímu břehu.

Kanibal vystoupí a na druhý břeh jedou dva mniši.

Jeden z mnichů na druhém břehu vystoupí a zpět jede mnich s kanibalem.

Zde kanibal vystoupí a vymění se s posledním mnichem na této

straně řeky.

Po přejetí na druhý břeh mniši vystoupí a nechají kanibala, aby postupně dovezl druhého a třetího kanibala a následně posledního.

2. řešení:

Do loďky nastoupí dva kanibalové.

Jeden se vrátí s loďkou a přiveze na druhý břeh třetího kanibala.

Jeden kanibal jede zpět, vystoupí a do loďky nastoupí dva mniši.

Jeden z mnichů na druhém břehu vystoupí a přenechá své místo kanibalovi.

Na prvním břehu kanibal vystoupí a vymění se s posledním mnichem.

Po přejetí na druhý břeh mniši vystoupí a nechají kanibala, aby postupně dovezl své zbylé přátele.

Při hledání na internetu jsem narazila na stránku http://www.plastelina.net, kde jsou tyto úlohy zpracovány formou hry. Tato verze pravděpodobně může žáky zaujmout a budou tak motivováni k jejímu vyřešení.