Problem of the Week 1072

Sinister, Dexter, Sinister, Dexter

Consider a maze in the plane made from a network with a specified starting point S, which has a single edge leaving from it, and such that at each vertex (other than S) there are only two possible choices: turn left or turn right (a backwards move is not allowed).

True or False: If one makes alternating moves left, right, left, right, and so on, one always returns to S.

This diagram shows a case where one does return.

Source: Puzzle 17 at the Carnegie-Mellon University CS Puzzle Page.

© Copyright 2007 Stan Wagon. Reproduced with permission.