Given a square of n X n proportion, break the square up into smaller squares none of which can be the same dimensions as another.

theodore hwa wrote:

> See http://www.astro.virginia.edu/~eww6n/math/PerfectSquareDissection.html
>
> The smallest n for which this is possible is n=110.

[ Editor: the other sources below give 112 as the side of the smallest
  simple perfect squared square. ]

I have kept the following emails and references from my own recent
investigation into this topic.

[ Editor: posted by Stuart Anderson <sanders@fl.net.au>. ]

Lynn Johannesen wrote:

> Stuart E Anderson (sanders@fl.net.au) wrote:
> : In one of Martin Gardner's Mathematic Recreation books he described
> : the search for squares within squares.  Each construction consists
> : of a square of integer n length which is wholly composed of smaller
> : squares of sides a,b,c... , all of unique integer size.  The squares
> : fit perfectly, do not overlap and leave no empty space.  Gardner
> : gave an example of a 'perfect square' as it is called with a side
> : length of 175.  I am interested to know if further work has been
> : done in this area.
>
> By coincidence (?) the Mathematical Recreations column in Scientific
> American for July 1997 (the current one) discusses this topic,
> although in rather less detail than Gardner did.  I'm not sure how
> available that is in Australia so I'll summarize.  Ian Stewart, the
> author, gives a squared square of side 112, with 21 component
> squares, and states that this has been proved minimal.  This was
> found by A.W.J. Duijvestijn [Editor: spelled "Duivestijn" here and
> below in the original] in 1978.  In 1992 Bouwkamp and Duijvestijn
> published a list of all squared squares with 25 or fewer component
> squares, 207 total.  Sorry, no more detailed references.

Perfect Square Dissection

A Square which can be Dissected into a number of smaller squares with
no two equal is called a Perfect Square Dissection (or a Squared
Square).  If no subset of the Squares form a Rectangle, then the
perfect square is called ``simple.''  Lusin claimed that perfect
squares were impossible to construct, but this assertion was proved
erroneous when a 55-Square perfect square was published by R. Sprague
in 1939 (Wells, 1991).  Square dissections in which the squares need
not be different sizes are called Mrs. Perkins' Quilts.

There is a unique smallest perfect square which is simple, discovered
in 1978 by A. J. W. Duijvestijn [Editor: spelled "Duijvestin" here in
the original] (Bouwkamp and Duijvestijn 1992).  It is composed of 21
squares with total side length 112, and is illustrated above.  There is
a simple notation to describe perfect squares in which brackets are
used to group adjacent squares with flush tops, and then the groups are
sequentially placed in the highest (and leftmost) possible slots.  The
21-square illustrated above is then denoted [50, 35, 27], [8,19], [15,
17, 11], [6, 24], [29, 25, 9, 2], [7, 18], [16], [42], [4, 37], [33].
Sloane and Plouffe (1995) give the number of simple perfect squared
squares of order n for n>=21 as 1, 8, 12, 26, 160, 441, ....

See also Mrs. Perkins' Quilt

References

Beiler, A. H. Recreations in the Theory of Numbers: The Queen of
Mathematics Entertains. New York: Dover, pp. 157-161, 1966.

Bouwkamp, C. J. and Duijvestijn, A. J. W. ``Catalogue of Simple Perfect
Squared Squares of Orders 21 Through 25.'' Eindhoven Univ.
Technology, Dept. Math, Report 92-WSK-03, Nov. 1992.

Duijvestijn, A. J. W. ``A Simple Perfect Square of Lowest Order.'' J.
Combin. Th. Ser. B 25, 240-243, 1978.

Gardner, M. ``Squaring the Square.'' Ch. 17 in The Second Scientific
American Book of Mathematical Puzzles & Diversions: A New Selection.
New York: Simon and Schuster, 1961.

Gardner, M. Fractal Music, Hypercards, and More: Mathematical
Recreations from Scientific American Magazine. New York: W. H. Freeman,
pp. 172-174, 1992.

Kraitchik, M. Mathematical Recreations. New York: W. W. Norton, p. 198,
1942.

Mauldin, R. D. (Ed.) The Scottish Book. Boston: Birkhäuser, 1981.

Sloane, N. and Plouffe, S. ``Squaring a Square.'' Sequence M4482 in The
Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Weisstein, E. ``Perfect Squares.'' Mathematica notebook PerfectSquare.m.

Wells, D. The Penguin Dictionary of Curious and Interesting Geometry.
London: Penguin Books, p. 242, 1991.

Mrs. Perkins' Quilt

The Dissection of a Square of side n into a Sn number of smaller
squares.  Unlike a Perfect Square Dissection, however, the smaller
Squares need not be all different sizes.  In addition, only prime
dissections are considered so that patterns which can be dissected on
lower order Squares are not permitted.  The following table gives the
smallest number of coprime dissections of an n x n quilt (Sloane's
A005670).

  n    Sn
 1  1
 2  4
 3  6
 4  7
 5  8
 6-7  9
 8-9  10
10-13  11
14-17  12
18-23  13
 24-29  14
 30-39  15
 40   16
  41   15
  42-100    17>=Sn>=19

See also Perfect Square Dissection

References

Conway, J. H. ``Mrs. Perkins's Quilt.'' Proc. Cambridge Phil. Soc. 60,
363-368, 1964.

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

Dudeney, H. E. Problem 177 in 536 Puzzles & Curious Problems. New York:
Scribner, 1967.

Gardner, M. ``Mrs. Perkins' Quilt and Other Square-Packing Problems.''
Ch. 11 in Mathematical Carnival: A New Round-Up of Tantalizers and
Puzzles from Scientific American. New York: Vintage, 1977.

Sloane, N. J. A. Sequence A005670/M3267 in ``An On-Line Version of the
Encyclopedia of Integer Sequences''
http://www.research.att.com/~njas/sequences/eisonline.html and Sloane,
N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San
Diego: Academic Press, 1995.

Trustrum, G. B. ``Mrs. Perkins's Quilt.'' Proc. Cambridge Phil. Soc.
61, 7-11, 1965.

[ Editor: the text above, from Eric Weisstein's web pages, refers to
  an illustration that is not reproduced; in the table "17>=Sn>=19"
  is presumably meant as 17<=Sn<=19. ]

[ Editor: an email from Jacques Haubrich: ]

Squaring rectangles (which may happen to have equal length and width,
though most of them don't) is an old subject.  The first squared
rectangle was found in 1925 by Z. Moron (see Przeglad Mat. Fiz. 3,
152-153, 1925).

Willcocks was the first to find a simple perfect squared square.
'perfect' means that all elements are different in size - 'simple'
means that the squared area does not show sub-rectangles.  He divided a
square into 37 smaller ones.

Both Bouwkamp and Duijvestijn devoted their lives to finding squared
squares in a systematic way, which is too complicated for a short
email.  The order 21 square with side 112 was indeed found by
Duijvestijn's computer in 1978.  He generated all squared rectangles
and filtered the squares out.  For lower orders, no squared squares
were found.

Numbers of squared squares:

      order    number
        21        1
        22        8
        23       12
        24       26
        25      160
        26      441

Publications:

 - Tables relating to simple squared rectangles of orders 9 to 14
   by
   C.J.Bouwkamp, A.J.W.Duijvestijn and P.Medema
   Published by Eindhoven University of Technology, EUT Report
   86-WSK-03, ISSN 0167-9708
   (note: not recommended: hard to read!)
 - Catalogue of Simple Perfect Squared Squares of orders 21 through 25
   by
   C.J.Bouwkamp and A.J.W.Duijvestijn
   EUT Report 92-WSK-03, Eindhoven, November 1992
 - Album of Simple Perfect Squared Squares of order 26
   by
   C.J.Bouwkamp and A.J.W.Duijvestijn
   EUT Report 94-WSK-02, Eindhoven, December 1994

[download from; ftp.cs.utwente.nl/pub/doc/dvs/  ]
The Catalogue and Album together list all squared squares up to order
26 (order = # of subsquares).
Order 27 is under investigation by Duijvestijn.  Since the amount of
computertime raises exponentially with the order, completion of this
job may take some time.

By diferent techniques, many solutions of larger orders were found.

Very serious and want to know all?  Contact Bouwkamp or Duijvestijn.

 Prof. Dr. C.J. Bouwkamp
 Department of Mathematics and Computer Science
 P.O.Box 513
 5600 MB  Eindhoven
 The Netherlands

 Prof. Dr. A.J.W. Duijvestijn
 Faculty of Computer Science
 University of Twente
 Enschede
 The Netherlands

-- Jacques Haubrich <jhau@win.tue.nl>

Some further references;
http://www.research.ibm.com/people/s/shearer/references/trr.html

-- Stuart Anderson <sanders@fl.net.au>, April 1998