Way 2 Freshers

Bicycle puzzle

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?
A boy, a girl and a dog are standing together on a long, straight road. Simulataneously, they all start walking in the same direction: The boy at 4 mph, the girl at 3 mph, and the dog trots back and forth between them at 10 mph. Assume all reversals of direction instantaneous. In one hour, where is the dog
and in which direction is he facing?

solution:

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.

As for the linear program which gives the lower bound of 2.75 hours, let [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.