МАЛЫЙ МЕХМАТ МГУ

Кружок 5 класса

Занятие 8. Переправы

Основные задачи

0.

Как-то раз крестьянин подошел к реке с пойманным волком, козой и капустой. Но вот беда — в лодку помимо крестьянина (а только он умеет грести) влезает либо только волк, либо только коза, либо только капуста. Кроме того, оставить без присмотра волка с козой или козу с капустой — верный способ потерять часть имущества. Как крестьянину переправиться вместе со своим имуществом без потерь?

Решение

Решение. Перевезти на другой берег козу, вернуться, перевезти волка, переправить обратно козу, перевезти капусту, вернуться, перевезти козу.

1.

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

Ответ

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

2.

На очень узкой дороге встретились 6 машин: три ехали в одну сторону и три в другую. Как им разъехаться, если сбоку есть стоянка, куда может заехать только одна машина?

Решение

Решение.
Обозначим машины так: машины А, Б, В едут слева направо, а машины Э, Ю, Я — справа налево (см. рисунок). Сначала машина В заезжает на стоянку. Машины А, Б, Э, Ю, Я проезжают налево (машинам А и Б при этом приходится двигаться задним ходом). Машина В выезжает с парковки и оказывается правее машин Э, Ю, Я; теперь она может уехать. Машины Э, Ю, Я двигаются направо задним ходом. Машина Б заезжает на стоянку, машины Э, Ю, Я едут налево. Машина Б выезжает с парковки, оказывается правее машин Э, Ю, Я и уезжает. Аналогичным образом машины Э, Ю, Я пропускают машину А.

3.

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

Решение

Решение. Сначала оба мальчика плывут на тот берег, где нет солдат, один из них там остаётся, а второй возвращается. Один из солдат садится в лодку и плывёт на другой берег. Мальчик, оставшийся там раньше, садится в лодку и плывёт за вторым мальчиком на берег, где все еще находится бóльшая часть солдат. Получается ситуация, которая отличается от исходиной только тем, что один солдат уже переправился на другой берег. Повторяя аналогичные действия нужное число раз, мальчики могут по одному переправить всех солдат на другой берег. Обратите внимание: решение совершенно не зависит от того, сколько солдат в полку!

4.

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

Решение

Решение. Буквами А, Б, В обозначим рыцарей, а буквами а, б, в — их оруженосцев. Ниже записаны все этапы переправы. В каждой строчке указано, кто находится на левом и правом берегах после очередного шага (то есть после того, как кто-то куда-то переправился на лодке). Подчеркиванием выделены те, кто только что переправился, а лодка находится с ними на одном берегу:
АБВабв ...
АБВа ... бв
АБВаб ... в
АБВ ... абв
АБВа ... бв
Аа ... БВбв
АБаб ... Вв
аб ... АБВв
абв ... АБВ
а ... АБВбв
Аа ... БВбв
... АБВабв

5.

Три миссионера и три каннибала должны переправиться через реку на двухместной лодке. Миссионеры боятся оставаться в меньшинстве, чтобы не быть съеденными. (Это происходит и тогда, когда в лодке и на берегу, к которому она причаливает, каннибалов в сумме оказывается больше, чем миссионеров.) Только один из миссионеров и один из каннибалов умеют грести. Помогите им переправиться.

Решение

Решение. Будем обозначать большой буквой М миссионера, умеющего грести, маленькими буквами м — миссионеров, не умеющих грести (их необязательно различать между собой), большой буквой К — каннибала, умеющего грести, маленькими буквами к — каннибалов, не умеющих грести (их тоже необязательно различать между собой). Запишем все этапы переправы подобно тому, как мы это делали при решении предыдущей задачи:
МммКкк ...
ммКк ... Мк
МммКк ...к
Ммм ... Ккк
МммК ... кк
мК... Ммкк
МмКк ... мк
мк ... МмКк
Ммкк ... мК
кк ... МммК
Ккк ... Ммм
к .. МммКк
Кк ... Мммк
... МммКкк

6.

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

Решение

Решение.

Эта задача аналогична задаче 2. Разница только в том, что вагоны не могут двигаться без помощи паровоза. Зато в тупичок помещаются сразу три вагона.

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

Дополнительные задачи

7.

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

Решение

Решение. Будем обозначать черные шашки буквой Ч, а белые — буквой Б; свободный квадрат будем обозначать _. При записи этапов решения будем выделять жирным шрифтом последнюю передвинутую шашку:
ЧЧЧ_БББ
ЧЧ_ЧБББ
ЧЧБЧ_ББ
ЧЧБЧБ_Б
ЧЧБ_БЧБ
Ч_БЧБЧБ
_ЧБЧБЧБ
БЧ_ЧБЧБ
БЧБЧ_ЧБ
БЧБЧБЧ_
БЧБЧБ_Ч
БЧБ_БЧЧ
Б_БЧБЧЧ
ББ_ЧБЧЧ
БББЧ_ЧЧ
БББ_ЧЧЧ
Это лишь одно из возможных решений. Другое решение можно получить, например, так:
ЧЧЧ_БББ
ЧЧЧБ_ББ
ЧЧ_БЧББ
ЧЧБ_ЧББ
Ч_БЧЧББ
ЧБ_ЧЧББ
_БЧЧЧББ
Б_ЧЧЧББ
БЧ_ЧЧББ
БЧЧ_ЧББ
БЧЧЧ_ББ
Заметим, что к этому моменту одна из белых шашек оказалась на нужном месте, и ее можно больше не трогать. А расположение оставшихся шашек очень похоже на первоначальное. Поэтому, повторяя аналогичные действия, переместим налево сначала вторую, а затем и третью белую шашку.

8.

Большая компания мальчиков весом 40, 50 и 60 килограммов идут в поход. Мальчиков каждого веса в компании хотя бы двое. По дороге они собираются переправляться через реку. Лодку какой наименьшей грузоподъемности им нужно для этого взять с собой?

Ответ Решение

Ответ. 80 кг.

Решение.

Сначала заметим, что в какой-то момент в лодке придется сидеть двум мальчикам одновременно, иначе один мальчик уплывет на лодке с самого начала, и некому будет вернуть ее обратно. Поэтому лодка должна иметь грузоподъемность не менее 80 кг (это минимальный вес пары мальчиков из нашей компании).

Теперь докажем, что лодки грузоподъемностью 80 кг хватит. Способ переправить нашу компанию мальчиков с помощью такой лодки аналогичен решению задачи 3. В роли двоих мальчиков из той задачи могут выступать любые два мальчика весом 40 кг (а по условию таких мальчиков не меньше двух), а остальные мальчики будут выступать в роли солдат. Лодка грузоподъемностью 80 кг выдерживат двух мальчиков весом 40 кг или одного «солдата» весом 50 или 60 кг (или даже двоих «солдат» весом по 40 кг, хотя это и не требуется).

9.

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

Решение

Решение.

Сначала Р забирает N, выезжает направо и подаёт задним ходом далеко налево. Там он оставляет вагон N, затем выталкивает М в промежуток А, возвращается, цепляет N и выезжает направо. Далее Р (вместе с N) задним ходом подъезжает к М и цепляет его позади N. Теперь Р c прицепленными к нему M и N выезжает направо, а затем задним ходом далеко налево. Там он оставляет вагон М и едет снова направо. Задним ходом Р заезжает в промежуток А и оставляет там вагон N. Затем он возвращается за вагоном М, уезжает с ним далеко направо, задним ходом подаёт на правую ветку, там оставляет вагон M, а сам уезжает на левую ветку и вытаскивает на неё из промежутка А вагон N. А сам возвращается на исходную позицию.

Совет. Чтобы понять это решение, нужно последовательно нарисовать все происходящее на картинках (каждую ситуацию нужно рисовать на отдельной картинке!). Если же вам (как и автору этого текста) лень рисовать столько картинок, нарисуйте на бумаге рельсы и катайте по ним машинки или ластики. Или используйте игрушечную железную дорогу (если она у вас есть).