Vlk, koza a zelí

Technology
12 hours ago
8
4
2
Avatar
Author
Albert Flores
...

Zadání

Na jednom břehu řeky stojí u člunu člověk, který má u sebe vlka, kozu a hlávku zelí. Jeho úkolem je přepravit vše přes řeku, ovšem do člunu se k němu vždy vejde jen jedna věc. +more A navíc nesmí nechat spolu samotnou kozu a zelí, protože by nehlídaná koza zelí sežrala, ani spolu nesmí nechat samotné vlka a kozu, protože nehlídaný vlk by sežral kozu.

Úkolem je vymyslet, jak to má provést.

Řešení

Jako první musí člověk převézt kozu, protože převezení vlka by znamenalo, že mezitím koza sežere zelí, a převezení zelí by znamenalo, že mezitím vlk sežere kozu.

Pak se vrátí s prázdným člunem a má na výběr, zda převeze zelí nebo vlka. Obě možnosti jsou možné a v důsledku mohou vést k řešení. +more Na první pohled to tak ale nevypadá: Pokud člověk převeze zelí a pak se bude chtít vrátit pro vlka, koza mezitím na cílovém břehu sežere zelí, pokud převeze vlka a pak se bude chtít vrátit pro zelí, sežere mezitím na cílovém břehu vlk kozu.

Trik je v tom, že poté, kdy je na cílovém břehu převozník s kozou a zelím (nebo vlkem), převeze kozu zpět, přestože se tím zdánlivě vzdaluje cíli (opět má na výchozím břehu dvě věci a na cílovém jen jednu). Na výchozím břehu pak naopak kozu vyloží a odveze za zelím (respektive za vlkem) vlka (respektive zelí).

Ty už může nechat na cílovém břehu nehlídané a s prázdným člunem se vrátí pro kozu.

Obě nejkratší řešení tak vyžadují sedm překonání řeky, čtyři tam a tři zpět.

Rozšíření

Varianty a kulturní rozšíření

Kromě formulace s vlkem, kozou a zelím existuje řada ekvivalentních formulací s jinými třemi objekty s analogickými vztahy, např. liška, husa a pytel fazolí; liška, kuře a obilí; liška, husa a kukuřice; jaguár, prase a ovesná kaše.

Varianta této klasické hádanky se objevuje i v seriálu Simpsonovi v dvacáté sérii v třinácté epizodě nazvané Gone Maggie Gone.

Pedagogické užití

Přestože lze úlohu zadat i žákům základní školy, kteří ji dokáží vyřešit prostým zkoušením, může být užitečná i při výuce na vysoké škole. Lze ji totiž vyjádřit jako problém z oboru dynamického programování, z oboru teorie grafů nebo z oboru celočíselného programování a následně na ní ilustrovat patřičné algoritmy z těchto oborů, které problém dokáží vyřešit.

Odkazy

Reference

Literatura

Kategorie:Hlavolamy

5 min read
Share this post:
Like it 8

Leave a Comment

Please, enter your name.
Please, provide a valid email address.
Please, enter your comment.
Enjoy this post? Join Cesko.wiki
Don’t forget to share it
Top