Ночь. Мост. Фонарик

Разминка для мозгов » Задачи » Ночь. Мост. Фонарик

Добавлено: 29.08.10 в 09:30

Метки: логические теория графов другой берег

Четырём людям надо в темноте перейти через мост.

У людей есть один фонарик на четверых.

Переходить мост можно только с фонариком, потому что темно и мост без перил.

Одновременно на мосту мосту могут находиться не более двух человек, потому что мост старый и не выдержит больше.

У каждого человека своя скорость прохождения через мост: первый проходит мост за 1 минуту, второй — за 2 минуты, третий — за 5, четвёртый — за 10 минут.

Когда два человека переходят мост вместе, они идут со скоростью наиболее медленного из них.

Какое минимальное время понадобится этой четвёрке, чтобы перейти мост, и в какой последовательности им надо его переходить?

СПРЯТАТЬ РЕШЕНИЕ/ОТВЕТ

Обозначим людей 1,2,5,10 по времени, затрачиваемому на переход через мост.

Вот последовательность переходов, гарантирующая минимальное время (время на каждый переход указано в скобках

0. Все на исходной позиции: 1, 2, 5, 10 ⇔ — (0 мин.)
1. 1 и 2 идут на другой берег: 5, 10 ⇔ 1, 2 (2 мин.)
2. 1 возвращается: 1, 5, 10 ⇔ 2 (1 мин.)
3. 5 и 10 идут на другой берег: 1 ⇔ 2, 5, 10 (10 мин.)
4. 2 возвращается: 1, 2 ⇔ 5, 10 (2 мин.)
5. 1 и 2 идут на другой берег: — ⇔ 1, 2, 5, 10 (2 мин.)

Итого: 2 + 1 + 10 + 2 + 2 = 17 минут.

Формальное доказательство можно провести с использованием графа, вершинами в котором являются положения людей и фонарика на разных концах моста; две вершины соединены ребром тогда и только тогда, когда из одного положения можно перейти в другое по условиям задачи (фонарик, не более двух человек за переход etc); вес ребра — время, затрачиваемое на такой переход.

Для решения этой задачи надо найти на этом графе минимальный путь из начального положения в конечное.

ПОКАЗАТЬ РЕШЕНИЕ/ОТВЕТ

Комментарии

Google says:

1ngvar (30.08.10):

19 минут. Фонарик должен находиться у самого быстрого, первого (скорость прохождения моста 1 минута), он же должен всех перевести. Переводит второго (2 мин.), возвращаеться (1 мин.), переводит третьего (5 мин.), возвращаеться (1 мин.), переводит четвёртого (10 мин.). Итого 19 минут.

Ответ редакции:

1. нет.
2. прежде чем писать комментарии можно свериться с ответом.

Makus (21.09.10):

можно и за 17 минут пройти

Makus (21.09.10):

сначало мост переходят 1 и 2 (2 мин). 1 возвращается (1 мин). 3 и 4 переходят мост (10 мин).2 возвращается (2 мин). 1 и 2 переходят мост (2 мин). Итого 2+1+10+2+2 = 17

Маша (31.10.10):

1 и 2 переходят мост
1 вернулся с фонариком
1 взял с собой 3
перешли мост
1 вернулся взял 4
перешли мост
2+5+10=17
:)

Аноним (09.11.10):

Маша, у тебя ошибка. Ты не посчитала две минуты, которые потратил первый возвращаясь. Makus прав. Чтобы уложиться в 17 минут нужно, чтобы третий и четвертый прошли по мосту одновременно.

SK (28.11.10):

Уже давным-давно в сети и эта задачка, и решение есть)

Вадим (20.12.10):

Логически верный ответ:
12 минут.
Почему? Вопрос задачи: "Какое минимальное время понадобится этой четвёрке, чтобы перейти мост, и в какой последовательности им надо его переходить?"
В задаче не чего не сказано о том где находятся люди, они все на одном берегу или нет. Сказано лишь то , что им всем нужно перейти на другой берег. При этом могут идти максимум вдвоем.
В данном случае мы можем расставить людей как захотим лишь бы они перешли мост.
Итак:
Человек 1 - (1мин\мост)
Человек 2 - (2мин\мост)
Человек 3 - (5мин\мост)
Человек 4 - (10мин\мост)

Оптимальный маршрут:
Человек 1 и 2 идут с правого берега на левый (затрачено времени 2 минуты) отдают фонарик второй паре и они идут с левого берега на правы (затрачено 10 минут). ИТОГО 10 + 2 = 12 минут.

Все условия выполнены и не одно не нарушено.

ДиРеКтОр ЗоО пАрКа (03.01.11):

Вадим ты урод и неправ.

rthn (12.02.11):

ДиРеКтОр ЗоО пАрКа вадим был прав

snejka (22.04.11):

Забавная задачка) спасибо автору

Аноним (17.09.11):

Мне кажется ответ "Гладиолус"

Сеня (30.12.11):

Вадим-РЕСПЕКТ !!!!!

упс (11.02.12):

вадим прав

))) (26.04.12):

В задаче не сказано что люди должны перейти все! 1 и 2 могут перейти к 3 и4 и поэтому всремя минимальное составляет 2 мин.)))

Саша (03.07.12):

Вадим ,вы не правы. Ибо из разделяет мост и они не могут передать фонарик другой паре

ваня (03.07.12):

В ответе ошибка!
0. Все на исходной позиции: 1, 2, 5, 10 :: — (0 мин.)
1. 1 и 2 идут на другой берег: 5, 10 :: 1, 2 (2 мин.)
2. 1 возвращается: 1, 5, 10 :: 2 (1 мин.)
3. 5 и 10 идут на другой берег: 1 :: 2, 5, 10 (10 мин.)
4. 2 возвращается: 1, 2 :: 5, 10 (2 мин.) ТУТ ОШИБКА :возрашался чтобы отдать фонарик 1 человек ,т.е за 1 минуту.
5. 1 и 2 идут на другой берег: — :: 1, 2, 5, 10 (2 мин.)

ПОЛУЧАЕТСЯ 16 минут а не 17

Ответ редакции:

На 4-м шаге как у вас фонарик от "2,5,10" попадёт к "1" за 1 минуту? Ошибка тут как раз у вас.

ваня (04.07.12):

Мы не правильно друг друга поняли,видимо.
на 2 шаге 1мин идет к 5мин и 10мин отдает фонарь - за 1 минуту
На шаге 4 человек 1мин возращается за 1 минуту обратно на нужный берег-где тут 2 минуты то?

Ответ редакции:

После третьего шага фонарик у группы товарищей "2, 5, 10". Кто его несёт на другую сторону?

lom (15.07.12):

18 минут

Hayk (11.10.12):

видимо последнему товарщу действительно в ЛОМ посмотреть на ответ :)))))))

Аноним (01.02.13):

как это я не похож на человека?)))))))))))

Анатолий (14.02.13):

минимальное время 5 минут, если у человека с скоростью в 1 минуту, хватит сил всех перенести на руках по одному.

Скорость их будет в одну минуту, так как второй не будет идти, а будет нестись )

Пвел (26.03.13):

Не, не получится: тот кто ходит за минуту не сможет поднять того кто ходит за 10 мин.(толстяк), получается 14 мин. хотя
10-и минутный мог на себя 5 посадить, тогда 11.

я (26.04.13):

я её давно решал получилось 16 минут минимум

Аноним (13.08.13):

19 минут (17+2). Ведь самому быстрому потребуется вернуться 2 раза (это 2 минуты).

Аноним (15.08.14):

5 минут.10 садится на плечи к 1 он его относит, так само с 5 и 2
1 2 5 10
25 1 10
1 2 5 10
2 1 5 10
1 2 5 10
1 2 5 10

Ответ редакции:

1 и 2 - хрупкие быстроногие девушки-лани, а 5-10 - мужики по полтора-два центнера каждый, не выйдет.

олег (15.08.14):

1 светит переходят по очереди(10 и 5)-10 минут, 1 и 2-2 минуты итого 12

Ответ редакции:

А как фонарик попадает к 1 и 2 после перехода 5 и 10 на другой берег?

анель (12.09.14):

мост переходят 1 и 2 . 1 возвращается . 3 и 4 переходят мост .2 возвращается . 1 и 2 переходят мост . Итого 2+1+10+2+2 = 17

Аноним (02.03.15):

вакханалия интеллекта

Ответ редакции:

Постарайтесь всё-таки все эмоциональные реакции запаковывать в один комментарий.

Спасибо

K (29.12.20):

Идет первый и несет четвертого на закорках. Оставляет на др берегу четвертого. 1 мин.
Возвращается. 1 мин.
Берет следующего - переносит. 1 мин.
Возвращается. 1 мин.
Берет следующего. 1 мин.
Итого всего 5 мин.

Ответ редакции:

Тщедущен слишком первый, не сдужит на закорках.

Бехруз пахан (04.02.22):

A,B ----- B , 2 minutes A back, 1 minute C,D ----- C,D , 8 minutes B back, 2 minutes A,B ----- A,B,C, D , 2 minutes

Копылова анна Ивановна (10.11.23):

папа с мамой; 2 мин
папа вернется.1 мин
бабушка с внуком 10 мин
мама возвращается; 2 мин
папа и мама переходят; 2 мин

		Сборник задач разного уровня сложности по математике, информатике, физике, химии, программированию, экономике etc. Логические задачи, SQL задачи, решение задач. Задачи с ответами, а также нерешённые задачи. Petruchek.Info

Petruchek.Info

Ночь. Мост. Фонарик