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×2n) and trominoes (n×3n) are referenced by their shorter side.

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

1. 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.).
2. 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)
3. 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)
4. Divide a 20×20 or 23×23 square into 9 squares or dominoes with sides 1-9. (Erich Friedman, Diverse Square Packings)
5. Divide a 25×25 or 26×26 square into 10 squares or dominoes with sides 1-10. (Erich Friedman, Diverse Square Packings)
6. 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)
7. 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)
8. Divide a rectangle into 2 squares each of sides 1-15. (Erich Friedman, Patrick Hamlyn)(Answer)
9. Pack dominoes of size 1 to 11 in a 32×32 square. (Erich Friedman, Dominoes in Squares)
10. 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)
11. 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.
12. 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)
13. 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.

Math Games archives.

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.