Problem of the Week 1059

Snakes on a Plane

MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW

Each of the eight rectangles in the diagram below represents a house, the door being marked by an attached semicircle. Each disk represents a gate on the boundary of the region. Each dot represents a tree:

Show how to draw eight non-crossing paths leading from each door of a house to the gate of the corresponding color, with the following restrictions.

1. The paths are broken lines consisting of only horizontal and vertical segments; i.e., a walker will make only right-angle turns. The walker can start from the door in any direction (north, east, west, or south) that doesn't take him back inside the house. So for example, one may leave the red door in a westerly, northerly, or southerly direction. The arrows are there only to point you to the gate.
2. Each path stays in the lanes between the trees (or between the trees and the border fence). However, the narrow lanes near the houses (which may not have visible trees on both sides because of the houses) may be used.
3. Each part of each lane contains only one path. To be precise, between any two trees that are one unit apart at most one path passes (and the same for the lanes between the trees and the border; a unit is the minimum distance between trees).

This is an old Sam Loyd puzzle, popularized by Ed Pegg in his regular puzzle column (highly recommended) for the MAA.

© Copyright 2006 Stan Wagon. Reproduced with permission.