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

So if I'm reading Jer's Solution and Larry's additinoal explanation correctly, this slight modification to the puzzle diagram will show how to make some large number of 19 step traversals...

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

By connecting the adjacent odd nodes to each other with an additional path you now change the network from a 6 odd-node network to a 2 odd-node network, and as stated by others a 2 odd-node always has a solution.

Is there a formula for figuring out the total number of solutions based on the number of odd and even nodes and the number of paths between them?

Posted by Erik on 2004-06-04 11:08:38