Strategic Paddling

A strong canoe paddler can achieve a water speed of about nine kilometers per hour. Most paddlers can achieve water speeds of at least two kilometers per hour pretty much indefinitely.

If a waterway is flowing against the paddler at speed w and the paddler has a water speed of s, then the paddler will achieve a land speed of s – w. This has consequences.

Warm-Up: Consider a system of waterways like that in the first illustration in this column, where each segment is one kilometer long, the segments in black flow downstream at three kilometers per hour, and the segments in red flow downstream at 1.5 kilometers per hour. Suppose a paddler is capable of paddling for a total of one hour at four kilometers per hour and then indefinitely at two kilometers per hour. What is the best route to choose from the bottom to the top and how long will that take?

Figure. A canoe paddler can achieve a water speed of four kilometers per hour (km/hr) for one hour and two kilometers per hour indefinitely. What is the fastest way to go from the downstream point to the top point?

Solution to Warm-Up: Paddle at four kilometers per hour (water speed) on the black segment, reaching the middle point after one hour. Then paddle at two kilometers per hour (water speed) on the top red segments. This will take another four hours to reach the top because the effective land speed is only 0.5 kilometers per hour.

OK, I think you are ready for more now.

Challenge: Suppose there is only one route of four kilometers along which the first two kilometers flow downstream at one kilometer per hour and the second two-kilometer segment flows downstream at two kilometers per hour. If a paddler can paddle at four kilometers per hour for one hour and three kilometers per hour for another hour, how should the paddler paddle to finish the course as fast as possible?

Solution: In the first hour, the paddler achieves a water speed of four kilometers per hour on the two-kilometer long, two kilometers per hour downstream segment thus finishing that segment. In the second hour, the paddler achieves a water speed of three kilometers per hour on the two kilometer-long one kilometer per hour downstream segment, thus completing the route. If the paddler paddles at three kilometers an hour on the first segment and then four kilometers an hour on the second segment, the time will be 2 1/3 hours.

Figure. A network of waterways. Depending on the strength of the paddler (see text), the paddler may take different routes.

Challenge: Prove that if there is only a single route, then the paddler will reach the destination earlier by paddling as fast as possible on the fastest downstream flowing part as long as possible?

Proof strategy: Imagine there is another strategy in which it is better to paddle faster on a slower downstream flow than on a faster downstream flow. Show that swapping so that you paddle on a faster downstream flow reduces the time. For example, consider the proof provided by my colleague Ernie Davis: http://cs.nyu.edu/cs/faculty/shasha/papers/ernieproof_canoe.pdf

Challenge: Consider the situation show in the second figure here.

1. If the paddler P can paddle with a water speed of two kilometers per hour only, then what is the best route P can take and how long will it take?
2. If the paddler P can paddle with a water speed of three kilometers per hour for one hour but two kilometers per hour at all other times, then what is the best route P can take and how long will it take?
3. If the paddler P can paddle with a water speed of three kilometers per hour for two hours but two kilometers per hour at all other times, then what is the best route P can take and how long will it take?
4. If the paddler P can paddle with a water speed of three kilometers per hour for three hours but two kilometers per hour at all other times, then what is the best route P can take and how long will it take?

Solutions:

1. d. ABCDF: nine hours
2. ABCEF: five hours (paddles at three kilometers per hour between E and F)
3. ACEF: four hours (paddles at three kilometers per hour between A and C and between E and F)
4. ACEF or AEF: three hours (paddles at three kilometers the whole time).

Paddling Upstart: Given a general network of different downstream flows and a variety of paddle speeds with their durations, what is the best route to take and at which speeds? Please design an algorithm and provide an implementation in some widely used computer language (or several:).