Science Forums 2

[CraigD]

Restating the problem as follow:

Given:
A number n travelers are stranded in the desert at various distances and directions from an oasis;
Each traveler can walk a distance no more than ;
One traveler , is a car that can travel distance . The car can carry any number of travelers.

How can all of the travelers reach the oasis?

It can be solved using a “tight string” approach:

1. On a map of the problem, attach strings of length to the position of each traveler except ; The end of each string has an eyelet (loop) allowing it to slide smoothly over another string;
2. Attach a “main” string to . Thread it through the eyelets on each of the other strings, and through an eyelet attached to the oasis;
3. Pull the main string ‘till it’s tight;
4. If the length of the main string is not greater than , the travelers can reach the oasis by walking to the point indicated on the map where their eyelets touch the main string, while follows the path indicated by the main string;
5. If is greater than , repeat from step 2, threading the main string thought the eyelets in a different order; If all possible orders are tried without success, the problem has no solution.

Note that only the main string will necessarily be tight after step 3. One or more of the other strings may be loose.

Here’s a picture of a possible solution. The circles are those inscribed by the many strings, and aren't part of the solution. It’s hand/mouse-drawn, so may not be very accurate.

The “tight string” solution is sometimes associated with solving network problems, such as “word web” puzzles where you must change one word into another by changing one letter at a time following certain rules. That’s where I first found it. It’s possible to compute a solution by modeling the physics of the strings, though it’s easier for most people to solve the problem with a physical map, strings, and pins.

Step 5 is a variation on the traveling salesman problem. If there are a lot of travelers, it can take a lot of tries to complete.