+ 1

# Bridge Torch Problem

A group of people are trying to cross a dark bridge. Each person has different walking speed. There is only one torch. The bridge can only be walked on by no more than two people at a time. Calculate the minimum time needed to cross the bridge and the walking arrangement. Example: 4 people with speeds in minute 1,2,5,8 Will need 15 minutes [1,2,5,8] => [ ] => [ ] [5,8] => [1,2] => [ ] [5,8] => [1] => [2] [1] => [5,8] => [2] [1] => [2] => [5,8] [ ] => [1,2] => [5,8] [ ] => [ ] => [1,2,5,8] 2 + 1 + 8 + 2 + 2 = 15 menit Please find the solution for 1,6,10,13,15,16,17 They say it's 75 but I got 77 My solution is in the comment below.

5 Réponses

+ 3

Using indices of the ordered list the scheme for the sum will be [2]+[1]+[-1]+[2]+[2]+[1]+[-3]+[2]+...
It repeats in blocks of 4 steps, moving the two slowest remaining persons with each block

+ 1

My solution:
[1,6,10,13,15,16,17] => [ ] => [ ]
[10,13,15,16,17] => [1,6] => [ ]
[10,13,15,16,17] => [1] => [6]
[1,10,13,15] => [16,17] => [6]
[1,10,13,15] => [6] => [16,17]
[6,10,13] => [1,15] => [16,17]
[6,10,13] => [1] => [15,16,17]
[6,10] => [1,13] => [15,16,17]
[6,10] => [1] => [13,15,16,17]
[6] => [1,10] => [13,15,16,17]
[6] => [1] => [10,13,15,16,17]
[ ] => [1,6] => [10,13,15,16,17]
6 + 1 + 17 + 6 + 15 + 1 + 13 + 1 + 10 + 1 + 6 = 77
Not 75
Please arrange the walking so the minimum time is 75 (if it really is possible)

+ 1

The trick is to combine the slow ones. Like 5 and 8 in example, so 5 is never counted. The two fastest can go back and forth multiple times as that adds only small amounts. 16 and 17 go together, later 13 and 15.
I am unsure if there are constellations where this scheme is not the fastest but I think it always is. But there are constellations with other equally fast solutions.
Solution in detail:
1 6 ->
<- 1
16 17 ->
<- 6
1 6 ->
<- 1
13 15 ->
<- 6
1 6 ->
<- 1
1 10 ->
6+1+17+6+6+1+15+6+6+1+10=75

0

Benjamin Jürgens thank you very much!

0

Fernando Moceces you're welcome. The general things i said i would consider assumptions, i.e. i didn't think about any proofs but couldn't find any contradicting examples