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

I've also got a solution that traverses four edges twice. Starting at D:

D, G, J, K, H, E, A, B C, F, E, B, C, F, I, H, G, J, K, L, I.

The edges (G,J), (J,K), (B,C), and (C,F) are traversed twice. This makes a total of 21 kilometers.

While doing this I discovered it can also be done in 20 kilometers (traversing three edges twice).

Starting at G: G, J, K, H, E, D, G, H, I, F, E, B, A, D, E, B, C, F, I, L, K.

Posted by Eric on 2004-06-07 18:34:20