|The Games and Puzzles Journal Issue 33, May-June 2004|
This issue is devoted to a study by Chris Tylor on the classic problem of cutting up a rectangle into as few pieces as possible to form a square. This is the first part of a longer study on Pythagorean dissections of two squares to form one.
One of the most elementary problems in the field of planar dissections is the transformation of a rectangle into a square of the same area; another is the transformation of two squares into one in illustration of Pythagoras' theorem. General solutions to both these problems are well documented, but it turns out that there are a wide variety of other solutions that have apparently never been described systematically. This account is an attempt at a full analysis of the rectangle-square problem; I hope to cover the Pythagorean problem by instalments in later issues of Games and Puzzles Journal.
In this account, I refer frequently to H. Lindgren's seminal work Geometric Dissections (Revised Edition, Dover, 1972). However, I have found it convenient to deviate from Lindgren's terminology by using capital letters to list classes of solution to the problem rather than general types of dissection. I also use my own set of technical terms (printed in bold type when they first occur) in preference to his.
Some general points. This problem consists of transforming a rectangle of dimensions p² by q² (p > q) into a square of side pq. I call particular values of p and q a case, which can be defined by its case ratio p/q. Minimal solutions to the problem require in general three pieces provided that the case ratio is not too high. A solution is simply a set of pieces into which rectangle and square may be cut in order to allow the transformation of one shape into the other. There may be alternative arrangements of the pieces, but differences are often trivial. Closely related solutions to the same case may be called variations (though the distinction between solutions and variations may sometimes be blurred). An individual solution or variation may be identified by a code symbol.
Classes of solution can be put into three main groups. Firstly, there are those in which the case ratio is continuously variable, giving a continuum of general solutions (i.e. those in which there is no restriction on the angle of the cuts). The code symbol of one of these solutions will consist of the class letter followed by the case ratio in square brackets.
Secondly, there are families of solutions defined by one or more discrete variables. (If there is only one variable, the family will be equivalent to a simple series.) The code symbol of one of these solutions will consist of the family's letter and subscript, followed by the value(s) of the variable(s) in normal brackets. In these solutions, all the cuts are horizontal or vertical. Lindgren calls them rational solutions, but I prefer the term orthogonal as being more descriptive. Their cases are rational, and are best defined by integral values of p and q rather than by a ratio. A case can be called simple if p and q are relatively prime, composite if they have a common factor. Each family will have a case formula consisting of a pair of expressions giving p and q in terms of the other variable(s).
Thirdly, there are irregular solutions that do not belong to either a continuum or a family. The code symbol of one of these will be the simple case numbers in square brackets followed by an arbitrary subscript.
|(72) 1. Continua of general solutions.||é|
There are two of these, operating on quite different principles.
A. Tessellated solutions. These can be derived from superimposed tessellations of squares and of rectangles, so that a single diagram can illustrate the complete dissection. (Lindgren calls them S-dissections without referring to tessellations.) In the transformation process, any one of the three pieces can be considered to remain unmoved while the other two are displaced from one side of it to the other.
Figures 1a-c show the case ratio increasing from 1 to the three-piece limit of Ö2, with the rows of squares and rectangles that make up the two tessellations becoming increasingly displaced relative to one another. The first two also illustrate one unsymmetrical tessellation of squares giving rise to two different tessellations of rectangles. The special case of a symmetrically displaced tessellation of squares (not illustrated) gives a case ratio of (Ö5)/2; in the limiting case it is the tessellation of rectangles that is symmetrically displaced.
Figures 1d,e show the same tessellations of squares being used to produce four-piece solutions for more elongated rectangles up to a new case ratio limit of Ö5. This process can be extended to give (n + 2)-piece solutions with a general case ratio limit of Ö(n² + 1).
Figures 1 Tessellated solutions.
Key to Figures 1.
B. Slide solutions. These contain a single oblique line that can be imagined to be a slide, with one triangular piece below the line forming the base of the slide, and the other two pieces above the line sitting on the slide, and changing places in the transformation. (Lindgren called this a P-slide to distinguish it from a more complex four-piece Q-slide.) These solutions are simpler to visualise than those of the previous type, but do require two separate diagrams for a clear illustration; they also have more ramifications.
Figures 2a,d show how increasing the case ratio changes the relative sizes of the two upper pieces. Figure 2b shows that at the limiting ratio of 2 (not Ö2 as with tessellated solutions) the slide effectively disappears to give a two-piece solution. For case ratios between 2 and 3, four-piece solutions can be obtained by combining the slide with an additional rectangle as in figure 2c. (The pieces may be differently arranged, but the differences are trivial.)
In general, the limiting case ratio for (n + 2)-piece solutions is n + 1, with one piece being lost when the limit is reached. This general limit is always greater than that for tessellated solutions, but with an overlap. As a result, the (n + 2)-piece tessellated solutions described above are only minimal for case ratios between n and Ö(n² + 1); thus that of figure 1d is non-minimal.
Figures 2A Slide and Step solutions.
Key to Figures 2A.
Having a rational case ratio does not affect tessellated solutions, but opens up new possibilities for slide solutions by allowing the line of the slide to become a flight of steps of infinitely variable shape. I call these solutions line variable. It is possible that the infinite number of line variations may be greater than that of the number of points on a line or in a plane figure (as in the point variations to be described later), but I am unable to be certain about this.
The limits of the steps are defined by the edges of a set of p × q unit rectangles. The steps must all be identical, and the line of a step cannot return to the top or bottom of its unit rectangle having once left it (since doing so would create an extra piece). Solutions with either line or point variations may be coded by adding the letter v (possibly with an arbitrary subscript) to the code. Figures 2e,f illustrate line variations for the case of figure 2d, where p/q = 5/3; 2e shows the limiting unit rectangles, and 2f shows a variation in which the pieces interlock to give a jig-saw effect.
Equalised diagrams. In both slide and step solutions, the orientations of all pieces and both shapes are maintained; the solutions can thus be called fully aligned. (The pieces of a tessellated solution may also retain their orientation, but the resulting rectangle and square are then out of alignment with one another; these solutions I call semi-aligned.) All fully aligned rectangle-square solutions may be diagrammed in a simplified way (due to Lindgren) in which the rectangle and square are represented by a pair of p × q and q × p rectangles to produce what I call an equalised diagram.
Thus figure 2h is the equalised diagram for figure 2d (enlarged in figure 2g). Note that in it the two rectangles with their cuts are congruent, which means that only one rectangle-square pair can be obtained by compressing or expanding them. If an equalised diagram shows non-congruent rectangles, it will represent two distinct solutions, which I call l-p variations (l-p being short for landscape-portrait).
Equalised diagrams are especially useful for investigating and displaying orthogonal solutions. These diagrams take up less space than normal diagrams when sketched on graph paper, since they use single squares to represent unit rectangles. They can also be used for solutions where pieces are rotated through 180° or are turned over vertically or horizontally, but fail when 90&g#deg; rotations are involved.
Figures 2B Example of equalised diagrams.
Key to Figures 2B.
|(73) 2. Families of orthogonal solutions.||é|
I have found thirteen of these families, which I group into six classes. All contain at least one flight of steps. Solutions with low numbers of steps are often trivial or degenerate; lower limits for the variable values will be given where this happens. The large majority of solutions are fully aligned and are represented by equalised diagrams, with step sizes (horizontal × vertical) measured in unit rectangles; exceptions are noted when they occur. Apart from a brief mention under the first of the classes, cases requiring solutions in four or more pieces are not considered.
C. Single-step solutions. These are the most straightforward orthogonal solutions, covering all possible cases. They consist of two closely related families, C1 and C2, which for simple cases represent the lower and upper limits of line variation in slide solutions. Each family can be defined by 2 variables, n and m (listed in reverse alphabetical order to tie in with later use of these letters). Of these, n indicates the total number of steps (though C2 solutions actually have only n-1 steps!) and m the movement of the larger of the two upper pieces. Both families have the same case formula, p = n + m and q = n; a common factor for n and m will of course give a composite case. Step sizes are 1 × 1.
Figures 3 show all the solutions for n = 4 and m < 5. The most important point to note is that C1 solutions with m = 1 are centro-symmetric and use only two pieces. They form a series within the C1 family to which I will give the symbol C0. This well-known series is described in Section 61 of GPJ Issue 30. I will use the term super-minimal for these two-piece solutions and their cases. All three-piece solutions for super-minimal cases will be called sub-minimal rather than non-minimal, and will be regarded as valid solutions to be described in this account (although trivial modifications of the super-minimal solution will be ignored).
Figures 3 illustrate several other features of this class. None of the solutions have l-p variations. All those with m = n degenerate into the C0 solution for the 2,1 case, since there is no movement on the step itself. C1 solutions with m > n + 1 and C2 solutions with m > n require four or more pieces (unless m = 2n). C1 solutions with m = n + 1 form a three-piece super-minimal series, since the case is outside the normal limit for three-piece solutions. These solutions contain a large rectangle; I call them strip-step for no very good reason. C2 solutions with m = n 1 are also strip-step, but are not super-minimal. Finally, C1 solutions with m = 2 and C2 solutions with m = 1 contain a single unit rectangle.
Figures 3 Single-step solutions (equalised diagrams).
Key to Figures 3.
D. Matched double-step solutions. These contain two flights of steps of equal height, running in opposite directions, with the transformation involving pieces moving by one step rather than changing places. This means that only one variable is required, n giving the number of steps. There are two quite different families (or series); each has the case formula p = n + 1 and q = n, so giving sub-minimal solutions for all super-minimal cases. Unlike those of the previous class, all solutions have l-p variations.
The D1 series is essentially a modification of the C0 series; it requires n > 1, with n representing the number of steps in either flight. The solutions have the special feature of being point variable; i.e. they can be varied continuously by adjusting the position of a point on a line. In fig 4a,b (showing the n = 3 case and drawn on a ×2 scale) the point x may lie anywhere on the bottom line. The point variations always include one with orthogonal symmetry. Steps are 1 unit high but of variable width.
The D2 series requires n > 2, with n representing the total number of steps in both flights. There are no point variations, the step size being always 1 × 2. Further, the solutions are not fully aligned but are two-sided, one or more of the pieces needing to be turned over horizontally. Figures 4c,d, which show the n = 5 and n = 6 solutions to illustrate the difference in appearance between odd and even values of n, are drawn with the central piece turned over. Alternatively, the two side pieces could be turned over, but since their combined area equals that of the central piece, this gives no advantage. However, figure 4e shows that with the alternative arrangement for n = 3, only one side piece need be turned over.
E. Nested double-step solutions. These have two different and independently variable types of steps, which can be called primary and secondary. The two types do not form separate flights; instead, each of the m primary steps (m > 1) contains within it n secondary steps, leading to intricate patterns. The solutions resemble single-step ones in having two upper pieces that change places, but differ in always having l-p variations.
There are two related families, differing according to which of the upper pieces a certain horizontal row of unit rectangles belongs to. Each has q = p 1, and so contains sub-minimal solutions only, but the case formulae for p are different and do not cover all possible super-minimal cases. The E1 family has p = m(n + 1), with a secondary step size of 1 × m; its solutions contain a centro-symmetric pattern. The E2 family has p = (m + 1)(n + 1) 1, with a secondary step size of 1 × (m + 1); its solutions have an unbalanced appearance. Figure 4f-i shows (2,3) and (3,1) solutions for both families.
Figures 4 Matched and Nested double-step solutions (equalised diagrams).
Key to Figures 4:
F. Parallel double-step solutions. This is a class known to Lindgren, who was aware of its wide scope. As with class E, a typical solution has a primary flight of m steps (m > 1) and a secondary flight of n steps, but the two flights are now separate and run in the same direction, giving the appearance of a single flight with uneven steps. The two upper pieces do not change places in the transformation; instead, each moves up or down one step relative to the base piece and to one another.
There are again two families, even more closely related than those in class E. With F1 solutions, the upper pieces move over each other in the same direction as they move over the base piece (syn-movement). With F2 solutions, they move in the opposite direction (anti-movement). Figures 5a and 5b illustrate the difference for m = 3 and n = 2, while 5a and 5e show the effect of interchanging the variables. Figures 5f and 5g show the simplest possible solutions.
The two families have different case formulae. For F1, q = m(n + 1) 1 and p = q + n + 1; for F2, q = mn + 1 and p = q + n. (It might be possible to modify these formulae, making them more similar at the cost of changing what m and n actually stand for.) F1 primary steps are (n + 1) × (n + 1); F2 primary steps are n × n; all secondary steps are 1 × 1. All values of m and n (even those sharing a common factor) result in simple cases. All F1 solutions are minimal, but a high proportion of F2 solutions are sub-minimal.
For both families, values of m and n define the case but not the whole solution; position variations can be produced by moving the secondary flight of steps relative to the primary flight. These variations can be coded by means of a third variable k (k < n) as illustrated by figures 5b and 5c. Figure 5h shows that k > 1 can produce a centro-symmetric three-piece solution; this is possible only with m odd and n = 1. Although position variations complicate the situation, they also simplify it by removing the need to consider l-p variations. Thus, changing k to n + 1 k is equivalent to changing from the landscape to the portrait variation.
There is yet one more possibility, that of producing solutions that are a kind of hybrid of double- and single-step solutions. A fourth variable j (j<>k and j < n) is needed to code these; figure 5d shows an example.
Figures 5 Parallel double-step solutions (equalised diagrams).
Key to Figures 5.
G. Triple-step solutions. In these, the case is determined by three variables, each indicating a number of steps. However, the name triple-step is not quite accurate, since the diagrams suggest not three independent flights but a two-part flight of primary steps (with h steps in the upper part and m in the lower) together with a secondary flight (of n steps). The secondary flight runs at an angle to the primary one, meeting it at the join between its upper and lower parts. In the transformation, each piece moves one step relative to each of the others. There are no hybrid solutions and no variations apart from l-p ones, which, as with the F classes, are encompassed by the variables and so can be ignored. Interchanging the values of h and m is equivalent to switching between a landscape and a portrait solution.
For this class, there are no fewer than four distinct families. They are related in pairs in two ways. Firstly, G1 and G2 solutions have a convex primary flight of steps and (like F1 solutions) show syn-movement of the two upper pieces; G3 and G4 solutions have a concave primary flight and (like F2 solutions) show anti-movement. Secondly, G1 and G3 solutions have the secondary flight joining the primary flight at the corner of a step; G2 and G4 solutions have the join in the middle of a primary step edge.
The case formulae for these families can be written in a way that brings out the relationships between them. All four families have p = q + n, and their formulae include the expression hm + hn ± mn. This expression gives q for the G1 and G3 families but p for the G2 and G4 families; it has the mn term positive for the G1 and G2 families but negative with the G3 and G4 families. With the negative sign comes the limitation that n must be greater than either h or m; with the positive sign there is no limitation. All the families have a secondary step size of m × h; the upper primary (h) steps are (n ± m) × n and the lower primary (m) steps (n ± l) × n. Again, the sign is positive for the G1 and G2 families and negative for the other two.
These formulae give both simple and composite cases for all the families. Particular cases recur for different combinations of variables, but I have not been able to find any pattern behind these recurrences. Sub-minimal solutions are produced when n is a factor of hm; this happens more often for the G1 and G2 families than for the other two. If all three variables have a common factor k, the diagrams can be scaled down by the factor of k.
The similarities between the formulae disguise some differences. For the G2 and G4 families, the base piece has a total of h + m 1 primary steps instead of the expected h + m. This is a consequence of the way the flights join, but I can see no explanation for the fact that for the G4 series, and that alone, there are actually only n 1 secondary steps!
Figures 6a-d show the four types of solution for the same set of variables (h = 2, m = 3, n = 4). Figure 6e shows the smallest example with a diagram scaled down because of a common factor between the variables. Figures 6f-g show the two smallest possible cases. Figure 6h illustrates the special point that in the G4 series with h = 1 (or m = 1) two of the pieces lose contact. Finally, note that the solution to problem 61(B) in issue 30 of GPJ is G2(2,2,1).
Figures 6A Triple-step solutions (equalised diagrams).
Key to Figures 6A.
Figures 6B Triple-step solutions continued (equalised diagrams).
Key to Figures 6B.
H. Block-step solutions. The block is my name for a rectangle (or possibly another shape) which is rotated through 90° in the transformation. This rotation rules out the use of equalised diagrams, and makes l-p variations impossible. Blocks, together with their associated types of variation, merit detailed consideration because they play a major role in solutions to the Pythagorean problem. Here, however, there is just the one H family, consisting (like the D families) of a simple series of sub-minimal solutions, each with a single flight of n steps (n > 1). The case formulae are p = n + 1, q = n, and the step size (measured in unit squares, not unit rectangles) is 1 × n.
These solutions have two different types of variations, as illustrated for the n = 2 case in figure 7a-e. Figures 7a,b show position variations (similar to those in the F families), which can be coded by means of an additional variable k, taking values of 2 and 1 in these two diagrams. The maximum k is int(n/2) + 1; figures 7f-h are partial illustrations of the three position variations for n = 4.
Figures 7b-d show what I call block variations, in which the size and shape of the block changes, but not its position. Figures 7b and 7c show the two main block variations; the one with the maximum block size (as in figure 7c) can be coded with the number 0. However, these two actually represent limits; in between them lies an infinite set of line variations. These line variations differ from those of slide solutions of rational cases (see figure 2f) in having a pattern with two mirror-image halves rather than one that repeats on different steps; they are two-sided, one piece being turned over on a 45° axis rather than rotated. Figure 7d shows one such variation, and figure 7e shows the limits of variation with the line of symmetry marked.
Analysis of block variations is best based on the k = 0 solution. The existence of a full set (as here) requires a piece (the middle piece in the figure 7c rectangle) to share corners with the block and also have a complete edge that always touches the block. Any less contact will only allow at most a pair of variations (see figures 8 l,m for an example).
Figures 7 Block-step solutions (normal diagrams).
Key to Figures 7.
|(74) 3. Irregular solutions.||é|
I have found thirteen of these solutions, covering five cases. All the solutions are orthogonal, though none are fully aligned. (Non-orthogonal irregular solutions exist for the Pythagorean problem, and could possibly exist for this problem also.) Unless otherwise noted, they will be represented by equalised diagrams and have l-p variations,
Figure 8a (drawn on a ×5 scale) shows a variable two-sided solution to the 2,1 case. This solution is unique in being point variable in two dimensions; in it, the point x can lie anywhere in the left half of the diagram. [Note: the piece on the right of the landscape diagram looks as if it might be being rotated through 90° but with an equalised diagram a 90° rotation is invalid, it is in fact being reflected.]
Figures 8b-e (drawn on a ×3 scale) show three two-sided solutions to the 3,2 case, all point-variable in one dimension. In [3,2]1, the point x can lie anywhere on the left two-thirds of the bottom line, though, as figures 8b,c indicate, moving x from the left third to the middle third changes the appearance of the solution. In [3,2]2 and [3,2]3 (which are similar enough to be regarded as variations of one another), x can lie anywhere on the left third of the bottom line. [3,2]3 requires two pieces to be turned over (one horizontally and one vertically), though there is an alternative arrangement in which one piece is turned over and one simply rotated through 180°.
None of the remaining solutions are point-variable. Figures 8f-h show three two-sided solutions to the 4,3 case, the last two requiring a 180° rotation as well as a turning over. Figure 8i shows a solution to the 5,4 case in which two pieces (the smallest ones) are turned over in different directions. This one does not have l-p variations, making it the only unique solution in the set.
Figures 8j,k show two solutions to the 5,3 case, these being the only minimal ones in the set. Both require a 180° rotation, but only the first is two-sided.
Finally, figures 8 l,m return to the 3,2 case, and are normal diagrams of block solutions. The first of these looks as if it might be the n = 2 member of a series; such a series does exist for rectangle-rectangle dissections, but fails for this problem if n <> 2. The second is really a block variation of the first, but there are no two-sided line variations this time.
Figures 8 Irregular solutions (equalised and normal diagrams).
Key to Figures 8.
This account is complete according to my work to date, but may of course contain errors. Anyway, I can hardly expect to have exhausted all the possibilities of this unexpectedly complex and interesting problem; the fact is that almost every time I have returned to the topic after a break, I have ended up by finding something new. There may well be much waiting to be discovered: new irregular solutions, new orthogonal classes or extensions of the existing ones, new relationships between classes or better mathematical treatment of case formulae. Further, there is need for an analysis of the cases for which multi-step solutions of classes E-G exist.
My hope is that readers will be inspired to investigate this problem for themselves, and will report any new discoveries they make. Further, I would welcome any offers of help with the daunting task of working on and writing up the even more complex and interesting Pythagorean problem!