Cesko.wiki Vlk, koza a zelí
Author
Albert FloresDetail 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. +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.