EWD 1190

Problem 10406 from The American Mathematical Monthly, Volume 101, Number 8 / October 1994

10406. Proposed by David C. Fisher, University of Colorado, Denver, CO, Karen L. Collins, Wesleyan University, Middleton, CT, and Lucia B. Krompart, Rochester, MI.

Show that a path on an m by n square grid which starts at the northwest corner, goes through each point exactly once, and ends at the southeast corner divides the grid into two equal halves: (a) those regions opening north or east; and (b) those regions opening south or west.

(10406) A path meeting the conditions of the problem on a 5 by 8 grid is shown in figure 10406 below.

EDW1190 figure 1


We confine our attention to paths from NW to SE that do not necessarily go through each point; the off-path points are called free. Directing the paths from NW to SE, I identify (here without proof) the region(s) “a” with those to the left of the path, and the regions “b” with those to its right.

A path, along which turns to the left and turns to the right alternate, is a shortest path; we give a simple example (in the same 5 by 8 grid).

EDW1190 figure 2

For the m by n grid with a shortest path we observe
•   # points = m * n
•   # unit squares = (m−1) * (n−1)
•   # edges on shortest path = (m−1) + (n−1)
•   # points on shortest path = m + n − 1
•   # free points = (m*n) − (m+n−1) = (m−1) * (n−1)

in short: the number of unit squares equals the number of free points. But we can go further: this equality holds for the separate regions! We can establish in the a-region a 1-1 correspondence between each unit square and its NE corner, and in the b-region between each unit square and its SW corner.

Fa and Fb : # free points in a-region(s) and b-region(s) respectively
Sa and Sb : # unit squares in a-region(s) and b-region(s) respectively,
we can now formulate

Lemma 0   In the case of a shortest path Fa = Sa Fb = Sb.

The idea of the proof is to start with a given path that visits each point exactly once —i.e., Fa = 0 Fb = 0—, and to transform it in a finite number of moves into a shortest path for which Fa = Sa Fb = Sb holds. Initial and final state are then to be linked via an invariant that is maintained by each move.

For the move we consider that, as said, a path, along which turns to the left and turns to the right alternate, is a shortest path. Consequently, if the path is not of minimal length, it contains at least one pair of successive turns in the same direction. With those turns k edges apart it means that there exists a rectangle —a “bar”— of k (k ≥1) unit squares such that 3 of its sides are formed by 1, k, 1 edges of the path, e.g. for k = 5:

EDW1190 figure 3

We can —and will— always choose a rectangle such that the k−1 interior points of the 4th side are free. The move shortens the path by 2 edges in the obvious way; in the same example, the above configuration is transformed into

EDW1190 figure 4

With x,y = a,b or x,y = b,a, we observe for the transformation by the move:

Sx = −k
Fx = −(k−1)
(SxFx) = −1
                      Sy = +k
Fy = +k+1
(SyFy) = −1

The above transformation reduces at both sides of the path the difference SF by 1, and hence

(SaFa) − (SbFb) = q   ,

if initially true, is an invariant of our total transformation process (which obviously terminates since each move reduces the path by 2 edges).

From Lemma 0, which is applicable in the final state, we conclude q = 0. Therefore initially, with Fa = 0 Fb = 0, we have SaSb = 0 or Sa = Sb. Quod erat demonstrandum.

*         *         *

It took me several hours to design the move of the previous page; for quite a while I considered 2 unparameterized moves: the current one with k =1 and EDW1190 figure 5, which changes the shape of the path without shortening it. The mere fact that the second move complicates the termination argument should have made me reject it much faster.

I liked the problem.

Austin, 17 October 1994

prof.dr. Edsger W.Dijkstra
Department of Computer Sciences
The University of Texas at Austin
Austin, TX 78712-1188