162.6866: optimal solution for the "so so difficult problem".

1. We prove that if ignoring 5, and assuming there are only 4 people with speed 1,2,3 and 4, then the optimal solution is 162.6866, by the following strategy:

a. let car pick 2,3 and go to some point.
b. let car go back and pick 4, and then catch up with 2.
c. let car pick 2 up and catch up with 3.

At this moment, we have 2,3,4 at the same point. Let's call such a state "*". It is easy to see from a * state to the next * state by repeating a, b and c, the average speed (of 2, 3 and 4) is a constant 6.1468. So the time spent to go 1000 is 1000/6.1468 = 162.6866. This can be proved to be optimal by exhaustive cases study. For the targeted audience of this article, no more words need to be spent.

2. We prove that for the case of 5 people with speed 1,2,3,4 and 5, the optimal couldn't be better than the 4 people case. This is so obvious.

3. We prove 162.6866 is doable in 5 people case, and here is (briefly) how:
a. let car pick 2,3 and go ahead to some point.
b. let car go back and pick 4 FIRST and then 5 and catch up with 2.
c. let car drop 5 and pick 2 and carry 2 and 4 to catch up with 3.

At this moment, 2,3,4 are at the same point and 5 is falling behind for a distance, let's call such a state "*". It is easy to see from a * state to the next * state by repeating a, b and c, as long we make sure

in step b the car picks up 4 first and then 5,
the average speed (of 2, 3 and 4) is also 6.1468, which is exactly the same as the 4 people case. So it is trivial to see that, without caring about 5, which is falling behind, 2,3 and 4 can travel at the speed 6.1468.

Now here is the best part: we do not really need to care about 5! And here is why: from a * state to the next * state, the distance that 5 is falling behind is reducing at a constant rate r, where r >= 0.5357. This basically means, as long as we repeat the steps a,b and c for enough number of times, 5 is catching up with 2,3 and 4 automatically. In other words, as long as we repeat a,b and c enough, the average speed for 2,3,4 and 5 is constantly 6.1468. So 1000 / 6.1468 = 162.6866 is doable in 5 people case.

所有跟帖： 

• Is 2,3,4's speed the same in the 2nd iteration as in the 1st? -endofsuburbia- ♂ (82 bytes) () 10/09/2008 postreply 13:03:55

• good question and bad question -火球魔法- ♂ (1404 bytes) () 10/09/2008 postreply 15:45:22

• Same as 康MM's solution -15少- ♂ (0 bytes) () 10/09/2008 postreply 16:10:47

• ok, but -火球魔法- ♂ (363 bytes) () 10/09/2008 postreply 16:23:13

• 关于 康MM's solution -koushi321- ♀ (526 bytes) () 10/14/2008 postreply 15:08:06

• It's still not very clear to me -endofsuburbia- ♂ (213 bytes) () 10/09/2008 postreply 17:59:01

• 回复：It's still not very clear to me -火球魔法- ♂ (46 bytes) () 10/09/2008 postreply 18:38:58

• 回复：It's still not very clear to me -火球魔法- ♂ (162 bytes) () 10/09/2008 postreply 18:40:06

• 讨教一下，你的average speed是怎么算的。 -koushi321- ♀ (0 bytes) () 10/14/2008 postreply 14:59:25