Patrolling the Palace

A puzzle by James Tanton:

King Tricho lives in a palace in which every room is a triangle:

patrolling the palace

Before retiring for the night he’d like to inspect it. Is there a path that will let him visit each room once and only once? He can start anywhere.

	Select Click for Answer
No, there isn’t. Color the cells as shown: Any path that the king takes must alternate between dark and light rooms, so the king can succeed only if there are an equal number of each (or if their numbers differ by 1). In the diagram there are 12 dark rooms and 10 light rooms, so there’s no way to visit all of them on one connected tour, unless the path travels outside the palace. (From Tanton’s “A Dozen Questions About a Triangle,” Math Horizons 9:4 [April 2002], 23-28.)