Переправы и разъезды
В задачах на переправы кто-то через что-то переправляется. В таких задачах принято (если явно не оговорено иного), что из подошедшей к берегу лодки все должны выйти на берег, даже тот, кто собирается плыть обратно. Иными словами, нельзя "выпрыгивать" и "выкидывать" что-то на берег.
Задач, в которых речь идет о переправах, очень много. Приведем два известных сюжета.
ПУТНИКИ И ДВУХМЕСТНАЯ ЛОДКА
Путник подошел к реке, по которой на лодке катались двое мальчиков. Как ему переправиться на другой берег и вернуть лодку детям, если лодка вмещает либо только одного взрослого, либо двоих детей? А как быть, если путников двое? Трое? Очень много?
РЕШЕНИЕ
Научимся сначала переправлять одного путника. Пусть он стоит на левом берегу и собирается переехать на правый. Сперва оба мальчика плывут на правый берег, один из мальчиков остается на правом берегу, а другой плывет на левый. Там он вылезает и ждет, пока путник переправится на правый берег. После чего мальчик, который был на правом берегу, садится в лодку и плывет за вторым мальчиком на левый берег.
Повторяя эти действия, можно переправить любое количество путников.
ВОЛК, КОЗА И КАПУСТА
Крестьянин направлялся домой вместе с волком, капустой и козой. Всю дорогу он следил, как бы волк не съел козу, а коза капусту. Наконец, он подошел в реке, около берега которой нашел лодку. В лодке может поместиться, кроме крестьянина, либо только коза, либо только капуста, либо только волк. Как крестьянину переправить зверей и капусту, чтобы никто никого (и ничего) в процессе не съел?
РЕШЕНИЕ
Сперва крестьянину придется перевезти козу (если взять волка, то коза съест капусту, а если взять капусту, то волк съест козу). Затем он оставляет козу пастись на противоположном берегу и возвращается к волку и капусте. Теперь крестьянин может забрать, например, волка и перевезти его на противоположный берег. Осталось вернуться за капустой, но нельзя же оставить волка наедине с козой! Поэтому козу придется забрать с собой обратно на исходный берег. Далее крестьянин оставляет ее еще немного погулять и перевозит капусту. А затем возвращается за козой.
Канатная дорога
К кабинке канатной дороги на гору подошли четверо с весами 50, 75, 75 и 100 кг. Смотрителя нет, а в автоматическом режиме кабинка ходит туда-сюда только с грузом от 110 до 260 кг (в частности, пустой не ходит), при условии, что пассажиров можно рассадить на две скамьи так, чтобы веса на скамьях отличались не более, чем на 30 кг. За какое наименьшее количество переездов они все смогут подняться на гору? (Переезд – движение кабинки вверх или вниз).
Начало формы
За какое наименьшее количество переездов они все смогут подняться на гору?
Конец формы
Решение задачи
Всех перевезти за одну поездку не удастся: 50+75+75+100>260. Ехать в первую поездку только двоим бессмысленно — им же придется и вернуться. Следовательно, в первый раз едут трое, и это люди весом 50 кг, 75 кг и 100 кг. Затем можно, например, спуститься тем, кто весит 50 кг и 75 кг. Затем вверх поднимаются оба весящие 75 кг. Вниз спускаются весящие 75 кг и 100 кг. И, наконец, вверх поднимаются люди весом 50 кг, 75 кг и 100 кг. Итого 5 переездов.
Есть еще второй (аналогичный) вариант, когда во второй поездке вниз спускаются те, кто весит 75 кг и 100 кг.
Горная река
К бурной горной реке подошли трое путников, первый весом 50 кг, второй весом 45 кг, а сколько весит третий – точно он не помнит, но где-то от 70 до 80 кг. Около берега стоит старая лодка, на которой есть надпись “Больше 100 кг не выдержит!”. За какое наименьшее количество переправ путники смогут переправиться через реку?
Начало формы
За какое наименьшее количество переправ путники смогут переправиться через реку?
Решение задачи
Все сразу переправиться не сумеют, одному ехать смысла нет, поэтому пусть первыми едут двое более легких. Затем пусть один из них останется на другом берегу, а второй в лодке вернется за третьим, самым тяжелым путником. Теперь переправляется в одиночестве самый тяжелый, а затем уже переправившийся легкий возвращается за оставшимся легким туристом.
Мушкетеры
Атос, Портос, Арамис и Д’Артаньян сидели за круглым столом (именно в такой последовательности), заспорили, и каждый поссорился со своими двумя соседями. Чтобы ехать дальше, им надо переправиться через реку в двухместной лодке. Каждый из мушкетеров отказывается оставаться вдвоем на берегу или быть в лодке с тем, с кем он в ссоре. Как им переправиться за как можно меньшее количество переездов?
Ниже заглавными латинскими буквами обозначены возможные комбинации мушкетеров в лодке. Выведите в качестве ответа последовательность букв, соответствующую наискорейшей переправе. Например, последовательность AAEA соответствует тому, что сначала переправился один Д'Артаньян и затем вернулся обратно, после этого на лодке переехали Д'Артаньян и Арамис, Арамис остался на противоположном берегу, а Д'Артаньян вернулся назад к Портосу и Атосу.
Д'Артаньян
B. Атос
C. Арамис
D. Портос
E. Д'Артаньян и Арамис
F. Д'Артаньян и Атос
G. Д'Артаньян и Портос
H. Арамис и Атос
I. Арамис и Портос
J. Атос и Портос
Конец формы
Решение задачи
Сначала переезжают мушкетеры, которые сидят напротив друг друга, то есть, либо Атос и Арамис, либо Д'Артаньян и Портос. Пусть это будут Атос и Арамис. Теперь один из них, например, Атос, остается на берегу, а второй (Арамис) возвращается обратно. Он остается на исходном берегу, а переправляется вторая пара мушкетеров, сидевших напротив (Д'Артаньян и Портос). Теперь Д'Артаньян и Портос и остаются на конечном берегу, а Атос возвращается за Арамисом. Получаем такую последовательность: HCGBH.
Еще три возможных варианта ответа: HBGCH, GAHDG, GDHAG.
Эльфы и гномы
Эльфы и гномы не любят друг друга, и если где-то одних оказывается по-крайней мере вдвое больше, чем других, они обязательно нападают. К левому берегу реки подошли 3 гнома, а к правому — 3 эльфа. Каждому нужно на противоположный берег. У левого берега есть двухместная лодка. Грести умеют один гном и один эльф.
Начало формы
За какое наименьшее количество переездов через реку им удастся переправиться без нападений?
Конец формы
Решение задачи
Задача решается однозначно. Сначала обязательно переправляются два гнома (если поплывет один, эльфы на него нападут). Теперь на правом берегу 2 гнома и 3 эльфа. Если обратно поплывут два эльфа, гномы нападут на оставшегося эльфа. Если обратно поплывут гном и эльф, эльфы нападут на оставшегося гнома. Следовательно, обратно плывет один эльф (который умеет грести). Он забирает оставшегося гнома и перевозит его на правый берег. Совершены три поездки и теперь все на правом берегу.
Чтобы никто ни на кого не напал, уехать может или один любой персонаж или гном с эльфом. Одному ехать нет смысла, поэтому отправляются гном, который умеет грести и эльф, который грести не умеет. Гном возвращается обратно и переправляются два эльфа (один из них умеет грести.)
Фонарик на мосту
Семья (папа, мама, сын и бабушка) ночью подошла к мосту, способному выдержать только двух человек одновременно. По мосту можно двигаться только с фонариком. Известно, что папа может перейти мост в одну сторону за минуту, мама – за три, сын – за шесть и бабушка – за десять минут. Если по мосту движутся двое, время перехода определяется более медленным из двоих. За какое наименьшее время они сумеют переправиться? (Фонарик у них один, кидать его нельзя, светить издали тоже нельзя.)
Решение задачи
Если всех будет по очереди переводить папа, то получится слишком долго.
Поэтому поступим так: папа переведет маму (3 минуты) и вернется обратно (1 минута). Затем пойдут два самых медленных — сын и бабушка (10 минут), а обратно фонарик принесет мама (3 минуты). Затем перейдут мама и папа (3 минуты). Итого: 3 + 1 + 10 + 3 + 3 = 20 минут.
.png)
