Dwarfs over a bridge

Question

300 dwarfs go over a bridge in the middle of the night. The bridge is rickety and manages at most two dwarfs at a time. With them is a lantern that they must provide at each transition. Dwarfs need different time to go over the bridge: 1 min, 2 min, 3 min ... and 300 minutes. When two dwarves go over, they go with the slowest one's speed. No dwarf would like to go over the bridge more than 3 times (ie, front-back-front). What is the minimum time they can manage the transition?

Answer 1

Hint: if two go over and one comes back, you leave one dwarf at the far end and the lantern back at the near end. How many trips does that require to get all 300 dwarves across the bridge? There is a slight perturbation at the end. How many have to come back? You clearly want the fastest ones coming back.

Answer 2

Suppose we have $n$ dwarves and let $x_i$ be the time the $i$th crossing dwarf needs to cross the bridge. Note that whatever couple you send in the beginning, it's best to return the quickest dwarf. Therefore the total crossing time is equal to $$ \max\{x_1,x_2\} + \min\{x_1,x_2\} + \sum_{i=3}^{n-1}x_i + \sum_{i=2}^{n-1}\max\{x_i,x_{i+1}\}, $$ which equals (assuming $x_1>x_2$) $$ \sum_{i=1}^{n-1}x_i + \sum_{i=2}^{n-1}\max\{x_i,x_{i+1}\}, $$ Next, we fix the dwarf on place $n$ and see that it's best to have dwarf 1 the slowest remaining dwarf, since changing dwarf 1 with dwarf $k<n$ such that $x_k>x_2$ raises the total crossing time by \begin{align} \max\{x_{k-1},x_1\} + \max\{x_1,x_{k+1}\} &- \max\{x_{k-1},x_k\} - \max\{x_k,x_{k+1}\} = \\ 2x_1 &- \max\{x_{k-1},x_k\} - \max\{x_k,x_{k+1}\} > 0. \end{align} Similarly, given that we fix dwarf $1$ its best to have dwarf n the slowest remaining dwarf, since changing dwarf $n$ with dwarf $k$ raises the total crossing time by \begin{align} x_n-x_k + \max\{x_{k-1},x_n\} + \max\{x_n,x_{k+1}\} - \max\{x_{k-1},x_k\} - \max\{x_k,x_{k+1}\} - (\max\{x_{n-1},x_n\} - \max\{x_{n-1},x_k\}) = \\ 2x_n - \max\{x_{k-1},x_k\} - \max\{x_k,x_{k+1}\} + \max\{x_{n-1},x_k\} - x_k > 0. \end{align} We conclude that $x_1$ and $x_n$ have to be the two slowest dwarfs. This means we have to find an order for dwarfs $2,\ldots,n-1$ that minimizes $$ \sum_{i=1}^{n}x_i + \sum_{i=2}^{n-2}\max\{x_i,x_{i+1}\}, $$ which equals minimizing $$ \sum_{i=2}^{n-2}\max\{x_i,x_{i+1}\}. $$ See for yourself that this is done by ordering the $x_i$ from either fastest to slowest, or slowest to fastest.

We conclude that the minimal total time taken equals \begin{align} \sum_{i=1}^{300}i + \sum_{i=2}^{298}\max\{x_i,x_{i+1}\} &= \sum_{i=1}^{300}i + \sum_{i=2}^{298}i \\ &= 2\sum_{i=1}^{300}i - 1-299-300 \\ &= 2\frac{300(300+1)}{2} - 600 \\ &= 300^2 - 300 \end{align} Note that we have found four unique solutions for which this minimum is attained.

Answer 3

According to what I believe is the same way you solve a similar bridge crossing problem, you start with the two fastest people running across the bridge.

Then one of them runs back to return the lamp.

The two slowest cross the bridge next. By sending the 2 slowest, you minimalize the time lost by them.

Once they are crossed, the other guy (one of the fast ones) runs back with the lamp.

The two fastest runners other than the original 2 go next. We repeat this process, having the 2 slowest walking across together and fastest running back and forth.

We do this until 100 slow dwarves have made it across.

We now have 200 dwarves left.

The 100 fastest ones have already went across the bridge twice, so this third run will be their last.

But someone needs to be able to carry the lamp back!

So we make pairs between the current 66 slowest runners and 66 fastest runners.

They will run across, after which the slow runners return the lamp back.

Repeat this until all 66 fastest runners make their final lap.

We are now left with 68 dwarves.

The trick was to take the fastest 1/3 and slowest 1/3, allowing the middle 1/3 to carry lamps back at the very end.