Vlk, koza a zelí

Detail iluminace zobrazující muže s člunem, vlka, kozu a zelí (folio 89r pocházející ze 13. nebo 14. století).

Vlk, koza a zelí je klasický logistický hlavolam, jedna z úloh s překonáváním řeky. Její nejstarší písemné zaznamenání je z devátého století ve spise Úlohy k bystření mladíků, který je připisován Alkuinovi z Yorku.

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. 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í. 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

V tomto článku byl použit překlad textu z článku Fox, goose and bag of beans na anglické Wikipedii.

Literatura

• MAČÁK, Karel. Tři středověké sbírky matematických úloh. Praha: Prometheus, 2001. Dostupné online. ISBN 80-7196-215-5. Kapitola Akluin: Úlohy k bystření mladíků.