Jump to content
BrainDen.com - Brain Teasers
  • 1
bonanova

Salesman in a Square

Question

Al made sales calls at a number of cabins, which lay in a square field, one mile on a side. He drove his car to the first cabin, then visited the remaining cabins and returned to his car on foot, walking several miles in the process. If Al had had a map and perhaps a computer, he could have picked the shortest route to take, (traveling salesman problem). Lacking these amenities, Al simply chose to visit (after the first one) the (un-visited) cabin closest to his current location.

If there were 6 cabins in all, how might they be placed, so that using Al's nearest-neighbor algorithm, and selecting the worst initial cabin, Al would be forced to walk the greatest distance; and what is that distance?

Examples:

2 cabins: diagonal corners, starting at either: 2 x sqrt(2) = 2.828... miles.
3 cabins: any three corners, starting at any of them: 2 + sqrt(2) = 3.414... miles.

Check out n=4 and n=5 as a warm-up.

 

Share this post


Link to post
Share on other sites

6 answers to this question

  • 1

Think I have the ideal solution here

Spoiler

A (0,0); B (1,0); C(1,1); D (0,1); E (cos(30),sin(30)); F (cos(60),sin(60))

This solution assumes if you are excatly the same distance from points you get to choose. Very slight tweaks to the points can force the longest path

Start at A. B,D,E&F are all 1 mile away so pick E (+1 mile)

At E. B and F are both same distance away (2 sin(15)~.5176) so pick B  (+.5176 mile)

At B. A,E,&F are all 1 mile away so pick F (+1 mile)

At F, D is closest (2 sin(15)) (+.5176 mile)

At D, C is closest (+1 mile)

At C, return to A (2^.5~1.414

Total distance walked= 3*(1)+2*(2sin(15))+2^.5~5.449

 

 

Share this post


Link to post
Share on other sites
  • 1

 

Spoiler

 

My intuitive placement and path of the cabins would be thus:
Let the vertices of the square be A, B, C, D with the diagonals being AC and BD.

Let the first cabin [a] be at point A.
Let the second cabin be a walk of 1 mile from A along the diagonal AC.
Let the third cabin [c] be perpendicular to diagonal AC on side CD.
Let the fourth cabin [d] be at or on toward point D at no less distance than point C from cabin ;
this should be approximately 0.4 miles distant from cabin [c].
Let the fifth cabin [d] be at point C.
Let the sixth cabin [e] be at point B.
Finally, a return to the car at cabin [a], point from cabin [e] A requires another walk of 1 mile.
Accumulative walk is approximately 4.8 miles.

 

 

Share this post


Link to post
Share on other sites
  • 0
13 hours ago, DejMar said:

 

  Hide contents

My intuitive placement and path of the cabins would be thus:
Let the vertices of the square be A, B, C, D with the diagonals being AC and BD.

Let the first cabin [a] be at point A.
Let the second cabin be a walk of 1 mile from A along the diagonal AC.
Let the third cabin [c] be perpendicular to diagonal AC on side CD.
Let the fourth cabin [d] be at or on toward point D at no less distance than point C from cabin ;
this should be approximately 0.4 miles distant from cabin [c].
Let the fifth cabin [d] be at point C.
Let the sixth cabin [e] be at point B.
Finally, a return to the car at cabin [a], point from cabin [e] A requires another walk of 1 mile.
Accumulative walk is approximately 4.8 miles.

Not a bad result.

Spoiler

The locations (four corners, side and circular arc) are all correct. But adjusting the last two a bit, and changing the first cabin, in order to alter the sequence, the distance can exceed 5.

 

 

Share this post


Link to post
Share on other sites
  • 0

Modified solution:
 

Spoiler

Let the following lettered points also be the labels of the six cabins. Let the vertices of the SQUARE be AEDF.
Let the midpoint of DF be C. Let B be the midpoint between CE.

The first leg would be approximately 0.83 miles from cabin A to B.
The second leg would be approximately 1.12 miles from B to C.
The third leg would be 0.50 miles from C to D.
The fourth leg would be 1.00 mile from D to E.
The fifth leg would be approximately 1.41 miles from E to F.
The sixth leg would be 1.00 mile from F to A.

The leg-journey will be approximately 5.83 miles.

 

Share this post


Link to post
Share on other sites
  • 0

Correction to modified solution. (It appears I incorrectly calculated the second leg's length by failing to divide it by 2, and my approximation of the first leg also needed adjusting.)

 

Spoiler

The lengths of each leg of the salesman's path should be as follows:
Cabin A to Cabin B = (√(13)/4) miles.
Cabin B to Cabin C = (√(5)/4) miles
Cabin C to Cabin D = 1/2 mile
Cabin D to Cabin E = 1 mile
Cabin E to Cabin F = √(2) miles.
Cabin F to Cabin A = 1 mile.

Total length of the salesman's journey: approximately 5.37 miles.

 

Edited by DejMar
correcting math

Share this post


Link to post
Share on other sites
  • 0
2 hours ago, tojo928 said:

Think I have the ideal solution here

  Hide contents

A (0,0); B (1,0); C(1,1); D (0,1); E (cos(30),sin(30)); F (cos(60),sin(60))

This solution assumes if you are excatly the same distance from points you get to choose. Very slight tweaks to the points can force the longest path

Start at A. B,D,E&F are all 1 mile away so pick E (+1 mile)

At E. B and F are both same distance away (2 sin(15)~.5176) so pick B  (+.5176 mile)

At B. A,E,&F are all 1 mile away so pick F (+1 mile)

At F, D is closest (2 sin(15)) (+.5176 mile)

At D, C is closest (+1 mile)

At C, return to A (2^.5~1.414

Total distance walked= 3*(1)+2*(2sin(15))+2^.5~5.449

 

 

Spoiler

Extremely close to optimal. So close I'm declaring it solved.

Spoiler

The best solution I know of has length of L = (5+√2+√5+√6) / 2 = 5.549+ by moving one of your points (E) to the center of side AB and starting by going from that point to B. Check it out.

 

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×