Волк, коза и капуста

Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект — или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту. В присутствии же крестьянина «никто никого не ест».

Как крестьянину перевезти на другой берег всё своё имущество в целости и сохранности?^[1][3]

Первым шагом решения должна быть перевозка козы, так как любой другой вариант приведёт к потере части имущества. Вернувшись, крестьянин перевозит капусту (или волка) на другой берег, а козу увозит обратно. Оставляя козу на первом берегу, крестьянин перевозит волка (или капусту) на другой берег, после чего возвращается, чтобы забрать козу^[9][10].

Головоломка принадлежит к числу задач о переправе^{[англ.][2][6]} (ferry-boat problems^[11], river-crossing puzzle), где задача состоит в том, чтобы перевезти набор предметов через реку с заданными ограничениями. В первом известном упоминании этой головоломки, в средневековом манускрипте Propositiones ad Acuendos Juvenes («Задачи для развития молодого ума»^[6]), имуществом крестьянина являются волк, коза и капуста. Существуют «косметические» вариации головоломки, в которых фигурируют волк, овца и капуста^{[12][7], p. 26}, лиса, курица и зерно^[13], лиса, гусь и бобы^[14], пантера, свинья и овсянка^[15]. Логика головоломки не меняется: есть три предмета A, B, C, таких, что нельзя оставить без присмотра A с B или B с C.

Головоломку можно обнаружить в фольклоре афроамериканцев, Камеруна, Островов Зелёного Мыса, Дании, Эфиопии, Ганы, Италии, Румынии, России, Шотландии, Судана, Уганды, Замбии, Зимбабве^{[7], pp. 26-27;[16]}. Головоломке присвоено обозначение H506.3 в указателе сюжетов Стита Томпсона и ATU 1579 в указателе сюжетов Аарне — Томпсона^[17].

В Европе широкую популярность задача получила после издания сборника занимательных задач, приписываемого Алкуину (лат. Propositiones ad Acuendos Juvenes, VIII век). Задача была любимой головоломкой Льюиса Кэрролла^[18] и многократно перепечатывалась в сборниках занимательной математики^{[6][7], p. 26.}.

В некоторых областях Африки были обнаружены вариации головоломки, в которых лодка может вместить в себя два объекта, помимо человека. Когда головоломка подобным образом ослаблена, можно ввести дополнительное ограничение, заключающееся в том, что никакие два объекта не могут быть оставлены на берегу вместе^{[7], p. 27.}.

• Задача о миссионерах и людоедах

• Олехник С. Н., Нестеренко Ю. В., Потапов М. К. Старинные занимательные задачи. — 2-е изд., испр. — М.: Наука, Главная редакция физико-математической литературы, 1988. — 160 с. — 700 000 экз. — ISBN 5-02-013759-6.
• У. Болл, Г. Коксетер. Математические эссе и развлечения = Mathematical Recreations and Essays. — М.: Мир, 1986.
• Б. А. Кордемский. Математическая смекалка. — Издание пятое, стереотипное. — М.: Государственное издательство физико-математической литературы, 1958.
• H. E. Dudeney. Good Old-Fashioned Challenging Puzzles. — Summersdale Publishers Ltd, 2007. — ISBN 1-84024-557-3. — ISBN 978-1-84024-557-8.
• W. W. Rouse Ball. Mathematical Recreations and Essays. — Sixth edition. — London: Macmillan, 1914. — 538 p.
• Владимир Белов. Головоломки из близкой дали  (неопр.). Компьютерра (11 января 2000). Архивировано 28 ноября 2015 года.

• Goat, Cabbage and Wolf Архивная копия от 26 сентября 2007 на Wayback Machine
• Шейнис Е. Волки, козы и капуста Архивная копия от 1 февраля 2016 на Wayback Machine // Наука и жизнь, 1998, № 4.
• Сухин И. Г. Задача «Волк, коза и капуста» Архивная копия от 3 февраля 2016 на Wayback Machine // Начальная школа, 2002, № 7, стр. 69-71.