Проблема с мостом и факелом - Bridge and torch problem

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

История

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

Решение

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

Пройденное время	Стартовая сторона	Действие	Конечная сторона
0 минут	А Б В Г
2 минуты	CD	A и B переходят вперед, занимает 2 минуты	А Б
3 минуты	A C D	А возвращается, занимает 1 минуту	B
8 минут	D	A и C переходят вперед, занимает 5 минут	А Б В
9 минут	А Д	А возвращается, занимает 1 минуту	ДО Н.Э
17 минут		A и D переходят вперед, занимает 8 минут	А Б В Г

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

Пройденное время	Стартовая сторона	Действие	Конечная сторона
0 минут	А Б В Г
2 минуты	CD	A и B переходят вперед, занимает 2 минуты	А Б
3 минуты	A C D	А возвращается, занимает 1 минуту	B
11 минут	А	C и D переходят вперед, занимая 8 минут	B C D
13 минут	А Б	B возвращается через 2 минуты	CD
15 минут		A и B переходят вперед, занимает 2 минуты	А Б В Г

Второе эквивалентное решение меняет местами обратные поездки. По сути, два самых быстрых человека пересекаются вместе в 1-м и 5-м поездках, два самых медленных человека пересекаются вместе в 3-м путешествии, и ЛИБО из самых быстрых людей возвращается во 2-м путешествии, а другой самый быстрый человек возвращается в 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 по отдельности является наиболее эффективным.) Но время истекло, а люди 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]

Загадка также упоминается в книге Дэниела Деннета. От бактерий до Баха и обратно как его любимый пример решения, которое противоречит интуиции.

Смотрите также

• Пазл о переходе через реку

Рекомендации

1. "УБИЙСТВЕННЫЕ МАТЕРИАЛЫ МОЗГЛЯДЫ". Получено 2008-02-08.
2. Глеб Грибакин. «Несколько простых и не очень простых математических задач». Получено 2008-02-08.
3. Хитрые переходы, Иварс Петерсон, Новости науки, 164, № 24 (13 декабря 2003 г.); доступ на сайте 7 февраля 2008 г.
4. Роте, Гюнтер (2002). «Переход ночью по мосту» (PDF). Бюллетень Европейской ассоциации теоретической информатики. 78. С. 241–246.
5. "Загадка перехода моста". Архивировано из оригинал 31 мая 2008 г.
6. Торстен Силлке (сентябрь 2001 г.). «Переход по мосту через час». Получено 2008-02-09.
7. Левмор, Саул X .; Кук, Элизабет Эрли (1981). Супер стратегии для головоломок и игр. Гарден-Сити, Нью-Йорк: Doubleday & Company. ISBN  0-385-17165-X.
8. Эрвиг, Мартин (2004). «Побег из Зурга» (PDF). Журнал функционального программирования, Vol. 14, № 3. С. 253–261.

внешняя ссылка

• Слайды проблемы с резаком емкости C. [1]
• Документ, посвященный проблеме с резаком емкости C. [2]
• Видео и упражнения Теда Эда, основанные на задаче о мостике и факеле [3]
• Документ, посвященный систематическому решению загадки моста с использованием комбинаторики [4]