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.

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).

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.

Introducing
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:

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

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

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

(Sa−Fa) − (Sb−Fb) = 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 Sa−Sb = 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 , 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
USA

transcribed by Corrado Cantelmi
revised 24-Dec-2011