12th Swedish 1972 Problem 2 A rectangular grid of streets has m north-south streets and n east-west streets. For which m, n > 1 is it possible to start at an intersection and drive through each of the other intersections just once before returning to the start?
mn even Solution Suppose a path is possible. Let N,S,E,W be the number of moves north, south, east, west. Then the total number of moves N + S + E + W = mn. Since the path is closed we have E = W and N = S. Hence N + S + E + W is even and hence mn is even. wlog suppose n is even. The diagram shows one way of making the drive using a comb shape. 12th Swedish 1972 © John Scholes jscholes@kalva.demon.co.uk 13 February 2004 Last corrected/updated 13 Feb 04