Rectangles within rectangles.

Rectangles within rectangles

Anyone who has gone through the chore of tiling a floor or installing a suspended ceiling can appreciate how much easier the job is if the tiles or panels evenly fit the area to be covered. For example, panels that are 4 feet long and 2 feet wide nicely cover a ceiling that happens to be, say, 6 feet by 8 feet. No panels need to be cut, and all the space is filled. Mathematically, this tiling problem can be generalized to the statement that if an a b rectangle is tiled with copies of a c d rectangle, then each of c and d divides evenly into one of a and b. The theorem, in a form that applies in higher dimensions as well, was proved about 20 years ago by Dutch mathematician N.G. de Bruijn of the Eindhoven (Netherlands) University of Technology.

Mathematicians subsequently suggested and proved a more general theorem: "Whenever a rectangle is tiled by rectangles, each of which has at least one integer side, then the tiled rectangle has at least one integer side. The original proof for this theorem, as in the case of de Bruijn's theorem, required the use of complicated mathematics involving double integrals and complex numbers. It was like using "a cannon to kill a mouse,' says Solomon W. Golomb of the University of Southern California in Los Angeles.

At a meeting in 1985, mathematician Hugh L. Montgomery of the University of Michigan in Ann Arbor discussed the problem and stimulated a search for a more elementary proof of the theorem. The results of that search, as compiled by Stan Wagon of Smith College in Northampton, Mass., appear in the August-September issue of THE AMERICAN MATHEMATICAL MONTHLY. Wagon describes 13 alternative proofs proposed by various mathematicians. "The variety of techniques that have been brought to bear is striking,' says Wagon.

Richard H. Rochberg of Washington University in St. Louis and Sherman K. Stein of the University of California at Davis independently came up with one of the simplest proofs. Each rectangular tile is colored to produce a checkerboard pattern in which each square is half a unit wide. Because each tile has an integer side, it carries an equal amount of black and white. If such tiles completely cover a large rectangle, then it, too, must have equal amounts of black and white. Therefore, at least one of the sides of the large rectangle has an integer length. Otherwise, the whole rectangle can be split into four pieces, three of which have equal amounts of black and white while the fourth does not.

Other proofs involve double integrals with real instead of complex numbers, various ways of counting squares, and the use of prime numbers, polynomials, step functions or graph theory. Although several of the proofs are mathematically related and most have similar ingredients, important differences show up when the methods are tried on extensions of the original theorem. What if the tiles are like flexible postage stamps pasted on the surface of a cylinder or a doughnut-shaped form called a torus? What happens in higher dimensions, that is, when n-dimensional bricks are stacked in n-dimensional boxes? Some methods of proof are more powerful than others because they yield more general results, says Wagon. However, which proof is the best isn't easy to decide. That depends on the criteria used to define "best.' Perhaps the best possible proof hasn't even been found yet.