On a problem transmitted by Doug McIlroy

On a problem transmitted by Doug McIlroy

During the recent meeting of IFIP Working Group 2.3 on "Programming Methodology", Doug McIlroy (AT&T) told me the following

Theorem Let a big rectangle $R$ be tiled into small rectangles $r$ . Then

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

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

My quick consideration that this might be a theorem was as follows. Let each side of each small rectangle be a multiple of $1/p$ . Then

(0) having an integer side, each small rectangle $r$ has an area that is a multiple of $p$ (1) hence $R$ has an area - the sum of areas of small rectangles - that is a multiple of $p$ (2) each side of $R$ - being sums of sides of small rectangles - is a multiple of $1/p$ . (3) combining (1) and (2) we conclude for $p$ a prime that $R$ has a side of integer length.

So far so good. But even the consideration that with sufficiently large prime $p$ each real value can be approximated arbitrarily closely by a multiple of $\frac{1}{p}$ does not make this a proof. Before I had designed a proof, Doug told me the argument that I shall now develop.

The argument takes for granted that each small rectangle has sides parallel to those of the big one.

How do we formally express that the little rectangles r partition the big one R ? Just stating that the sum of the areas of the little ones equals the area of the big one does not suffice for then the jigsaw puzzle need not fit. The claim that the little rectangles have been so positioned in the plane as to form a tiling of R is equivalent to the statement

(0) $\underset{R}{\left( \sum M\right) } = \iint {f}_{1}x.y\mathrm{\;d}x\mathrm{\;d}y = \left( {\iint R}\right) f$ .

Remark This characterization of the r's forming a tiling of R may surprise the reader at first sight but it is the only compact way in which I can characterize that fact. That the tiling implies (o) is a direct consequence of the definition of the integral -we know it more generally as "splitting the range"-, but (o) is also a sufficient condition. With $f = 0$ inside $\mathbb{R}$ and $f = 1$ outside $\mathbb{R}$ it expresses that no r lies outside $\mathbb{R}$ . With $f = 1$ inside $\mathbb{R}$ but outside all r's and $f = 0$ elsewhere, it expresses that $\mathbb{R}$ is covered by the r's, etc. (End of Remark.)

But if (0) is the characterization of a tiling there is only one thing we can do:

Firstly, we must think of a constraint such that

a sum meets the constraint if all summands do, and

Secondly, we must find such an $f$ that for any rectangle $g$ with sides horizontal or vertical

(1) ( $g$ has a side of integer length) $\equiv$

( $\iint$ f.x.y dx dy) meets the constraint)

Let us focus on the constraint first. Being positive works only for non-empty sums, but being $\geq 0$ would do. Being congruent 0 mod $p$ would do; but meeting the constraint should say something about one of the sides. By choosing $p$ prime, our quick consideration led to some sort of conclusion, but we saw that that argument was a dead end: the $p$ was too arbitrary. Why don't we try the simplest constraint we can think of, viz. being equal to zero?

This choice pins down requirement (1) on $f$ : for any rectangle $g$ with sides horizontal or vertical, $f$ should satisfy

(2) $\left( q\right.$ has a side of integer length $) \equiv$ $\left( {\iint {f}_{1}x.y\mathrm{\;d}x\mathrm{\;d}y}\right) = 0$

or, a little bit more explicitly

(2') (q's horizontal side is of integer length) $v$ (q's vertical side is of integer length) $\equiv$

$$ (\iint_ {9} f \cdot x \cdot y d x d y) = 0. $$

The latter formulation suggests to rewrite the right-hand side as a disjunction of two terms, dependent on the horizontal and the vertical dimension of $g$ only. Because a product is zero iff a factor of it is zero, we would like to write the double integral as the product of two single integrals. This we can achieve by choosing for fix.y the product of two factors, dependent on $x$ and $y$ respectively. In order to maintain the symmetry we choose for $f$ with some $h$

$$ f \cdot x \cdot y = h \cdot x \cdot h \cdot y $$

Then $\left( {\iint {f}{x.y}{dx}{dy}}\right) = \left( {\int {h}{x}{dx}}\right) \cdot \left( {\int {h}_{y}{dy}}\right)$

and (2) is now satisfied provided $h$ satisfies

(b - a is integer) $\equiv \left( {\mathop{\sum }\limits_{a}^{b}h.x{dx}}\right) = 0$

Can we find such an $h?$ with $h = H'$ ? We can rewrite (3) as the conjunction of

(4a) (b-a is integer) $\Rightarrow H.b = H.a$ and (4b) (b-a is integer) $\Leftarrow H.b = H.a$

Relation (4a) is satisfied by any $H$ with period 1 . Because we wish to define $h$ by $h = {H}^{\prime },h$ should also be differentiable. So far

satisfy (4b), which requires all values in a period to be distinct. A moment's reflexion tells us that no real, differentiable, and periodic function meets that requirement, but that in the complex plane there is no problem: for instance

$$ H. x = e ^ {2 \pi i x} $$

meets all our requirements. (Any differentiable function with period 1 whose period traces a nonintersecting cyclic path in the complex plane will do.)

The above proof design has been recorded for a number of reasons. Doug McIlroy showed me this proof as a surprising example of how effective complex numbers can be in solving a problem in real numbers. He pulled $e^{2\pi i(x + y)}$ out of a hat. The above design makes it quite clear why a detour via the complex plane is so appropriate.

Another reason to record this design is that each next step of the design is sweetly rea- sonable after the decision to characterize the tiling by (o). I am convinced that the elegance of the final argument and the compelling nature of its design are an immediate consequence of the choice of (o): it is noncombinatorial and

lends itself to manipulation. I am also convinced that this is an instance of a very general observation.

Austin, 21 November 1987

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

PS. This was a semester of very few EWDs. The explanation is very simple: five months ago I started on the manuscript of a book, and that text was given the highest priority. Until a month ago, I progressed so nicely that at one moment I hoped to have the text essentially completed by the end of the year. But I won't make that. Somewhere in the course of next semester I hope to resume the writings of EWD's at its normal rate. (I apologize to all those that started worrying about my health for not having announced that I would be otherwise engaged.)