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

 The Tour (Posted on 2004-06-04)
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 | Comment 2 of 11 |

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

 Search: Search body:
Forums (0)