This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

A boy, a girl and a dog go for a 10 mile walk. The boy and girl can

walk at 2 mph and the dog can trot at 4 mph. They also have a bicycle

which only one of them (including the dog!) can use at a time. When

riding, the boy and girl can travel at 12 mph while the dog can pedal

at 16 mph. What is the shortest time in which all three can complete

the trip?

analysis/bicycle.s

First note that there's no apparent way to benefit from letting either the

boy or girl ride the bike longer than the other. Any solution which gets the

boy there faster, must involve him using the bike (forward) more; similarly

for the girl. Thus the bike must go backwards more for it to remain within

the 10-mile route. Thus the dog won't make it there in time. So the solution

assumes they ride the bike for the same amount of time.

Also note that there's no apparent way to benefit from letting any of the three

arrive at the finish ahead of the others. If they do, they can probably take

time out to help the others. So the solution assumes they all finish at the

same time.

The boy starts off on the bike, and travels 5.4 miles. At this

point, he drops the bike and completes the rest of the trip on foot. The

dog eventually reaches the bike, and takes it *backward* .8 miles (so the

girl gets to it sooner) and then returns to trotting. Finally, the girl makes

it to the bike and rides it to the end. The answer is 2.75 hours.

The puzzle is in Vasek Chvatal, Linear Programming, W. H. Freeman & Co.

The generalized problem (n people, 1 bike, different walking and riding speeds)

is known as "The Bicycle Problem". A couple references are

Masuda, S. (1970). "The bicycle problem," University of California, Berkeley:

Operations Research Center Technical Report ORC 70-35.

Chvatal, V. (1983). "On the bicycle problem," Discrete Applied Mathematics 5:

pp. 165 - 173.

As for the linear program which gives the lower bound of 2.75 hours, let

t[person, mode, direction] by the amount of time "person" (boy, girl or dog)

is travelling by "mode" (walk or bike) in "direction" (forward or backwards).

Define Time[person] to be the total time spent by person doing each of these

four activities. The objective is to minimize the maximum of T[person], for

person = boy, girl, dog, e.g.

minimize T

subject to T >= T[boy], T >= T[girl], T >= T[dog].

Now just think of all the other linear constraints on the variables t[x,y,z],

such as everyone has to travel 10 miles, etc. In all, there are 8 contraints

in 18 variables (including slack variables). Solving this program yields the

lower bound.

Continue to: