BrainDen.com - Brain Teasers
• 1

# 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.

## Recommended Posts

• 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)

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

##### 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 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.

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 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 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 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)

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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.