Squaring the Square
N 1936, FOUR STUDENTS AT TRINITY COLLEGE, Cambridge-Brooks, Smith, Stone, and Tutte--considered the problem of cutting up a rectangle into squares of unequal size (no two alike). It was known, at that time, that a rectangle 32 by 33 could be "squared" as shown in Figure 7.1.
Stone became particularly interested in trying to prove that it was impossible to cut a given square into unequal squares. While not able to do this, he did discover a squaring of another rectangle (see Figure 7.2).
One way of attacking the problem of finding rectangles that can be squared is to make a sketch of a proposed partition into squares, labelling the edge-length of each square, writing down all the relations that the edge-lengths must satisfy in order to fit into the rectangle, and solving the system of equations thus obtained.
We shall carry this out for some examples. Instead of carrying as many unknowns as there are squares in the subdivision, we shall try to label neighbouring squares so that they fit together in the sketch; thus we shall have fewer unknowns to eliminate later.
In Figure 7.3, we label the neighbouring squares x, y and z, as shown. Then it is easy to label the remaining squares in the order
x + y, 2x + y, y - z, y - 2z, y - 3z, 2y - 5z.
Next, we obtain relations between our unknowns; for example, we can equate the lengths of opposite sides of the containing rectangle The horizontal sides yield
2x + y + x + y = 2y - 5z + y - 2z + y - z,
that is, (1)
3z - 2y + 8z = 0;
and the vertical sides yield
2y - 5z + 2x + y = y - z + y + x + y,
x - 4z = 0.
x = 4z and Y = 10Z.
We observe that if we set z = 1, we obtain the tiling shown in Figure 7.1; if we set z equal to any other positive quantity, we obtain the same configuration, blown up (or shrunk) by the factor z. If we prescribe the length of the horizontal edge, say 64", then z would be 2" and the figure would be completely determined.
In Figure 7.4, two unknowns, x and y, suffice to express the edgelengths of all compartments.
Equating the lengths of the horizontal sides of the containing rectangle, we obtain
9x - 5y + 6x - 2y = 2x + 5y + x + 2y + x + y + 2x + y,
that is, 9x - 16y = 0, whence (3) X 16 -- = -- Y 9
The values x = 16, y = 9 yield Stone's tiling of the 177 X 176 rectangle (see Figure 7.2), and other values satisfying (3) would give a similar figure.
To show that such schemes do not always yield feasible results, we give another example.
Starting with x and y as shown in Figure 7.5, we can label the other squares
X + Y, 2x + y, 3x + y;
and equating lengths of the vertical borders, we get
2x + y + 3x + y=x + y + y
our middle square turns out to be a point and the remaining four squares axe equal. We have merely quartered the given rectangle, which must have been a square!
Our examples indicate that the system of linear equations we get from an arbitrary sketch of a partition seems to have a unique solution (except for a scaling factor), although the solution is not necessarily geometrically feasible. It could happen, for example, that some of the edge-lengths turn out to be negative, and that would not make sense in the context of our tiling problem.From our previous experience with systems of linear equations we know that there may be too many equations (in which case there is no solution) or there may be too few (in which case there are infinitely many solutions) or the number of equations may bejust right, that is, they are satisfied by exactly one set of numbers. In all our examples, the number of equations obtained by prescribing the length of one pair of edges of the containing rectangle, but not the length of the other, was just right; i.e., each system had a unique solution. Was this just a happy accident? We shall show, by appealing to electrical network theory, that a system of linear equations obtained from a sketched partition always has a unique solution.
To make things more precise, consider a given subdivision of a rectangle into squares. With respect to each horizontal segment of the partition (see Figure 7.6) we have a relation
a + b = c + d + e
telling us that the sum of the lengths of the edges of squares bordering the segment on one side is equal to the sum of the lengths of the edges of squares bordering the segment on the other side. We shall call all such relations horizontal compatibility relations. Similarly, the analogous relations obtained from vertical segments will be called vertical compatibility relations. Clearly, the set of all compatibility relations forms a system S of linear equations.
THEOREM. If one of the two dimensions of a partitioned rectangle is prescribed, the system S of compatibility relations always has a unique Solution (though not necessarily geometrically meaningful).
Imagine that the rectangle is a plate of uniform thickness made of some conducting metal. Suppose all points of the upper edge of the rectangle were given the same electric potential V, and all points on the lower edge had a lower constant potential V'. (This could be accomplished by coating these edges with some perfect conductor.) Because of the prescribed potential difference V - V', there will be a steady flow of current through the rectangle, in the vertical direction. The rate at which electrons cross over a horizontal interval is proportional to the length of that interval. Thus, if I is the current crossing over a horizontal interval of unit length, then the current flowing across an interval of length I is 11. The resistance of such a rectangle to electric current is directly proportional to its vertical height L (to the distance the current must traverse) and inversely proportional to its horizontal width W (the distance along which the current may enter); i.e., resistance = (RL/W). Thus, if the rectangle happens to be a square (L = W ), then its resistance is R and does not depend on the size of the square.
Now suppose that such a current-carrying rectangle has been partitioned into squares. Since the flow is vertical (there is no flow in the horizontal direction), we may cut through vertical segments without interfering with the current. Now regard the cut-up plate as a network where the constituent squares are identified with conducting wires and where horizontal segments axe identified with points, or vertices at which the conducting wires meet. (See Figure 7.7, where the vertices A, B, - - . in the network correspond to horizontal segments at levels a, b, . . . of the rectangle, wires AB, AC, correspond to squares extending from levels a to b, a to c,
The magnitude of the current flowing through each wire is proportional to the length of the side of the square represented by that wire.
The law of conservation of current states that, at each vertex of the graph, the total amount of current flowing in equals the total amount of current flowing out. For example, the vertex C (corresponding to the horizontal segment at level c) receives current tI + wl through wires AC and BC (corresponding to squares t and w) and C loses current xI + zI through wires CD and CE (corresponding to squares x and z). The law cited above yields the relation
t + w = X + z
which is just one of our horizontal compatibility relations.
Since current flows in at the upper edge of the plate, moves down vertically and flows out at the lower edge, we see that every point at the same horizontal level is at the same potential, and points at higher horizontal levels have higher potentials than points at lower horizontal levels. According to Ohm's law, the difference in potential between two Points of the network joined by a wire is equal to the product of the current through that wire and the resistance offered by it. For example, the Potential difference between B said C (representing levels b and c of the plate) is wI x R (wI being the current entering at the upper edge of the square w, and R the resistance of any square; see p. 52). Moreover, the potential difference is additive; that is, if A and D are two vertices in the network connected by a path AB, BD through B, then the difference in potentials between A and D is the sum of the differences in potentials between A, B and B, D: sI.R + vI.R in our illustration. As a consequence, for any closed path in the
network, say ABDCA, the corresponding sum is zero+, and for any two paths from the same beginning point to the same end point, the corresponding sums are the same. Thus for ABD and ACD, we have
sI.R + vI-R = tI.R + xl.R
which reduces to
s + V = I + X.
This is one of our vertical compatibility relations.
The law of conservation of current and Ohm's law yield a system of linear equations equivalent to the system S of compatibility relations. Now it seems plausible that if a difference in potential is prescribed for a network such as ours (say the potentials at vertices A and E are given, or equivalently, at the top and bottom edges of the plate) then the current flowing in each wire is determined. This, in fact, is the content of the celebrated theorem by Kirchhoff:
If a potential difference between any two points of a network is prescribed, then the laws of conservation and Ohm determine -uniquely the flow in each wire.
Since these physical laws axe equivalent with the geometrical compatibility relations (the prescribed potential difference corresponding to the vertical dimension of the rectangle), the assertion that the system S has a unique solution (see p. 52) is seen to be just a corollary of Kirchhoff's theorem.
A rigorous proof of Kirchhoff's theorem is beyond the scope of this essay.$
Let us now re-examine the problem of partitioning a rectangle into squares.
First we note that a solution of the linear system S may include
non-positive quantities. These cannot be made to correspond to lengths of sides
of subdivision squares, so such solutions of the system S are not solutions
of the tiling problem.
We might try to attack the rectangle-tiling problem by first devising a systematic method of enumerating all possible partitions into n squares and letting the integer n increase. We might then solve the system S for each partition and discard all partitions with geometrically non-feasible solutions. Even among the feasible solutions, many would be uninteresting (i.e., partitions into equal squares, etc.). Requirements such as (a) no two squares in the partition may be congruent, or (b) the partitioned rectangle may not contain a smaller rectangle, impose further conditions on the solutions of S. Perhaps we can approach the problem simultaneously from the other direction; that is, weed out all networks about which we know a priori that the solutions of the associated system S are either geometrically not feasible or produce unwanted partitions of types (a) or (b) above.t
A squaring or tiling in which no two squares are the same size is said to be "perfect". Tutte and his friends were chiefly after perfect tilings. They wanted to find a "perfect square", that is, a square with a perfect tiling. All their results involved non-square rectangles. And so they began to think that a perfect square did not exist. However, in 1939 Roland Sprague of Berlin found one, and, since then, many others have been discovered.
Attention was then turned to finding the perfect square with the smallest number of squares in it (i.e., of lowest order). The record to date is one of order 24, found by an amateur mathematician, T. H. Willcocks of Bristol, England. (See Figure 7.8.)
Figure 7.8 (Compound) perfect square of order 24.
A tiling tiling is said to be "simple" if the arrangement of the squares does not form any smaller squared rectangle inside the original. Willcocks' perfect square is compound, not simple. Accordingly, attention was focussed on the simple perfect square of lowest order. Until recently, Willcocks also held this record with a square of order 37. However, in. 1964 Dr. John Wilson of the University of Waterloo (a student of Tutte), using an electronic computer, found one of order 25 (see Figure 7.9), and he is the record-holder at present.
It has been shown, using computers, that there is no perfect square of order less than 20, simple or otherwise. Consequently, there is not much room for improvement in the above records.
So many perfect squares have been found that experts in the field suspect that tiled rectangles of unequal sides are the harder to come by.
We close this essay with the following easy-to-prove theorem: It is impossible to fill a rectangular box with a finite number of unequal cubes.
Figure 7.9. Simple perfect square of order 25
Proof: Any successful packing of the box provides a perfect tiling of the bottom of the box by those cubes which rest on the bottom. Now the smallest cube S among those lining the bottom certainly could not touch an upright side of the box; for then there would have to be an even smaller one touching the bottom. (See Figure 7.10.)
Figure 7.10. View of bottom rectangle of the box.
This smallest cube on the bottom, being out in the middle part of the bottom, must be bordered on every side by a bigger cube (it is the smallest). Its upper surface, then, is completely walled in; see Figure 7.11. In order to cover this upper surface, even smaller cubes must be used.
Among the cubes on the upper surface of S, the smallest, again occurring in the middle part, is surrounded by bigger ones. Consequently, even smaller ones still must occur in a third layer on the top of this walled-in cube. This argument continues without end, implying that there is no end to the number of cubes that must be employed.
Prove that there exists some rectangle which can be tiled into N unequal squares for each value of N greater than 8, i.e., for N = 9, 10, 11, . . .
In tiling an equilateral triangle with unequal equilateral triangles, prove:
(b) the smallest
tile, T, touching the top of S meets the top of S in just
(c) Does this lead to an endless tower of little triangles, providing a proof of the theorem "it is impossible to tile an equilateral triangle with unequal equilateral triangles (no two alike)", which was first proved by Tutte around 1948?
+ Some headway in this direction has been made, for example, by applying Euler's formula to the graphs of our networks.
+ A path in our network leads from a vertex along an edge in the direction of a next vertex, etc. We take these directions into account by using signed quantities in this sum. For example, A C corresponds to tI, and CA corresponds to - 11.
$The interested reader may look it up, for example, in R, E. Scott, Elements of Linear Circuits, Addison-Wesley, 1965, Reading, Mass.
J. Bouwkamp, On the Dissection of Rectangles into Squares, Kon. Ned.
Ak. van Wet.,
1946, Vol. 49, pp. 1176-1188; 1947, Vol. 50, pp. 1296-1299.