From: hwatheod@leland.Stanford.EDU (theodore hwa)
Newsgroups: sci.math,rec.puzzles
Subject: Re: Dissection of square (Or Rectangle) into unequal squares.
binesh@hex21.com wrote:
: Hi...
: I was reading in my encyclopaedia about number games and I came
: upon this interesting one, that I'm trying to come up with an algorithm
: for (given that the encyclopaedia CLAIMS that there's a solution.)
:
: The problem is as follows...
: 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...
See http://www.astro.virginia.edu/~eww6n/math/PerfectSquareDissection.html
The smallest n for which this is possible is n=110.
==============================================================================
Date: Sat, 11 Apr 1998 17:46:00 +1000
From: Stuart Anderson
Newsgroups: sci.math,rec.puzzles
Subject: Re: Dissection of square (Or Rectangle) into unequal squares.
[previous post deleted -- djr]
I have kept the following emails and references from my own recent
investigation into this topic.
I am writing a Director lingo script which draws Perfect Squares and displays
images inside them using text files with the compact notation. I've got it
working and hopefully should have it shocked and available on the web soon.
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. Some questions;
> : Q1 What is the construction of the smallest possible perfect square?
>
> : Q2 Is there an optimised pruned search algorithm which could
> efficiently
> : catalog perfect squares?
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. Duivestijn in 1978. In 1992 Bouwkamp and Duivestijn published
> a list of all squared squares with 25 or fewer component squares, 207
> total. Sorry, no more detailed references.
Perfect Square Dissection
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. Duijvestin (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.
-----------------------------------------------------------------------
jhau@win.tue.nl (Jacques Haubrich)
Thu 4:15
Subject:
Re: Squaring the square
To:
sanders@fl.net.au
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
Cheerio,
Jacques - jhau@win.tue.nl
Some further references;
http://www.research.ibm.com/people/s/shearer/references/trr.html
==============================================================================
From: Carl Funk
Newsgroups: sci.math,rec.puzzles
Subject: Re: Dissection of square (Or Rectangle) into unequal squares.
Date: Sat, 11 Apr 1998 03:38:29 -0400
[opriginal post deleted -- djr]
Martin Gardner devoted an entire chapter to the solution of this puzzle
in one of his books. (Mathematical Puzzles & Diversions, Vol. 2)
I won't bother trying to reproduce it here, since it is kind of long.
He does have an illustration of the smallest solution: a square with
sides of 175, broken up into 24 smaller squares.
Carl
==============================================================================
From: mwdaly@pobox.com (Matthew Daly)
Newsgroups: sci.math,rec.puzzles
Subject: Re: Dissection of square (Or Rectangle) into unequal squares.
Date: 11 Apr 1998 12:05:10 GMT
[previous post deleted -- djr]
This problem also shows up in one of my college Graph Theory books (Graph
Theory with Applications by J.A. Bondy and U.S.R. Murty, North Holland,
1976) as an application of network theory. If nothing else, it will
describe a mathematical model for perfect squares (and rectangles) that
might work better in your computer.
-Matthew