In Gridland, the cities are arranged in a 4 by 6 grid:

A-B-C-D-E-F
| | | | | |
G-H-I-J-K-L
| | | | | |
M-N-O-P-Q-R
| | | | | |
S-T-U-V-W-X

A man born in A (and never ventured outside his city) has to visit a man in X but wants to take a detour to get there. He wants to visit every city but not enter any city more than once during his tour. How should his trip go?

Such a path is impossible given the conditions that it must start at A and end at X.

If we consider the cities on the grid as squares on a checkerboard and color them appropriately (say A, C, E, H, J, L, M, O, Q, T, V, X red, B, D, F, G, I, K, N, P, R, S, U, W black), we realize that as we travel we must alternate between red and black squares. excluding A and X, we are left with 12 black squares and only 10 red squares. We can't alternate between red and black and hit each of them exactly once. Note that if we were to stop on a black square it would be doable, but since A and X are both red, the man in A is out of luck.

Posted by Timothy on 2004-05-21 23:26:39