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.
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.
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:).
All are invited to submit their solutions to email@example.com; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.
No entries found