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