кроссворды, задачки, головоломки

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

Petruchek.Info

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

Добавлено: 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):
вакханалия интеллекта
   Ответ редакции
Постарайтесь всё-таки все эмоциональные реакции запаковывать в один комментарий.

Спасибо
Комментарий от новенького:
Новенький является
Новенький не робот
Знаки на картинке: латинские буквы, арабские цифры


Есть на сайте: Онлайн кроссворды Задачи Онлайн игры Блог
Все работы, опубликованные на сайте — авторские, если не указано иное. Перепечатка возможна только с письменного разрешения владельцев ресурса, с обязательной ссылкой на сайт petruchek.info. Пишите нам: . Сайт должен работать в IE, FF, Opera, Safari.

Реклама:

Разработано в студии "Webous"о проектесайта карта

Реклама: