Проблема с мостом и факелом

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

История

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

Решение

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

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

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

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

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

Таким образом, минимальное время для четырех человек определяется следующими математическими уравнениями: Когда $A<B<C<D$ ,
$\min(B+A+C+A+D,B+A+D+B+B)$
$\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 не могут, и мы минимизируем пересечения. Затем А должен пересечься следующим, поскольку мы предполагаем, что нам следует выбрать самого быстрого, кто сделает одиночный переход. Тогда мы находимся на втором, или среднем, парном пересечении, поэтому 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 ]}

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

См. также

Загадка о переправе через реку

Ссылки

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

Внешние ссылки

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

[mm-1] Перейти обратно: ^а ^б «УБИЙСТВЕННЫЕ МАТЕМАТИЧЕСКИЕ МОЗГИ» . Проверено 8 февраля 2008 г.

[webam-2] Перейти обратно: ^а ^б Глеб Грибакин. «Некоторые простые и не очень простые математические задачи» . Проверено 8 февраля 2008 г.

[a-3] Tricky Crossings. Архивировано 20 января 2008 г. в Wayback Machine , Иварс Петерсон, Science News , 164 , № 24 (13 декабря 2003 г.); доступ онлайн 7 февраля 2008 г.

[eatcs-4] Перейти обратно: ^а ^б ^с Роте, Гюнтер (2002). «Переход моста ночью» (PDF) . Бюллетень Европейской ассоциации теоретической информатики . Том. 78. стр. 241–246.

[visi-5] «Загадка о переходе моста» . Архивировано из оригинала 31 мая 2008 г.

[sillke-6] Торстен Силке (сентябрь 2001 г.). «Переход моста за час» . Проверено 9 февраля 2008 г.

[7] Левмор, Сол X.; Кук, Элизабет Эрли (1981). Супер стратегии для головоломок и игр . Гарден-Сити, Нью-Йорк: Doubleday & Company. ISBN 0-385-17165-Х .

[ezurg-8] Эрвиг, Мартин (2004). «Побег из Зурга» (PDF) . Журнал функционального программирования, Vol. 14, № 3. С. 253–261.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]