Переправа четырёх рыцарей с оруженосцами
*
Можно ли переправиться при тех же условиях, что и в предыдущей задаче, если к реке подъехали четыре рыцаря с оруженосцами?
А именно, можно ли переправиться через реку четырём рыцарям с оруженосцами, если имеется только одна двухместная лодка, и ни один оруженосец не может оставаться в обществе чужих рыцарей без своего хозяина?
В формулировке задачи есть один тонкий момент, от толкования которого зависит, имеет задача решение или нет. В условии сказано, что «ни один оруженосец не может оставаться в обществе чужих рыцарей без своего хозяина». Это требование может быть понято буквально, что оруженосец может переправляться через реку или оставаться на берегу только в обществе своего рыцаря (и неважно кого ещё) или только лишь других оруженосцев. Но при этом ситуация, когда оруженосец приплывает (один или в паре с другим оруженосцем) на берег, на котором есть один или два чужих рыцаря, но нет его хозяина, после чего все чужие рыцари переправляются на противоположный берег, может считаться допустимой. Ведь формально в этом случае оруженосец не находится «в обществе» чужих рыцарей, а лишь сталкивается с ними, когда он выходит из лодки, а они в неё садятся. При такой интерпретации условий задачи она является вполне разрешимой. Вы без труда найдёте нужную последовательность рейсов.
Однако всё же более правильным является следование духу задачи, а не её букве. То есть оруженосцам запрещается не только «оставаться в обществе» чужих рыцарей, но и вообще как-либо пересекаться с ними в отсутствии своих хозяев. При таком подходе задача является неразрешимой.
Для доказательства предположим, что переправа возможна, и пронумеруем, начиная с первого, все рейсы, которые совершит лодка. Тогда после нечётных рейсов она будет находиться на втором берегу, а после чётных — на первом. Обозначим через
В первом случае обозначим рыцарей, оставшихся на первом берегу, через А, Б, В, а рыцаря на втором берегу — через Г. Если соответствующих оруженосцев обозначить а, б, в, г, то с соблюдением условий задачи возможно единственное распределение оруженосцев. Итак, в первом случае после рейса с номером
Первый берег | | | Второй берег | ||||||||
А | Б | В | . | | | . | . | . | Г | ||
а | б | в | . | | | . | . | . | г |
Кто же отправится в лодке рейсом 2k? Рыцарь Г уплыть не может, ведь тогда после рейса
Во втором случае обозначим рыцарей на первом берегу через А, Б и переправившихся рыцарей через В, Г. Тогда после рейса
Первый берег | | | Второй берег | ||||||||
А | Б | . | . | | | . | . | В | Г | ||
а | б | . | . | | | . | . | в | г |
Кто же в этом случае отправится рейсом 2k? Ни один из рыцарей В, Г уплыть не может, так как тогда рейсом
Итак, мы установили, что с соблюдением условий задачи на второй берег не может переправиться более двух рыцарей.
Добавить комментарий