A and B are opposite corners of an n x n board, divided into n2 squares by lines parallel to the sides. In each square the diagonal parallel to AB is drawn, so that the board is divided into 2n2 small triangles. The board has (n + 1)2 nodes and large number of line segments, each of length 1 or √2. A piece moves from A to B along the line segments. It never moves along the same segment twice and its path includes exactly two sides of every small triangle on the board. For which n is this possible?
Answer
n=2 only
Solution
The diagram above shows that n=2 is possible (the path is AHEFGHCDIHB). Now suppose n > 2.
Note that if X is any vertex except A or B, then an even number of segments with endpoint X must be in the path.
Let F be the bottom left-hand vertex. Two sides of the triangle EFG are in the path, so at least one of EF and FG is. But EF and EG are the only segments with endpoint F, so an even number of them must be in the path, so both are in the path. Hence, again considering EFG, EG is not in the path. Hence, considering EHG, EH and HG are in the path.
E has an even number of segments on the path, so CE is not on the path. Hence (considering CEH) CH is on the path. Similarly, GJ is not on the path and HJ is on the path. An even number of segments at H are on the path, so DH and HI are either both on the path or neither is on the path. But (considering DHI) at least one must be, so they both are. Hence DI is not, and CD is not.
Since n > 2, C is not the top left vertex. Considering MCD, MC and MD are both on the path. Considering DLI, DL is on the path. There must be an even number of segments at D, so DP is on the path. Hence MP is not. Now M cannot be the top left vertex (with n = 3) because then it should have an odd number of segments, whereas it would have two (MC and MD). So there must be a vertex N above M. Considering NMP, MN must be in the path. But now M has an odd number of segments. Contradiction.
© John Scholes
jscholes@kalva.demon.co.uk
25 January 2004
Last corrected/updated 25 Jan 04