Jump to content
BrainDen.com - Brain Teasers
  • 0

Walking man's delight


bonanova
 Share

Question

Enough with traveling salesman who hate long road trips.

Mario Andretti has joined the team, and he loves to drive!

His route today comprises eight towns, placed at the corners of an octagon.

Here are their coordinates:

post-1048-0-45677600-1368577451_thumb.gi

Edit: 7 and 8 are labeled incorrectly. They should be switched.

+---+-+-+

City x y

+---+-+-+

1 0 2

2 0 4

3 2 6

4 4 6

5 6 4

6 6 2

7 4 0

8 2 0

+---+-+-+

The inter-city distances, to save some calculations, are N-S and E-W distances of 6, along with four different diagonal distances of 2.828, 4.472, 5.657 and 6.083 6.325

If Mario begins driving at city 1 (coordinates 0 2) and drives until he has visited them all, how far will he be able to drive, and what city will he visit last?

If his objective is to return to his hotel in City 1 after visiting the other cities, how long of a trip could he accomplish?

Edited by bonanova
Switch 7 and 8 on the graph and correct 6.063 to 6.325
  • Upvote 1
  • Downvote 1
Link to comment
Share on other sites

15 answers to this question

Recommended Posts

  • 0

Enough with traveling salesman who hate long road trips.

Mario Andretti has joined the team, and he loves to drive!

His route today comprises eight towns, placed at the corners of an octagon.

Here are their coordinates:

attachicon.gifsalesman.gif

+---+-+-+

City x y

+---+-+-+

1 0 2

2 0 4

3 2 6

4 4 6

5 6 4

6 6 2

7 4 0

8 2 0

+---+-+-+

The inter-city distances, to save some calculations, are N-S and E-W distances of 6, along with four different diagonal distances of 2.828, 4.472, 5.657 and 6.083

If Mario begins driving at city 1 (coordinates 0 2) and drives until he has visited them all, how far will he be able to drive, and what city will he visit last?

If his objective is to return to his hotel in City 1 after visiting the other cities, how long of a trip could he accomplish?

Are you saying what is the greatest path?

  • Upvote 1
  • Downvote 1
Link to comment
Share on other sites

  • 0

Yes. But visit each city only once.

If we are able to backtrack or drive aimlessly then it could take infinitely long.

I am working out the possible distance if a person must go in straight lines. Now my question is, can they cross over the same point? If i go diagonal between two cities, when going to a different city may i travel back over a common point or must each visit be completely unique. In other words in my travels between three cities may my path form a modified x (intersecting segments) or would i have to more likely make a U (no intersection segments)?

Link to comment
Share on other sites

  • 0

Yes. But visit each city only once.

If we are able to backtrack or drive aimlessly then it could take infinitely long.
I am working out the possible distance if a person must go in straight lines. Now my question is, can they cross over the same point? If i go diagonal between two cities, when going to a different city may i travel back over a common point or must each visit be completely unique. In other words in my travels between three cities may my path form a modified x (intersecting segments) or would i have to more likely make a U (no intersection segments)?

Assume a network of straight roads connects every pair of cities.

I did not draw all the roads to keep the map uncluttered, but gave the distances.

That may have been a source of confusion.

Visit every city once and only once, using those roads.

No trips to Disney World.

Paths can cross.

Link to comment
Share on other sites

  • 0

My first instinct is to have the salesman criss-cross as much as possible. The route I would take (just a guess, haven't verified) is 1, 5, 2, 6, 3, 8, 4, 7 for a total of 41.989 units traveled.

Good guess BG, but I found one a little longer.

This is the correct open route.

P.s. I think it's more challenging than finding the shortest route, which in this case is trivial.

If people like this genre I will post another.

Edited by bonanova
This solution is optimal.
Link to comment
Share on other sites

  • 0

on the graphic, 7 and 8 are inverted, also it seems the 6.083 distance whould have been 6.325

not returning: 1 5 2 6 3 8 4 7 for 42.63

returning: 1 5 2 7 3 8 4 6 1 for 47.10

Xavier is correct on both counts. I've modified the OP. Square root of 40 is 6.325.

Edit: both of these paths are just shy of optimal.

  • Upvote 1
  • Downvote 1
Link to comment
Share on other sites

  • 0

My first instinct is to have the salesman criss-cross as much as possible. The route I would take (just a guess, haven't verified) is 1, 5, 2, 6, 3, 8, 4, 7 for a total of 41.989 units traveled.

BG has the longest (non-returning) path.

I have marked the puzzle solved, but we still have the longest (closed-loop) path to determine.

(Post solutions in terms of the corrected 7-8 numbering and corrected 6.325 distance.)

Link to comment
Share on other sites

  • 0

Non-Returning: 1, 5, 2, 6, 3, 7, 4 ,8 for 42.957

Returning: 1, 4, 7, 5, 2, 8, 3, 6, 1 for 47.278

You have the longest non-returning path.

The returning path can be slightly longer.

I'm not sure which order of 7 and 8 you are using, but I see one path that is too short to use.

There are no (chess) Knight moves, like 7-5 and 2-8 (using the correct 7 8 labeling).

If you are using the original 8 7 labeling you are not using knight moves, but too many 1-4 type moves.

Clue for those still working on this the longest total length is 47.97, and from that you can get the distribution of city-city distances used, and work out the path.

Try my next, harder puzzle just posted. ;)

Link to comment
Share on other sites

  • 0

Non-Returning: 1, 5, 2, 6, 3, 7, 4 ,8 for 42.957

Returning: 1, 4, 7, 5, 2, 8, 3, 6, 1 for 47.278

You have the longest non-returning path.

The returning path can be slightly longer.

I'm not sure which order of 7 and 8 you are using, but I see one path that is too short to use.

There are no (chess) Knight moves, like 7-5 and 2-8 (using the correct 7 8 labeling).

If you are using the original 8 7 labeling you are not using knight moves, but too many 1-4 type moves.

Clue for those still working on this the longest total length is 47.97, and from that you can get the distribution of city-city distances used, and work out the path.

Try my next, harder puzzle just posted. ;)

Doh... mixed up 7 and 8 on the returning...

Link to comment
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...