All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
The Tour (Posted on 2004-06-04) Difficulty: 2 of 5
You want to conduct a tour of this museum:

A-B-C
| | |
D-E-F
| | |
G-H-I
| | |
J-K-L

You want to walk through all the hallways once. What would be the least amount of walking you would need to do (each hallway is a kilometer long) to cover all the hallways at least once? (You can start and stop anywhere.)

See The Solution Submitted by Gamer    
Rating: 3.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution | Comment 2 of 10 |

A network is traversable if it has two or fewer even nodes.

This network has six so some hallways will have to be walked more than once.  Odd nodes may be turned into even nodes by connecting them in pairs.  The two pairs most easily (and shortly) connectable are GD and FI. 

Doing this adds two kilometers of walking to the 17 kilometers of existing hallway for a total tour length of 19 kilometers.  B and K remain as the odd nodes so the tour begins at one and ends at the other.

A possible tour (though the problem doesn't ask for one) is BCFILKJGDABEDGHEFIHK

-Jer


  Posted by Jer on 2004-06-04 09:23:09
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information