+ 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.

10th May 2021, 8:22 PM
Fernando Moceces
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
10th May 2021, 11:14 PM
Benjamin Jürgens
+ 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)
10th May 2021, 8:22 PM
Fernando Moceces
+ 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
10th May 2021, 11:04 PM
Benjamin Jürgens
0
Benjamin Jürgens thank you very much!
11th May 2021, 12:37 AM
Fernando Moceces
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
11th May 2021, 7:52 AM
Benjamin Jürgens