Math Games |
Square Packing | Ed Pegg
Jr., December 1, 2003 |

For Christmas, Mrs. Potipher Perkins received a very pretty
patchwork quilt constructed of 169 square pieces of silk material.
The puzzle is to find the smallest number of square portions of which
the quilt could be composed and show how they might be joined
together. Or, to put it the reverse way, divide the quilt into as few
square portions as possible by merely cutting the stitches. (Henry E.
Dudeney, *Amusements
in Mathematics*, Problem 173, Mrs Perkins's Quilt)

Define a *quilt* as square made from smaller integer squares.
The *order* of a quilt is the number of smaller squares. The
*size* is the edge length *n* of the full quilt. I urge
everyone to try Dudeney's puzzle -- divide a 13×13 square into
11 smaller integer sided squares. Alternately, find an order 11
solution for quilt of size 13. No smaller order is possible, so this
is an *optimal quilt*. Any optimal quilt is a Mrs. Perkins's
Quilt. As an illustration, here are optimal quilts of size 14 to 58.

Figure 1. Mrs. Perkins's Quilts of size 14 to 58.

Note that the 34×34 solution isn't four 17×17 squares. In order to keep things interesting, the side lengths of squares in a Mrs. Perkins's Quilt cannot have a common factor. If you count the number of squares in each solution, you will see that 14×14 through 17×17 each require 12 squares -- they have order-12 solutions. Note the patterns in the above solutions. The solution for 34×34 is basically a "simple doubling" version of 17×17.

For "doubling with overlap," start with the 23×23
solution, remove the size-5 corner square, and add squares of size 18
and 23. This build-up process obtains the solution for 41×41.
Of the squares above, most are built up from smaller
solutions. The building-up method simplifies analysis -- Conway and
Trustrum were able to use it to show a log(n) bound for the growth of
the order. For many sizes, a build-up doesn't give the best solution.
Something more unusual is needed. For these, we need more interesting
items -- the *primitive quilts*.

Figure 2. Primitive Quilts -- Quilts without sub-quilts, found by Lance
Gay.

Primitive quilts are related to Perfect
Squares, which can be considered as quilts without any repeated
squares. The primitive quilts are not necessarily optimal quilts, but
that does not lessen their usefulness. As an example, consider
[13,10,5][5][9,6][10,3][3][3,3][9,9][5,5]. (See the Perfect Squares
link for more details on Bouwkamp codes.) This quilt is not optimal,
but it lies at the core of the optimal quilt of size 109. Similarly,
[14,10,5][5][9,6][9,5][3,3][10,10][6,3][3] can be expanded to make
the optimal size 153 quilt. I sent these solutions by Lance Gay to
Richard K. Guy, the maintainer of *Unsolved Problems in Geometry*
(this is problem C3). Richard studied these, then sent back new best
solutions for 199 and 202, 203, 344. He used the method of building
on primitive solutions. As of January 7, 2003, the below list shows
in boldface the lowest known order for a given square of size *n*.

{**1**| 1},
{**4**|2},
{**6**|3},
{**7**|4},
{**8**|5},
{**9**|6,7},
{**10**|8,9},
{**11**|10-13},
{**12**|14-17},

{**13**|18-23}, {**14**|24-29},
{**15**|30-39,41},
{**16**|40,42-53},
{**17**|54-70},
{**18**|71-91},

{**19**|92-120,122,126}, {**20**|121,123-125,127-154,157,158},
{**21**|155,156,159-207,209,216},

{**22**|208,210-215,217-265,268,269,273}, {**23**|266,267,270-272,274-353,355,361,364,369,373},

{**24**|354,356-360,362,363,365-368,370-372,374-446,448,450,451,453,456-459,461,468,479}.

The above list can be attacked in two ways -- computer programs and hand analysis. Dozens of improvements were discovered by Richard Guy, Lance Gay, and Geoff Morley. If you can best any of these solutions, please contact me, so that the lists can be updated.

Many more puzzles deal with squares. In the problems below, all
squares have integer sides. Dominoes (*n*×2*n*) and
trominoes (*n*×3*n*) are referenced by their shorter
side.

Figure 3. A smallest square packing from Problem 1. (Solution for 1-51)

- What is the smallest square that
contains squares of side 1-37, or 1-40? Unsolved. (
*UPIG*D5, OEIS A005842. Robert Reid, Erich Friedman, Minami Kawasaki, and Ed Pegg have solved many sequential square packing problems up to order 50. The two listed have unknown status. Orders 26, 28, 32, 33, 34, 38, 42, 47, and 48 all are highly unlikely to fit into the smallest square.). - What's the smallest square that can be tiled with 2 or more integer-sided squares so that equal sized squares don't touch? (Karl Scherer. Karl's page, Erich's page)
- Arrange squares with sides 1 1 1 1 2 2 3 3 4 5 7 8 8 9 9 10 10 11 13 to make a 30×30 square. (Patrick Hamlyn)
- Divide a 20×20 or 23×23 square into 9 squares or dominoes with sides 1-9. (Erich Friedman, Diverse Square Packings)
- Divide a 25×25 or 26×26 square into 10 squares or dominoes with sides 1-10. (Erich Friedman, Diverse Square Packings)
- Divide a 14×14, 17×17, or 20×20 square into differently sized dominoes and trominoes. (Ed Pegg Jr, Guenter Stertenbrink. Ed's Page-22 October)
- Divide a 23×23 square into smaller squares, all of them 4×4 or larger. {Extensions: 37×37 with 7×7 or larger, 53×53 with 8×8 or larger, 59×59 with 9×9 or larger, 61×61 with 10×10 or larger} (Erich Friedman, Integer Square Tilings)
- Divide a rectangle into 2 squares each of sides 1-15. (Erich Friedman, Patrick Hamlyn)(Answer)
- Pack dominoes of size 1 to 11 in a 32×32 square. (Erich Friedman, Dominoes in Squares)
- Divide a 33×32, 81×80, 97×96, or 98×97 rectangle into differently sized squares. (The first was found by Z. Moron in 1925. Compiled from Stuart E. Anderson's squaring.net)
- For 1 to
*n*, the square of their sum is equal to the sum of their cubes (provable by induction). A cube with a side of 8 can be divided into 8 "squares" with side of 1×8×8. Similarly, a cube of size 7 can be divided into 7 "squares", and so on down to a 1×1×1 cube. Arrange these 36 squares into a 1×36×36 square. This is Bob Wainwright's Partridge Puzzle (my page, Erich's page). It was first solved by Bill Cutler. - Pack squares of size 1 to 17 into a 39×46 rectangle. (The smallest rectangle for squares of size 1 to 22 is unknown. For 1-24, 43×115 has been shown by Mike Reid, but it is not verified as minimal. OEIS A081287. See also Erich's Stacking Squares)
- Using 4 copies each of squares 1-24, make a 140×140 square. (Erich Friedman)

Figure 4. Erich Friedman's solution for Problem 13.

Lots of interesting questions here, many of them unsolved, and many ripe for being solved right now. There are integer sequences that need extending. The primitive solutions need to be built up systematically. Solving these unsolved problems can be assisted by the links provided in the references. I'd like to get optimized Mrs. Perkins's Quilts up to size 300 or so.

*Addendum:*

Figure 5. New methods in Quilt building.

**References:**

Anderson, S E. "Square Listings." http://www.squaring.net/

Conway,J H. "Mrs. Perkins's Quilt." *Proc. Camb. Phil. Soc.*60
(1964), 363-368.

Croft, H T. Falconer, K. J. & Guy, R.K.
*Unsolved
Problems in Geometry*. Springer, 1991, Section C3.

DeVincentis, J. "Square the Square." http://members.bellatlantic.net/~devjoe/sqsq/.

Dudeney, H E. Problem 173 in *Amusements
in Mathematics*. New York: Dover, 1917.

Duijvestijn, A J W. "Electronic Computation of Squared Rectangles." Philips Res. Reports 17, 523-613, 1962.

Friedman, E. Integer Square Tilings, Non-Touch Tilings, Dominoes in Squares, Partridge Packings, Diverse Square Packings. http://www.stetson.edu/~efriedma/mathmagic/

Gardner, M. "Mrs. Perkins' Quilt and Other Square-Packing
Problems." *Mathematical
Carnival*. Vintage, New York:, 1977.

Pegg, E T Jr. "List of Best Solutions." http://mathpuzzle.com/perkinsbestquilts.txt.

Reid, M. "Squares 1-24 in a 55x90 Rectangle", *Journal of
Recreational Mathematics* v. 26, no. 4 (1994) p. 318

Scherer, K. "Square the Square." http://karl.kiwi.gen.nz/prosqtsq.html.

Sloane, N J A. Sequences A005670 A005842 A081287 in "The On-Line Encyclopedia of Integer Sequences." http://www.research.att.com/~njas/sequences/.

Trustrum, G B. Mrs Perkins's quilt, Proc. Cambridge Philos. Soc., (1965) 7--11.

Weisstein, E W. Perfect
Square, Mrs.
Perkins's Quilt. *Eric Weisstein's World of Mathematics.*
http://mathworld.wolfram.com/.

I greatly thank Richard K Guy and Lance Gay for assistance with this article.

*Mathematica*
Code:

<< PerfectSquare`

(* This package is available at
http://mathworld.wolfram.com/packages/PerfectSquare.m
*)

(*Figure 1*) Show[GraphicsArray[Partition[Graphics[Squares[BouwkampConstruction[#[[1]]]], AspectRatio -> Automatic, PlotRange -> All] & /@ MrsPerkinsQuilts /@ Range[14, 58], 9], GraphicsSpacing -> {0, 0}]];

PrimitiveQuilts={{{3,3,8},{6},{1,1,6},{5,2,1},{1},{3}},
{{7,6,3},{3},{4,5},{4,3},{1,6},{5},{5}},

{{2,4,7,6},{2},{6},{3,3},{3,2,2},{10},{9}},
{{9,6,5},{1,4},{7},{5,4},{4},{1,7,7},{6}},

{{12,8},{3,5},{1,2},{8,3,1,1},{2,7},{5}},
{{4,8,9},{4},{6,5,1},{4,6},{1,8},{7},{6}},

{{13,6,5},{1,4},{7},{4},{7,6,11},{1,5},{4,4}},
{{15,12},{4,8},{8,6,1},{5},{1,7},{6,6},{4,4}},

{{15,13},{6,7},{6,5,4},{9,1},{1,4},{8},{7},{4}},
{{12,8,8},{7,9},{9,3},{8,2},{11},{7,2},{5,5}},

{{1,1,3,8,7,12},{2},{5},{2,5},{12,1},{3},{20},{12}},
{{4,4,5,20},{7,1},{6},{13},{7,13},{9,4},{1,6},{5}},

{{15,10,10},{8,12},{12,3},{7,4},{3,13},{10},{4,8},{4}},
{{8,9,8,11},{8},{3,5},{7,2},{5},{2,9},{7},{20},{16}},

{{17,9,10},{8,1},{11},{11,10,4},{15},{1,9},{4,8},{4}},
{{20,8,11},{5,3},{2,12},{7},{19,8},{5,7},{11,2},{9}},

{{8,8,28},{16},{9,7},{5,7,16},{2,5},{11},{3,2},{9},{8}},
{{22,13,16},{9,4},{1,15},{5},{14,13,9},{4,20},{1,16},{15}},

{{36,29},{16,13},{14,13,9},{4,9},{4,20,1},{5},{1,16},{15},{14}},

{{25,20,23},{5,12,3},{26},{23,7},{19},{20,3},{7,19},{17,5},{12}}};

(* Figure 2 *) Show[GraphicsArray[Partition[Graphics[Squares[BouwkampConstruction[PrimitiveQuilts[[#]]]], AspectRatio -> Automatic, PlotRange -> All] & /@ Range[20], 5], GraphicsSpacing ->{0, 0}]];

A zip of Eric Weisstein's packages, used in this column, is
available at the *Mathematica*
Information Center. Related notebooks by Eric are at his Mrs.
Perkins's Quilt and Perfect
Square pages. For Figure 1, I used a slightly different set of
solutions, see http://www.mathpuzzle.com/perkinsbestquilts.txt.
At this same link, the code used by Lance Gay is available.

Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.

Ed Pegg Jr. is the webmaster for mathpuzzle.com.
He works at Wolfram Research, Inc. as the administrator of the
*Mathematica*
Information Center.