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?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Nothing, I have no idea??? $\endgroup$– algebra1Dec 21, 2015 at 20:41
-
1$\begingroup$ Where did you get this puzzle, then? It might give answerers an idea of the complexity. $\endgroup$– Thomas AndrewsDec 21, 2015 at 20:43
-
1$\begingroup$ Well, to begin with, in order to answer "what is the minimum time they can manage the transition" - have you tried finding a "not-necessarily-minimum time they can manage the transition"? $\endgroup$– barak manosDec 21, 2015 at 20:43
-
2$\begingroup$ There needs to be 299 crossings of pairs to the destination. Every time, at least one must come back. Since a crosser can only come back once, that means the 298 different dwarves have to come back and thus cross three times. Try to make the ones that come back the fastest, and try to pair dwarves up with dwarves of close to the same speed. $\endgroup$– Thomas AndrewsDec 21, 2015 at 20:48
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ XD Love using math in such ways. But who goes first? Who goes next, next, and so on? $\endgroup$ Dec 23, 2015 at 0:40
$\begingroup$
$\endgroup$
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.
answered Dec 21, 2015 at 20:48
$\begingroup$
$\endgroup$
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.
answered Dec 23, 2015 at 0:49