All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math > Calculus
Minimum time (Posted on 2008-12-04) Difficulty: 3 of 5
N people can walk or drive in a single two-seater car to go from city A to city B. What is the minimum time required to do so?

1) the speed of the car: c
2) the speed of a walking person: p
3) the distance between cities: D
4) all persons start out from A at the same time t = 0.
5) all persons arrive in city B at the same time t = T.
6) nobody stands around idly waiting.
7) the car never holds more than two people

  Submitted by pcbouhid    
Rating: 4.3333 (3 votes)
Solution: (Hide)
See Steve Hermanīs solution here.

Another approach:

Let's plot everyone's movements on a graph showing coordinates (t,x).

Then at time t just after 0, (N-2) walkers are on the line L0 through (0,0) with slope dx/dt = p, and 2 in the car are on a line through (0,0) with slope c, and at t just before T, (N-2) walkers are on the line L1 through (T,L) with slope p, and 2 in the car are on a line through (T,L) with slope c.

Obviously L1 lies "above" L0 (greater x coordinate given the same t coordinate).

In between t=0 and t=T, the car zigzags between L0 and L1 along lines of slope c and -c, picking up people from L0 and dropping them off at L1. (note from the author: "I will not prove that this is the optimal strategy; in fact you can make an infinite number of variations on it which all come up with the same elapsed time.")

Now examine the graph again. Say the car travels distance r between picking someone up and dropping that person off, and distance s back to pick up the next person. The car makes (N-1) trips forward and (N-2) trips back to pick up and ferry everyone, so its total travel is:

cT = (N - 1)r + (N - 2)s = (N - 2)(r + s) + r

Moreover the car makes (r-s) net displacement on each round trip, plus r displacement on the extra forward trip, so:

D = (N - 2)(r - s) + r

Note that a person walks distance (r-s) in the time it takes the car to go (r+s), so:

r - s = (p/c)(r + s)

A little algebraic manipulation of this equation shows us that:

r - s = r * 2p/(c + p)
r + s = r * 2c/(c + p)

Plug this into the equation for D, and we get the first important piece of information, how far the car should drive before dropping off the passenger (once you know this, you tell it to the driver and this guarantees the people get to B in minimum time):

D = r + (N - 2) r * 2p/(c + p)
D = r * (c + p + (N - 2)*2p)/(c + p)
                 c + p
	r = ------------ D
	    2pN + c - 3p
We can also find out what the elapsed time T will be:

cT = (N - 2)r*2c/(c + p) + r

= r * ((N - 2)*2c + c + p)/(c + p)
	    1   2cN - 3c + p
	T = - * ------------ r
	    c      c + p
	    (2N - 3)c + p
	T = -------------- (D/c)
	    (2N - 3)p + c

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Some Thoughtsre: No calculus involvedAdy TZIDON2008-12-07 13:17:34
re(2): No calculus involved -------- I forgotSteve Herman2008-12-06 19:09:31
re: No calculus involved -------- I forgotpcbouhid2008-12-06 13:29:27
re: No calculus involvedCharlie2008-12-06 13:06:57
SolutionNo calculus involvedSteve Herman2008-12-06 10:13:25
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information