Задача о мосте и факеле (также известная как «Полуночный поезд» [1] и «Опасный переход» [2] ) — это логическая головоломка , в которой участвуют четыре человека, мост и факел . Она относится к категории головоломок о пересечении реки , где несколько объектов должны пересечь реку с некоторыми ограничениями. [3]
Четыре человека приходят к реке ночью. Мост узкий, и он может вместить только двух человек одновременно. У них есть один факел, и поскольку сейчас ночь, при переходе моста нужно использовать факел. Человек A может перейти мост за 1 минуту, B — за 2 минуты, C — за 5 минут, а D — за 8 минут. Когда два человека пересекают мост вместе, они должны двигаться в темпе более медленного человека. Вопрос в том, смогут ли они все перейти мост, если факел продержится всего 15 минут? [2]
Первая очевидная идея заключается в том, что стоимость возвращения факела людям, ожидающим перехода, является неизбежными расходами, которые следует минимизировать. Эта стратегия делает А факелоносцем, перевозящим каждого человека через мост: [4]
Эта стратегия не позволяет пересечь дорогу за 15 минут. Чтобы найти правильное решение, нужно понимать, что заставлять двух самых медленных людей переходить дорогу по отдельности — это трата времени, которое можно было бы сэкономить, если бы они пересекли дорогу вместе: [4]
Второе эквивалентное решение меняет местами обратные поездки. По сути, два самых быстрых человека пересекают дорогу вместе в 1-й и 5-й поездках, два самых медленных человека пересекают дорогу вместе в 3-й поездке, и ЛЮБОЙ из самых быстрых людей возвращается во 2-й поездке, а другой самый быстрый человек возвращается в 4-й поездке.
Таким образом, минимальное время для четырех человек определяется следующими математическими уравнениями: Когда ,
Предположим, что решение минимизирует общее количество переходов. Это дает в общей сложности пять переходов — три парных перехода и два одиночных перехода. Также предположим, что мы всегда выбираем самого быстрого для одиночного перехода. Во-первых, мы показываем, что если два самых медленных человека (C и D) перейдут мост по отдельности, они накапливают общее время перехода 15. Это делается путем взятия людей A, C и D: C+A+D+A = 5+1+8+1=15. (Здесь мы используем A, потому что знаем, что использование A для пересечения моста C и D по отдельности является наиболее эффективным.) Но время истекло, а люди A и B все еще находятся на исходной стороне моста и должны перейти. Поэтому два самых медленных (C и D) не могут перейти мост по отдельности. Во-вторых, мы показываем, что для того, чтобы C и D перешли мост вместе, им нужно перейти мост во время второго парного перехода: т. е. не C или D, поэтому A и B должны перейти мост вместе первыми. Помните, наше предположение в начале гласит, что мы должны минимизировать пересечения, и поэтому у нас есть пять пересечений - 3 парных пересечения и 2 одиночных пересечения. Предположим, что первыми пересекают C и D. Но затем C или 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 году в книге «Суперстратегии для головоломок и игр» . В этой версии головоломки на пересечение A, B, C и D уходит 5, 10, 20 и 25 минут соответственно, а ограничение по времени составляет 60 минут. [6] [7] Во всех этих вариациях структура и решение головоломки остаются прежними.
В случае, когда имеется произвольное количество людей с произвольным временем пересечения, а пропускная способность моста остается равной двум людям, задача была полностью проанализирована методами теории графов . [4]
Мартин Эрвиг из Университета штата Орегон использовал вариант этой проблемы, чтобы доказать целесообразность использования языка программирования Haskell вместо Prolog для решения задач поиска . [8]
Эта головоломка также упоминается в книге Дэниела Деннета « От бактерий к Баху и обратно» как его любимый пример решения, которое противоречит интуиции.
