Как перевезти гопников и философов с одного берега на другой
Олимпиадная задачка для старшеклассников. Но справитесь ли с ней вы?
Это кавер-версия задачи про волка, козу и капусту — классическую задачу на алгоритмическое мышление. Она очень простая для разработчиков, и если вы можете решить её с первого раза, можете гордиться собой — только 1 человек из 10 решает эту задачу правильно с первого раза.
Зачем уметь решать такие задачи: помогает в составлении сортировочных алгоритмов и успешно проходить собеседования в ИТ-компаниях. Также важно уметь обосновывать свой ход мыслей.
Ситуация. На одном берегу реки находятся шесть человек: три гопника и три философа. Пока что они ведут непринужденные беседы об экзистенциальном, но все они должны будут рано или поздно оказаться на другом берегу.
Есть одна лодка, в которую могут поместиться только два человека, но философы управлять лодкой не умеют, а гопники умеют. Также нельзя оставлять на одном берегу философов больше, чем гопников, потому что тогда философы взорвут мозг гопникам разговорами о природе вещей. Как переправить всех через реку?
Для первой поездки есть пять вариантов:
- один гопник — не подходит, потому что на берегу философов становится больше и они взорвут мозг;
- два гопника — не подходит по той же причине;
- один или два философа — тоже нет, потому что они не умеют управлять лодкой;
- философ и гопник — единственный вариант, который остаётся.
Значит, первым рейсом пара «философ-гопник» отправляется на другой берег:
Теперь лодку надо как-то отправить назад. Но так как философ не умеет ей управлять, то он остаётся на берегу, а гопник — возвращается. Философы не взрывают никому мозг:
Теперь прикинем варианты следующего рейса. Мы не можем отправить двух гопников, иначе философы останутся в большинстве, и настанет на левом берегу полный экзистенциализм.
Поэтому снова на тот берег уплывают философ с гопником. Причём гопник высаживает философа, но сам из лодки не вылезает — если так не сделать, то он останется с двумя философами на том берегу и они увлекут разговорами об идеях вещей:
Таким образом, у нас на том берегу сидят два философа, а на этом — один философ и три гопника, на которых он вряд ли сможет воздействовать силой дискурса:
Теперь нам нужно сделать выбор, кто поедет на этот раз. Можно отправить снова философа и гопника, но тогда на том берегу окажутся три философа. И безопасно перевезти остальных гопников поодиночке уже не получится — философы всегда будут в большинстве.
Значит, остаётся только один вариант: отправить в путь двух гопников. В итоге на том берегу всех будет поровну и всё пройдёт спокойно:
Но лодку надо как-то отправить на другой берег. Нельзя разместить на ней одного гопника, потому что второй останется в меньшинстве среди философов. Двум гопникам ехать обратно тоже не вариант, потому что они только что прибыли.
Поэтому назад отправляются философ и гопник:
Теперь единственный безопасный вариант — отправить на тот берег двух гопников:
Назад отправим одного гопника. Чтобы не выходить из лодки, он позовёт в неё философа (например, фразой «Что вы думаете о солипсизме?») и вернётся с ним обратно на тот берег:
Точно так же забираем оставшегося философа:
И в итоге вся компания оказывается на том берегу, бездонное небо — над головой, а нравственный закон — внутри:
Источник
Зарядка для ума: как переправить семью через реку?
Двое взрослых и двое детей хотят переправиться через реку.
Они смастерили плот, но он может выдержать либо одного взрослого, либо пару детей.
Сколько переправ потребуется, чтобы всех перевезти на другой берег?
Ответ
Плот необходимо переправить как минимум девять раз.
Возможно, ваше решение будет отличаться, но вот один из вариантов. Мы предположим, что все находятся на ближнем берегу и хотят переправиться на дальний.
Если взрослый переправится на дальний берег, то там уже должен находиться ребенок, который переправит плот назад (если только это не сделает взрослый, но в этом случае поездка будет потрачена впустую).
Решение будет возможно лишь в том случае, если в первых двух путешествиях на плоту будут только дети. Оба ребенка переправляются на другой берег, один из них остается там, а второй возвращает плот.
В третьем путешествии на другую сторону переправляется взрослый, а в четвертом ожидавший на другом берегу ребенок возвращается назад с плотом. Итак, после четырех поездок один взрослый находится на другом берегу, все остальные — на этом.
Затем все повторяется аналогичным образом, и к восьмому путешествию оба взрослых будут на другом берегу, а оба ребенка — на этом. На девятый раз на другой берег переправятся оба ребенка.
Загадка взята из проекта NRICH университета Кембриджа. Подробнее на сайте Today Programme.
Источник
"Волк, коза и капуста". "Крестьянская задачка" настолько гениальная, что никто не замечает её нелогичности в некоторых местах.
А их в ней как минимум две. И эти несостыковки сразу бы заставили забыть. обычные задачки. Но для этой, они каким-то образом служат усилителями интереса.
Во-первых, сразу скажу, что у неё два решения. Но это не главное. Но всё по порядку.
Давайте освежим память.
Волк, коза и капуста.
Крестьянину нужно перевезти через реку волка, козу и капусту. Но в лодке может поместиться только крестьянин, а с ним или один волк, или одна коза, или только капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевез свой груз крестьянин?
Итак, все правильно решили? Крестьянин сначала перевёз козу и вернулся. А зачем? Что он теперь перевозить собрался?
Правильно, капусту. И не совсем.
Вот тут-то и возникают два варианта решения этой задачки. А в хороших задачах вариант решения должен быть один. Но этого никто не замечает.
РЕШЕНИЕ.
Вариант 1.
Шаг 1. Перевозим козу.
Шаг 2. Возвращаемся.
Шаг 3. Перевозим волка.
Шаг 4. Забираем козу и возвращаемся.
Шаг 5. Оставляем козу и перевозим капусту.
Шаг 6. Возвращаемся.
Шаг 7. Перевозим козу.
Вариант 2.
Шаг 1. Перевозим козу.
Шаг 2. Возвращаемся.
Шаг 3. Перевозим капусту.
Шаг 4. Возвращаемся с козой.
Шаг 5. Оставляем козу и перевозим волка.
Шаг 6. Возвращаемся
Шаг 7. Перевозим козу.
Варианты не слишком отличаются, но их все же два.
А теперь рассмотрим ещё одну несостыковку.
Ручной волк.
Что больше всего расходится с реальностью в условии задачи, так это про волка. Что это за волк такой? И как часто крестьяне с волком на верёвочке и козой с капустой спокойно прогуливались раньше по дорогам. Я не читал у классиков.
Волк при первом же случае готов наброситься на козу, но спокоен при человеке. Ручной волк, который согласно поговорке "как его не корми всегда смотрит в лес" — нормальное явление?
Это если бы в задачке звучало так : "На берёзе росло пять яблок.." Или так: " На пальме висело девять ананасов. "
На пальмах тоже ананасы не растут. А растут они так:
И сдается мне, что задачка эта пришла к нам совсем не из наших крестьянских хозяйств. Скорее всего так оно и есть. А крестьянина в задачке придумали у нас потом.
А унас должен был быть медведь. Но для лодки он слишком большой.
А вот как звучит задачка в иностранных источниках:
И никакого крестьянина. Какой-то абстрагированный "один человек". Может дрессировщик. Но не нужно уточнять и на этом заострять.
Оказывается, существуют другие вариации этой задачки, где фигурируют волк, овца и капуста или лиса, курица и зерно . И даже лиса, гусь и бобы . Или совсем экзотическое — пантера, свинья и овсянка.
Но вот почему-то "волк, коза и капуста"зашагали по просторам наших умов.
И еще одна несостыковочка — лодку крестьянин не отвез обратно. Нехорошо как-то. Но возможно ему она понадобится, когда он будет возвращаться со следующими необычными персонажами.
И ещё одна — как крестьянин узнал, что лодка с ним, козой и капустой потонет. Да наши крестьяне могли перевезти за один раз в одной лодке кого-угодно. Он скорее так бы задачку решил, чем туда-сюда плавать.
Минутка здоровья.
Упражнение для памяти "Коза, волк, капуста".
Источник
И снова переправа
Вам нужно переправить через реку с помощью одного плота семью (мать, отца, 2-х дочерей и 2-х сыновей) и полицейского с заключенным.
Правила:
1. На плоту могут одновременно перемещаться максимум 2 человека.
2. Папе не разрешается находиться с дочерьми без присутствия матери.
3. Маме не разрешается находиться с сыновьями без присутствия отца.
4. Заключённого нельзя оставлять без полицейского ни с одним из членов семьи.
5. Управлять плотом могут только полицейский и родители.
Ответ: Вот решение:
1. Переправляются полицейский и заключенный, полицейский возвращается назад;
2. Переправляются полицейский и дочь, полицейский с заключенным возвращаются назад;
3. Переправляются мать и вторая дочь, мать возвращается назад;
4. Переправляются отец и мать, отец возвращается назад;
5. Переправляются полицейский и преступник, мать возвращается назад;
6. Переправляются отец и мать, отец возвращается назад;
7. Переправляются отец и сын, полицейский и заключенный возвращаются назад;
8. Переправляются полицейский и второй сын, полицейский возвращается назад;
9. Переправляются полицейский и заключенный.
Есть в решении один интересный момент — заключенный остается в последнем действии один на берегу
Комментарии
Оставлен ках о Чт, 07/08/2010 — 15:16
1. Переправляются полицейский с заключенным — полицейский возвращается.
2. Переправляются полицейский с папой — папа вовзращается.
3. Переправляются папа с сыном — папа возвращается.
4. Переправляется папа со вторым сыном — папа возвращается.
5. Переправляются папа с мамой — мама возвращается.
6 и 7 Переправляются мама и дочки.
На две ходки меньше, но заключенный опять остается один 😉
Оставлен Александр Ср, 09/29/2010 — 06:50
Так не получиться, по условиям задачи 3 пункт не выполняеться, остаёться один сын с мамой, также проваливаеться и 6 пункт, остаёться на противоположном берегу дочь с папой. Так что минимум 9 ходов на решение задачи.
Оставлен yp9i Ср, 05/18/2011 — 13:32
Ладно короче слушайте решение) долго сегодня мучался но решил
1) Полицейский перевезя бандита на правый берег возвращается за дочкой на левый
2)Переправив дочку на правый берег забирает бандита и едут на левый
3)Далее Мама с дочкой переправляются на правый берег,после чего Мама возвращается на левый(в итоге на правом 2 дочери)
4)Мама и Папа плывут на правый берег где остается мама с дочками а папа возвращается на левый берег
5)На правый берег переправляются Полицейский и бандит,на левый берег уезжает Мама(слева получаем — мама,папа,сыновья,лодка справа- бандит,мент и дочери)
6)Мама и Папа едут на правый берег и остается Мама, а Папа едет на левый берег.
7)Папа забирает сына и едет на правый берег и остаются там.Полицейский с бандитом едут на левый берег.
8)Оставив бандита на левом берег, полицейский забирает сына и увозит его на правый берег.Затем возвращается за бандитом.
Оставлен Гость Вс, 10/16/2011 — 19:54
переправляются отец и мать
полицейский и зак
и дети
Оставлен =+= Чт, 07/22/2010 — 10:04
1 папа перевозит сыновей по 1,а потом возвращается
2 мама перевозит дочерей по 1,а потом возвращается
3папа перевозит маму,а потом возвращается
4полицейский перевозит заключенного ,а мать возвращается
5 мама перевозит папу,или на оборот папа перевозит маму
Оставлен Ванёк Пнд, 03/14/2011 — 14:11
Тут не соблюдено то, что мать или отец не имеют право оставаться с детьми, протиположного пола.
Оставлен Гость Пнд, 06/06/2011 — 18:26
да не могут сыновья оставаться наедине с мамой и дочери наедине с папой.
Оставлен =+= Чт, 07/22/2010 — 10:12
в коменте что я написал ниже не 5 а 9 пунктов,сорри,за сыновьями и дочками возвращались по 2 раза,значит 9 пунктов,но по моему всёравно получилось правильно))
Оставлен Гость Сб, 09/18/2010 — 21:30
залюченный остается один не только в конце но, и в начале
Оставлен Гость Сб, 10/09/2010 — 16:03
1. Переправляются папа и мама, папа возвращается
2. Папа с сыном, возвращается папа с мамой
3. Папа со вторым сыном, возвращяется папа
4. Папа с мамой, возвращается мама
5. Полицейский с заключенным, возвращается папа
6. Папа с мамой, возвращается мама
7. Мама с дочкой, возвращается мама с папой
8. Мама с дочкой, возвращается мама
9. Мама с папой
Оставлен Гость Пнд, 06/06/2011 — 18:24
папа не может быть с дочерьми без мамы
Оставлен Гость Пнд, 11/01/2010 — 08:21
> Есть в решении один интересный момент — заключенный остается в последнем действии один на берегу
И в первом тоже. Но это не противоречит условиям задачи. Если бы задача была бы на здравый смысл, то не хотел бы я жить в семье с извращенными папой и мамой.
Оставлен Ag Сб, 11/06/2010 — 12:33
Я думаю так:
1. На плоту переправляются дочь и сын, сын возвращается.
2. Затем Полицейский и бандит, дочь возвращается.
3. Затем сын и дочь, сын возвращается.
4. Отец и мать, дочь возвращается.
5. Сын и дочь, сын возвращается.
6. Сын и сын, сын возвращается.
7. Сын и дочь.
Все условия соблюдены, меньше 9 шагов и бандит под присмотром полицейского.))
Оставлен хм. Пнд, 12/06/2010 — 21:20
5. Управлять плотом могут только полицейский и родители.
Это условие не соблюдено.
Оставлен Гость Ср, 12/22/2010 — 09:49
В условии нет обязательства одного заключенного не оставлять, зачет тому кто догадался полицейского и заключенного разъединить,я сначала ответил как «Гость в Сб, 10/09/2010 — 22:03», а потом нашел вариант после просмотра подсказки:
1.Полицейский и заключенный переправились, обратно полицейский.
2.Полицейский и папа переправились, обратно папа.
3.Папа и мама переправились, обратно мама.
4.Мама и 1-ая дочь переправились, обратно мама и папа.
5.Мама и 2-ая дочь переправились, обратно мама.
6.Папа и мама переправились, обратно папа.
7.Папа и 1-ый сын переправились, обратно папа и мама.
8.Папа и 2-ой сын переправились, обратно папа.
9.Папа и мама переправились.
Оставлен Гость Чт, 12/23/2010 — 21:02
так не может быть, т.к. не выполняется 3-е условие.
Оставлен Гость Сб, 02/12/2011 — 20:45
1. сын везет дочь
2. сын возвращается
3. сын везет 2 дочь
4. сын возвращается
6. отец везет мать
7. отец возвращатся
8. сын везет отца
9. сын возвращается
10.сын везет 2 сына
11.сын возвращается
12. полицейский везет сына
13. полицейский возвращается
14. полицейский везет преспупника
тож вариант D
Оставлен Гость Чт, 02/24/2011 — 12:52
Нельзя так, дети не могут управлять плотом.
Оставлен Andy Пнд, 05/09/2011 — 16:10
Сразу говорю — остальные комменты не читал, так как это запутывает.. вот моя версия — переправляются:
1. Полицейский и зак., обратно полицейский;
2. Полицейский и отец, обратно отец;
3. Отец и сын-1, обратно отец;
4. Отец и сын-2, обратно отец;
5. Отец и мать, обратно мать;
6. Мать и дочь-1, обратно мать;
7. Мать и дочь-2, все на другом берегу.
(Кстати в условии не сказано, что заключенному нельзя оставаться без полицейского. В первом действии зак. тоже остается один на другом берегу.)
Оставлен Гость Пнд, 06/06/2011 — 18:21
Мать нельзя оставлять с сыновьями
Оставлен Гость Пнд, 05/21/2012 — 16:52
В смысле отца с дочерью)) На 6 ходе.
есть даже в flash-варианте, только не знаю как здесь расместить
Оставлен Гость Чт, 05/12/2011 — 15:31
Это решение неправилно потому что преступника нельзя оставить с мирным жителем одного без полицейского и дочь не может быть одна
Оставлен Кристина Пт, 12/09/2011 — 13:24
??0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 0
. —>.
м. м. м. м. м. м. м. м. м. м. м. м. м. м. м. м. м. м. м
о. о. о. о. о. о. о. о. о. о. о. о. о. о. о. о. о. о. о
д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д
д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д
с. с. с. с. с. с. с. с. с. с. с. с. с. с. с. с. с. с. с
с. с. с. с. с. с. с. с. с. с. с. с. с. с. с. с. с. с. с
п. п. п. п. п. п. п. п. п. п. п. п. п. п. п. п. п. п. п
з. з. з. з. з. з. з. з. з. з. з. з. з. з. з. з. з. з. з
Это вот моё решение! =)
15 «трушных» шагов (ну или 8 «вашенских» туды-сюды)
Три столбика = берег1 – река – берег2.
Ни в одном столбике Вы не сможете найти такого, чтобы:
а) чтобы мать была с сыновьями без отца,
б) чтобы отец был с дочерями без матери,
в) чтобы заключенный был хоть с одним из членов семьи без полицейского (и даже чтоб вообще оставался один, как ужесточили условия некоторые «недалекие» люди здесь)
м = мать
о = отец
д = дочь
д = дочь
с = сын
с = сын
п = полицейский
з = заключенный
А вот СКАЗКА для тех, кому проще рассказ понять, чем математику…
Сначала мать захотела перевезти на другой берег дочерей. Для этого надо отца куда нить «сбагрить», поэтому Шаг1 – мать отвозит отца на другой берег, и возвращается – Шаг2. Потом мать берётся отвозить дочерей. Сначала отвозит первую дочь – Шаг3, но она не может ее оставить с отцом на том берегу без себя, поэтому она возвращается за второй дочерью прихватив отца с собой – Шаг4. Наконец, мать вторую дочь отвозит на другой берег, оставив отца с сыновьями на первом берегу – Шаг5. Возвращается мать думать об остальных – Шаг6 и придумывает перебросить следующими на другой берег заключенного с полицейским, и т.к. его нельзя оставлять без охраны, то обратно с того берега плот надо будет везти ей либо отцу, выбирает себя и потому просит отца перевезти её на тот берег – Шаг7. После возвращения отца (Шаг8) по плану матери заключенный и полицейский перебираются через реку (Шаг9) и мать возвращается (Шаг10), чтобы передать эстафету отцу. Отец принимает эстафету и отвозит, наконец, мать отдыхать (Шаг11). Затем отец возвращается за первым сыном (Шаг12) и перевозит его (Шаг13), но оставить его с матерью нельзя без себя, поэтому мать на обратном пути прихватывает с собой (Шаг14). Сбрасывает мать с плота и перевозит второго своего (а может, и не его вовсе) сына (Шаг15). Эх, хотел было отец оставить мать-тиранку на далеком берегу, да вспомнил, что с дочерями то он не может быть без неё и потому пришлось ему вернуться за ней (Шаг16) и забрать на тот берег ко всем остальным перебравшимся (Шаг17).
Источник