Ulrich Berger’s solution to the rectangle problem

Ulrich Berger's solution to the rectangle problem

In response to EWD1015, Ulrich Berger from Munich showed me his charming proof of the Theorem. Let a big rectangle R be partitioned into a finite number of small rectangles r. Then

$$ (\underline {{A}} r: P. r) \Rightarrow P. R, w h e r e $$

${P}_{1}q \equiv \left( {\text{rectangle }q\text{ has a side of integer length}}\right) .$

Berger's Proof Let the vertical side of R be of non-integer length; we shall prove that the horizontal side of R is of integer length. To this end we place a red line along the top side of R; segment by segment the red line is moved downward until it coincides with the bottom side of R: a segment of the red line that is fully touched from below by a little rectangle r may be moved downward over the height of r ,i.e. until it is touched by r from above. In each move one of the little rectangles is "swept" by the red line, which after as many moves as there are little rectangles coincides with the bottom side.

We now define the quantity INT by

INT = the sum of the lengths of the red segments at an integer distance from the bottom of $\mathcal{R}$ .

Because the vertical side of $R$ is of non-integer

length and the red line initially coincides with the top side of $\mathbb{R}$ ,we have initially $\operatorname{INT} = 0$ ; because the red line finally coincides with the bottom side of $\mathbb{R}$ ,we have finally $\operatorname{INT} =$ (the length of the horizontal side of $\mathbb{R}$ ). We shall prove the theorem by showing that each move changes INT by an integer amount.

Consider the move in which little rectangle $r$ is swept by the red line. We distinguish two cases.

(i) The vertical side of $r$ is of integer length. Since neither or both horizontal sides of $r$ have an integer distance from the bottom of $R$ , this move changes INT by 0 .

(ii) The vertical side of $r$ is of non-integer length. Since at most one of the horizontal sides of $r$ has an integer distance from the bottom of $R$ , this move changes INT by 0 or by the length of the horizontal side of $r$ , which is integer.

(End of Berger's Proof.)

I had hoped to render this argument on a single page, and apologize for my misjudgement.

Nuenen, 12 August 1988

prof. dr. Edsger W. Dyrkstra

Department of Computer Sciences, The University of Texas at Austin

Austin, TX 78712 - 1188, USA