The queer shape

[theblackalchemist]

hey all,

i've got this question.

i opened paint and dropper a few points on it.

to explain what i want, let us take an example.

the black points are travellers stranded on a desert with no supplies :)

they only have a vehicle, that can survive a short distance, which is with one random person.

 

they need to get to the red point.

 

how can they do it, while those who walk, do so in a short distance, and the one who drives, picks up all, too in a short distance

 

or

 

all cover the minimum distance possible.?

i hope this is clear

 

PS> you can edit and upload the image.

also you can exceed the circle if needed

THX

TBA

[theblackalchemist]

when i tried solving it, this solution came into my mind.

 

also this

 

the red line is of the car,

the blue line is of the people who walk to pick up the car.

and the remaining dont get a lift.

 

clearly a few people dont survive a walk

 

any thoughts?

[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 [math]T_i[/math] can walk a distance no more than [math]D_i[/math];

One traveler [math]T_x[/math], is a car that can travel distance [math]D_x[/math]. 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 [math]D_i[/math] to the position of each traveler [math]T_i[/math] except [math]T_x[/math]; The end of each string has an eyelet (loop) allowing it to slide smoothly over another string;
   
2. Attach a “main” string to [math]T_x[/math]. 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 [math]L[/math] of the main string is not greater than [math]D_x[/math], the travelers can reach the oasis by walking to the point indicated on the map where their eyelets touch the main string, while [math]D_x[/math] follows the path indicated by the main string;
   
5. If [math]L[/math] is greater than [math]D_x[/math], 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.