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$
8
-
25$\begingroup$ It should be noted that dwarves have darkvision of 60 feet and therefore don't need a lantern. $\endgroup$– DeaconDec 21, 2015 at 22:10
-
10$\begingroup$ Dwarves are pretty smart and industrious. The first pair of dwarves to cross should be holding the middle of a rope twice the length of the bridge, and set up a pulley on the other side (could just be one dwarf using his hands as a pulley). The dwarves on the other end do likewise, tying the two ends together to make a loop. Then, no dwarves ever need to make a return trip, they just tie the lantern to the rope and pull it back. $\endgroup$– Darrel HoffmanDec 21, 2015 at 22:32
-
13$\begingroup$ " No dwarf would like to go over the bridge more than 3 times " it's nice Dopey has a preference, but when Thorin Oakenshield tells him he's crossing 599 times with the lamp, well, he's in the army now. $\endgroup$– user662852Dec 22, 2015 at 0:43
-
8$\begingroup$ It will take days to finish the crossing. But in the daytime, they don't need a lantern $\endgroup$– Lance ShiDec 22, 2015 at 5:21
-
4$\begingroup$ @LanceShi: One way around that would be to specify that the river (or whatever the bridge actually spans) is underground. The sun's rays never reach it, so you need the lantern even in the daytime. $\endgroup$– The SpooniestDec 22, 2015 at 16:33
|
Show 3 more comments
5 Answers
$\begingroup$
$\endgroup$
2
Sander B's solution can be improved upon: Consider the following:
- Except for the last crossing, for every pair of dwarves crossing, 1 dwarf returns, so for each trio (2 out, 1 back), the number of dwarves on the far side increases by 1. So there must be 298 such trios, with the final crossing without return bringing the last two dwarves over. In particular, 298 times, a dwarf heads back.
- Since no dwarf will cross more than 3 times, no dwarf can return more than once. Thus 298 different dwarves return. It is evident that the best possible result would be to leave the two slowest dwarves out of this group. Then the time spent just returning will be $$1 + 2 + \ldots + 297 + 298 = \frac{298 \times 299}{2}=44551$$ minutes.
- For the forward crossings, dwarves 299 and 300 will cross once, while all the other dwarves cross twice. Of course half of the values don't contribute to the actual time, but which half? Every non-contributing time has to be matched with a higher time that contributes. So 300 must contribute. If we don't match 299 with 300, then some lower number is dropped in place of 299, and 299 contributes, which increases the total. So 300 and 299 should cross together. This leaves the two 298s that cannot be shielded. Again, if they cross with anyone other than 297, 297 will contribute instead of some lower number. Thus 298 should always pair with 297. And so on. Each even-numbered dwarf must be paired with dwarf whose number is 1 less to minimize the time. If this can be accomplished, the minimum forward crossing time is $$300+2\times(2 + 4 + 6 + \ldots + 298) \\= 300 + 4\times(1 + 2 + 3 +\ldots + 149) \\=300+4\times\frac{149\times150}{2}\\=300+44700\\=45000$$ Adding the return times gives a total time of $\ 89551$ minutes.
To accomplish it: Break the crossings up into groups of 4 crossings: (outbound, return, outbound, return). In each group, start with the 3rd and 4th highest numbers waiting to cross first, then the two highest cross. For each return, always the return the lowest number on the outward side. So the order goes $$\color{green}{297 + 298 \rightarrow\\297 \leftarrow\\299 + 300 \rightarrow\\298 \leftarrow}\\\color{blue}{295 + 296 \rightarrow\\295 \leftarrow\\297 + 298 \rightarrow\\296 \leftarrow}\\\color{green}{293 + 294 \rightarrow\\293 \leftarrow\\295 + 296 \rightarrow\\294 \leftarrow}\\\vdots\\\color{green}{1 + 2 \rightarrow\\1\leftarrow\\3 + 4\rightarrow\\2\leftarrow}\\1 + 2 \rightarrow$$
-
$\begingroup$ Nicely done. I prettied up your calculations a bit. Feel free to revert if you don't like it. $\endgroup$ Dec 23, 2015 at 12:50
-
$\begingroup$ @TheDarkTruth - Since this isn't MathExchange, I had chosen to avoid sigma notation to make it a little more accessible. So I will probably change that part back later (no time now), but otherwise, thank you. $\endgroup$ Dec 23, 2015 at 13:39
$\begingroup$
$\endgroup$
1
It should take them 89,700 minutes.
We use the following strategy:
We leave the 300 minute dwarf for the last trip.
Every time we send two of them over we send those two that take the most time out of all remaining ones. (excluding the 300 minute dwarf)
Every time we send someone back we send the one that needs the smallest amount of time out of the two that just got over the bridge.
The last trip will be made by the 300 minute dwarf and the 1 minute dwarf.
The trips will look something like this:
299 298 -> | 298 <-
298 297 -> | 297 <-
...
3 2 -> | 2 <-
2 1 -> | 1 <-
300 1 ->
The result:
The trips to the other side will take a total of 45149 minutes since every dwarf except the 1 minute one will be the slower one exactly once.
$$\frac{300 \times 301}{2}-1=45149$$
The trips back will be taken by every dwarf except the 300 and 299 minute ones for a total of 44551 minutes.
$$\frac{298\times 299}{2}=44551$$
Total:
$$45149+44551=89700$$
Why this is the fastest you can get:
First we look at the walks back:
We must have 298 walks back and every dwarf can only walk back once so we just let the 298 fastest dwarfs go back once each.
As for the walks forward:
With two exceptions every dwarf will have to walk forward twice.
At least one of those walks every dwarf should be the slower one as otherwise one dwarf that is even slower will have to be the slower one twice.
The two exceptions will be the two that never walk back.
And since we only have 299 walks forward the 1 will be the smaller one twice
answered Dec 21, 2015 at 22:16
-
$\begingroup$ That's two months. Surely there is plenty of daylight during this time when they can move faster ans they don't need a lamp. :) It could be underground, but the question specified that it's in the middle of the night, and it seems to be an important information. $\endgroup$– vszDec 22, 2015 at 18:03
$\begingroup$
$\endgroup$
1
1 and 2 go over: 2 minutes
1 comes back : 1 minute
1 and 3 go over: 3 minutes
2 comes back : 2 minutes
2 and 4 go over: 4 minutes
3 comes back : 3 minutes
3 and 5 go over: 5 minutes
4 comes back : 4 minutes
4 and 6 go over: 6 minutes
5 comes back : 5 minutes
...
297 comes back : 297 minutes
297 and 299 go over: 299 minutes
298 comes back : 298 minutes
298 and 300 go over: 300 minutes
This sums to 89,700 minutes
-
$\begingroup$ This is tidy, simple and understandable answer to me! ^^ $\endgroup$– NaiDec 23, 2015 at 10:32
$\begingroup$
$\endgroup$
5
Every dwarf, except the last, makes 3 trips. For each pair, they first go over at the even's speed, then the odd comes back (1x per dwarf).
Once all the evens are across (and odds on the starting side):
1 and 3 go over, 2 comes back
2 and 5 go over, 4 comes back
4 and 7 go over, 6 comes back
6 and 9 go over, 8 comes back
Times are: 3,2,5,4,7,6,9,8 etc. Again, 1x per dwarf, except the first and last.
1-300 sums to 45,150. Double is 90,300. Less 1 and 300 = $89,999$
-
-
$\begingroup$ @dperry By my quick guess, it's closer to 2 months. $\endgroup$ Dec 21, 2015 at 20:56
-
-
7$\begingroup$ So, by waiting until sunrise they could avoid torch passing, hence making it past the bridge in about one month, assuming 12 hours of daylight? :-) $\endgroup$ Dec 21, 2015 at 21:00
-
5$\begingroup$ They're dwarves. It's clearly an underground bridge and therefore it's always dark. $\endgroup$– DuncanDec 21, 2015 at 21:38
$\begingroup$
$\endgroup$
2
My answer: 89699
How? Let's see for 6 dwarves:
1 and 2 go -> 2
1 returns -> 1
6 and 5 go -> 6
2 returns -> 2
4 and 3 go -> 4
3 returns -> 3
1 and 3 go -> 3
4 returns -> 4
2 and 4 returns -> 4
So the sum for 6 is 1 + 2 + 2 + 3 + 3 + 4 + 4 + 4 + 6
Clearly, the first dwarf only benefits once from his speed, the third last dwarf has to cross three times at his speed, the second-last and last only once (at the speed of the last dwarf). all the others go 3 times; but ony 2 times at their speed (and once with a slower dwarf). Putting it together:
For n: 1 + 2*sum(2..n-3)+ 3*n-2 + n
For 300: 1 + 2*sum(2..297) + 3*298 + 300 = 1 + 88504 + 894 + 300 = 89699
-
$\begingroup$ First 1,2. Then 6,5. Then 4,3. Then 1,3. Then 2,4. I'm not seeing the pattern in which you're having them go. Are you sure it works for more than 6 dwarves? Say, 10? $\endgroup$ Dec 22, 2015 at 22:48
-
$\begingroup$ Thank you for pointing that out, Paul. I have corrected my answer. (and upvoted yours, congrats). I remembered it wasn't a easy solution like the ones given before. @twasbrillig, I know my answer doens't match a pattern, but the sum does. I'did test it but I didn't type these other cases. $\endgroup$– Sander BDec 23, 2015 at 8:35