==> 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.