З Задачи о переправах

Определения и обозначения

Переправа — перемещение людей или предметов с одного берега на другой с помощью лодки. В задаче важно перечислить всех участников и договориться, какие берега считаются исходным и целевым. Тогда понятно, откуда начинается движение и кого именно нужно перевезти.

Перевозчик — участник, который управляет лодкой и может перевозить других. Иногда его присутствие на берегу обязательно: без него некоторые участники могут попасть в опасную ситуацию. Это понятие помогает проверить не только пассажиров лодки, но и тех, кто остаётся без присмотра.

Ограничение переправы — условие, которое должно выполняться при каждом рейсе или после него. Например, лодка может вмещать только перевозчика и одного пассажира, а некоторых участников нельзя оставлять вместе без перевозчика. Если заранее выписать такие правила, проще отсеять неподходящие ходы.

Состояние задачи — описание того, кто находится на каждом берегу и где стоит лодка. Например: «слева перевозчик и пассажир, справа второй пассажир, лодка слева». Такая запись нужна, чтобы точно проследить изменения после каждого рейса и не потерять участников по дороге.

Как это устроено

Сначала уточняют цель: всех ли участников нужно перевезти или только некоторых. Это задаёт конечное состояние, с которым можно будет сравнить результат. Если цель не записать, легко остановиться раньше времени или продолжить лишние рейсы.

Перед решением выписывают правила: кто умеет управлять лодкой, сколько человек в неё помещается и какие сочетания нельзя оставлять на берегу. Это нужно потому, что привычные на вид действия могут быть запрещены условием. Например, свободное место в лодке не всегда означает, что можно взять ещё одного пассажира: возможно, перевозчик уже занимает единственное разрешённое место.

Каждый рейс записывают как переход из одного состояния в другое. Отмечают, кто отправился, кто прибыл, кто остался на каждом берегу и где теперь лодка. Благодаря такой записи можно проверить весь план шаг за шагом, а не полагаться на память.

Затем отбрасывают ходы, которые сразу нарушают правила. Но этого недостаточно: допустимый сейчас рейс может завести в тупик, например оставить лодку на берегу, откуда её нельзя вернуть. Поэтому перед выбором стоит прикинуть, какие следующие действия останутся возможными.

Когда план найден, его проверяют целиком от начала до конца. Каждый рейс должен соответствовать вместимости лодки и правилам управления, а после каждого перехода состояние должно быть безопасным. В последнем состоянии все нужные участники должны оказаться на целевом берегу.

Как проверять ход решения задачи о переправе

Заполняй такую проверку после каждого рейса, а не только в конце. Если хотя бы одно условие не выполнено, вернись к предыдущему состоянию и выбери другой ход. Так проще увидеть, на каком именно шаге план перестал работать.

Разбор задач

Два пассажира и перевозчик

Перевозчик должен перевезти на другой берег двух пассажиров по очереди. Лодка вмещает перевозчика и одного пассажира. По условию участники должны переправляться по одному, поэтому после первого пассажира перевозчик возвращается за вторым.

1. Обозначим пассажиров А и Б. Сначала перевозчик и А плывут на целевой берег; Б остаётся на исходном.
2. Перевозчик возвращается один. Это нужно, чтобы лодка снова оказалась у Б.
3. Перевозчик перевозит Б на целевой берег. А и Б теперь там, а лодка находится вместе с ними.

Проверим вместимость: в каждом рейсе плывёт перевозчик и не больше одного пассажира, а в обратном рейсе — только перевозчик. Значит, все переходы разрешены, и оба пассажира доставлены. Ответ: перевозчик с А переправляется, возвращается, затем переправляется с Б.

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

Перевозчик может взять в лодку только одного из троих. Без него волк съест козу, а коза — капусту. Поэтому опасно оставлять на берегу волка с козой или козу с капустой, если перевозчика там нет.

1. Перевозчик отвозит козу на другой берег. Волк и капуста остаются вместе — это безопасно.
2. Он возвращается один, забирает волка и перевозит его. Затем возвращает козу обратно, чтобы волк не остался с ней без присмотра.
3. Перевозчик оставляет козу на исходном берегу и увозит капусту к волку. Коза не остаётся с капустой без перевозчика.
4. Он возвращается один и в последнем рейсе перевозит козу. Теперь все находятся на целевом берегу.

После каждого шага опасные пары либо разделены, либо рядом с ними находится перевозчик. Ответ: коза туда, перевозчик назад, волк туда, коза назад, капуста туда, перевозчик назад, коза туда.

Двое взрослых и двое детей

В лодке помещается один взрослый или не более двух детей, а управлять лодкой умеют только взрослые. При буквальном чтении этих условий задача не имеет решения: взрослый не может находиться в лодке одновременно с детьми, а дети не умеют управлять ею сами.

1. Чтобы переправить детей, лодка должна отправиться с детьми на борту.
2. Но по правилу вместимости взрослый не может плыть вместе с ними.
3. Без взрослого дети не могут управлять лодкой, поэтому такой рейс невозможен.
4. Если взрослый едет один, он не перевозит детей, а их самостоятельный рейс всё равно запрещён.

Значит, ни один первый рейс не позволяет начать перевозку детей. Ответ: при данных правилах последовательности рейсов нет. Для решения условия нужно изменить, например разрешить взрослому плыть вместе с детьми или разрешить детям управлять лодкой.

Типичные ошибки

• В лодку сажают больше участников, чем разрешено. Так происходит, когда решающий торопится быстрее достичь цели и забывает о вместимости. Проверяй число пассажиров перед каждым рейсом и учитывай, занимает ли перевозчик отдельное место.
• Проверяют лодку, но не берег после отплытия. Из-за этого можно не заметить, что без перевозчика осталась запрещённая пара. После каждого перехода записывай состав обоих берегов и сверяй его с ограничениями.
• Считают обратный рейс лишним. Тогда лодка или единственный перевозчик могут остаться не на том берегу, и следующий ход станет невозможен. Перед планом спроси себя, кто вернёт лодку и сможет ли он это сделать.
• Записывают только пассажиров, забывая положение лодки. В результате легко перепутать берег отправления и приписать участнику невозможный рейс. После каждого перехода отмечай, на каком берегу лодка, и начинай следующий шаг именно оттуда.

Связь с другими темами

Для решения переправ полезно уметь внимательно читать условие и выделять в нём цель, участников и ограничения. Это помогает отличить обязательное правило от подробности, которая не влияет на ход решения. Когда условия записаны точно, их легче проверять на каждом шаге.

Запись состояний и проверка переходов связаны с составлением алгоритмов: действие меняет исходное положение и приводит к новому. Такой способ рассуждения пригодится и в логических задачах, где важно не пропустить ни одного возможного хода и исключить запрещённые варианты.

Что запомнить

• Сначала выпиши цель и все ограничения переправы.
• После каждого рейса проверяй, кто остался на каждом берегу.
• Учитывай положение лодки и возможность её вернуть.
• Не допускай запрещённых сочетаний участников без перевозчика.
• Каждый рейс в решении должен соответствовать условию задачи.
• В конце проверь всю последовательность от начала до завершения.