Переправа четырёх рыцарей с оруженосцами

*

Сложность: 

Можно ли переправиться при тех же условиях, что и в предыдущей задаче, если к реке подъехали четыре рыцаря с оруженосцами?

А именно, можно ли переправиться через реку четырём рыцарям с оруженосцами, если имеется только одна двухместная лодка, и ни один оруженосец не может оставаться в обществе чужих рыцарей без своего хозяина?

Решение

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

Однако всё же более правильным является следование духу задачи, а не её букве. То есть оруженосцам запрещается не только «оставаться в обществе» чужих рыцарей, но и вообще как-либо пересекаться с ними в отсутствии своих хозяев. При таком подходе задача является неразрешимой.

Для доказательства предположим, что переправа возможна, и пронумеруем, начиная с первого, все рейсы, которые совершит лодка. Тогда после нечётных рейсов она будет находиться на втором берегу, а после чётных — на первом. Обозначим через 2k + 1 наименьший номер нечётного рейса, в результате которого на втором берегу окажется более двух рыцарей. Рейс с номером 2k + 1 может доставить на второй берег не более двух человек, поэтому после рейса 2k – 1 на втором берегу должен находиться по крайней мере один рыцарь. Мы видим, что после рейса 2k – 1 на втором берегу могут находиться или один, или два рыцаря.

В первом случае обозначим рыцарей, оставшихся на первом берегу, через А, Б, В, а рыцаря на втором берегу — через Г. Если соответствующих оруженосцев обозначить а, б, в, г, то с соблюдением условий задачи возможно единственное распределение оруженосцев. Итак, в первом случае после рейса с номером 2k – 1 мы получаем такую картину:

Первый берег | Второй берег
АБВ.|...Г
абв.|...г

Кто же отправится в лодке рейсом 2k? Рыцарь Г уплыть не может, ведь тогда после рейса 2k + 1 на втором берегу будут не более двух рыцарей. Значит, рейсом 2k поплывёт один оруженосец г, но тогда на первом берегу он окажется в обществе чужих рыцарей, что противоречит условию задачи. В рейс 2k плыть некому. Это означает, что первый случай невозможен.

Во втором случае обозначим рыцарей на первом берегу через А, Б и переправившихся рыцарей через В, Г. Тогда после рейса 2k – 1 имеем:

Первый берег | Второй берег
АБ..|..ВГ
аб..|..вг

Кто же в этом случае отправится рейсом 2k? Ни один из рыцарей В, Г уплыть не может, так как тогда рейсом 2k + 1 с первого берега должны уплыть два рыцаря и один из оруженосцев а или б останется без охраны. Но ни один из оруженосцев в, г не может плыть рейсом 2k без своего рыцаря, ведь на первом берегу находятся А, Б. Опять в рейс 2k плыть некому.

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




Добавить комментарий

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.
Type the characters you see in this picture. (verify using audio)
Type the characters you see in the picture above; if you can't read them, submit the form and a new image will be generated. Not case sensitive.