Задача о мосте и факеле

Задача о мосте и факеле (известная также как Полуночный поезд^[1] и Опасный переход^[2]) — это логическая головоломка, в которой участвуют четыре человека, мост и факел. Задача принадлежит категории задач о переправе, где некоторое число объектов должно быть перенесено через реку при некоторых ограничениях^[3].

Четверо подошли к реке ночью. Есть узкий мост и он может выдержать лишь пару человек. У них есть один факел и, поскольку ночь, его нужно использовать при переходе через мост. Человек A может перейти мост за 1 минуту, B — за 2 минуты, C за 5 минут, а D за 8 минут. Когда двое пересекают мост вместе, они должны двигаться со скоростью более медленного спутника. Вопрос, могут ли они пересечь мост, если факел горит только 15 минут^[2]?

Очевидной первой мыслью является то, что стоимость возвращения факела людям, ожидающим перехода, является неизбежными расходами, которые следует минимизировать. Эта стратегия делает А факелоносцем, перевозящим каждого человека через мост^[4]:

Эта стратегия не позволяет переход моста за 15 минут. Чтобы найти правильное решение, нужно понять, что вынуждение двух самых медленных участников идти раздельно тратит время, которое может быть сохранено, если они пересекают мост вместе^[4]:

Второе эквивалентное решение меняет местами обратные переходы. По сути, два самых быстрых человека пересекаются вместе в 1-м и 5-м переходах, два самых медленных человека пересекаются вместе в 3-м переходе и ЛЮБОЙ из самых быстрых людей возвращается во втором переходе, а другой самый быстрый человек возвращается в 4-м переходе.

Таким образом, минимальное время для четырех человек определяется следующими математическими уравнениями: Если ${\displaystyle A<B<C<D}$,
${\displaystyle \min(B+A+C+A+D,B+A+D+B+B)}$
${\displaystyle \min(2A+B+C+D,A+3B+D)}$

Допустим, что решение минимизирует общее количество пересечений. Это дает в общей сложности пять пересечений: три парных пересечения и два одиночных пересечения. Кроме того, будем считать, что для одиночного пересечения мы всегда выбираем самого быстрого. Сначала заметим, что если два самых медленных человека (C и D) пересекают по раздельности, они займут полное время пересечения 15. Это достигается выбором A, C и D: C+A+D+A = 5+1+8+1=15. (Здесь мы используем A, потому что знаем, что использование A для сопровождения C и D по отдельности является наиболее эффективным.) Время истекло, а люди А и В всё ещё находятся на начальной стороне моста и должны его пересечь. Следовательно, двое самых медленных (С и D) не могут пересечь мост поодиночке. Далее мы покажем, что если С и D пересекают мост вместе, им необходимо сделать это во время второго парного перехода. Это означает, что первыми должны перейти не С или D, а А и В. Напомним, что наше изначальное предположение заключалось в минимизации переходов, и в итоге мы получаем пять переходов: три парных и два одиночных. Предположим, что С и D переходят первыми. Но тогда один из них (С или D) должен вернуться с факелом на другую сторону, и тот, кто переходил один, должен будет пересечь мост снова. Таким образом, они переправятся по отдельности. Также невозможно, чтобы они переправились вместе последними, поскольку это означало бы, что один из них должен был переправиться раньше, иначе на стартовой стороне оказалось бы три человека. Следовательно, поскольку существует только три варианта парных переправ, а C и D не могут переправиться первыми или последними, они должны переправиться вместе во время второй или средней парной переправы. Собрав все это воедино, A и B должны переправиться первыми, поскольку мы знаем, что C и D не могут, а мы стремимся минимизировать количество переправ. Затем A должен переправиться следующим, поскольку мы предполагаем, что следует выбрать самого быстрого для одиночной переправы. Затем мы оказываемся у второй, или средней, парной переправы, поэтому C и D должны отправиться. Затем мы выбираем отправить самого быстрого обратно, которым является B. A и B теперь находятся на стартовой стороне и должны переправиться во время последней парной переправы. Это дает нам: B+A+D+B+B = 2+1+8+2+2 = 15.

Существует несколько вариантов с небольшими изменениями, такими как имена людей, время перехода моста участниками или предельного допустимого времени^[5]. Время горения факела может быть ограничено и это время используется как предельное допустимое время. В варианте под названием Полуночный поезд, например, человеку D нужно 10 минут, а не 8, чтобы пересечь мост, а люди A, B, C и D, называемые теперь четырьмя братьями Габрианни, имеют только 17 минут, чтобы успеть на ночной поезд^[1].

Известно, что эта головоломка впервые появилась в 1981 году в книге Super Strategies For Puzzles and Games (Суперстратегии для головоломок и игр). В этой версии головоломки А, В, С и D пересекают реку за 5, 10, 20 и 25 минут соответственно, а временной лимит составляет 60 минут^[6][7]. Во всех этих вариациях структура и решение головоломки остаются неизменными.

В случае произвольного числа людей с произвольными временами перехода через мост и, если мост также выдерживает только двоих, задача была полностью проанализирована методами теории графов^[4].

Мартин Эрвиг из Университета штата Орегон использовал вариацию этой задачи, чтобы доказать преимущество языка программирования Haskell над языком Prolog для решения задач поиска^[8].

Головоломка упомянута в книге Дэниела Деннета «From Bacteria to Bach and Back» (От бактерий до Баха и обратно) как его любимый пример решения, которое противоречит интуиции.

• Задача о переправе

• Slides of the Capacity C Torch Problem [1]
• Paper discussing the Capacity C Torch Problem [2]
• Ted Ed Video and Exercise Based on Bridge and Torch Problem [3]
• Paper discussing A Systematic Solution to the Bridge Riddle using Combinatorics [4]