borie@ATHOS.CS.UA.EDU (Richard Borie) (05/28/91)
Is it possible to partition the interior of a square into smaller squares, no two of which have the same size? (Notice that it is trivial to partition a square with side 2 into 4 squares each with side 1, hence the requirement of distinct sizes.) The closest I have been able to get is to partition a 32-by-33 rectangle into squares with sides 1, 4, 7, 8, 9, 10, 14, 15, and 18. This problem is related to that of finding two (dual?) partial orders over the same set of elements, such that a chain in one order corresponds to an antichain in the other, and such that the sum of the elements along any maximal chain or antichain is the same. (Intuitively, the squares are the elements of the partial orders, one partial order is the relation "is to the east of" and the other is the relation "is to the south of".)
mmcg@dec15.cs.monash.edu.au (Mike Mc Gaughey) (05/28/91)
borie@ATHOS.CS.UA.EDU (Richard Borie) writes: >Is it possible to partition the interior of a square into >smaller squares, no two of which have the same size? I'd think not, assuming you want a finite number of squares. Here's a proof, but beware - I don't do this for a living... Assume you have a square, S, which is to be tiled as you suggest. Choose, and color in, all of the sub-squares lining the top of the square. At any point, P, along the top of S, we can say it's colored to depth D (D is currently just the size of the subsquare below P). Notice that there is some number (N) of distinct depths. Obviously, this starts off as the number of squares lining the top edge, which is at least 2. No two of the colored squares can be the same size, so there will be a number of "hollows" between the squares (or, if they are placed along the edge in, say, decreasing order, there'll be a hollow between the right edge of S and the second last square). Choose one. We cannot fill this hollow completely with one square, because the square required would be the same size as the colored square lining the top edge of the hollow, so there must be at least two unequally-sized subsquares placed along the top edge of the hollow. But placing two (or more) unequally-sized squares in a hollow means that you can never decrease the number (N) of distinct colored depths in S - in the best case, you'll keep N constant (if the left square matches the level of the left neighbor, and the right square matches the level of the right neighbor). If either of the new squares are next to a wall, the best you can do is (still) keep N constant. Obviously *both* squares being placed in the hollow can't be next to the left and right walls. To complete the tiling of S, however, we need to ensure that after the last tile is laid, N=1 (and the depth, D, is just the side length of S). >This problem is related to that of finding two (dual?) partial orders >over the same set of elements, >such that a chain in one order corresponds to an antichain in the other, >and such that the sum of the elements along any maximal chain or antichain >is the same. Interesting... Mike. -- Mike McGaughey AARNET: mmcg@bruce.cs.monash.oz.au "His state is kingly; thousands at his bidding speed, And post o'er land and ocean without rest." - Milton.
nc0i+@andrew.cmu.edu (Neil J. Calkin) (05/28/91)
Check out the chapter on electrical networks in Bollobas, Intro to Graph Theory, Springer Verlag Graduate Texts in Math, #63; yes it is possible, and was first done by Sprague, adn by Brooks, Smith, Stone and Tutte, in '39 and '40 respectively. The smallest example is a decomposition of a 21 x 21 square. Neil Calkin, Department of Mathematics, Carnegie Mellon University.
nc0i+@andrew.cmu.edu (Neil J. Calkin) (05/29/91)
Whoops: mistake in my earlier posting: the smallest decomposition of an integer sided square into distinct integer squares is of a 112x112 square, into 21 incongruent squares. Neil Calkin, Department of Mathematics, Carnegie Mellon University.
mmcg@dec15.cs.monash.edu.au (Mike Mc Gaughey) (05/29/91)
I wrote: >borie@ATHOS.CS.UA.EDU (Richard Borie) writes: >I'd think not, assuming you want a finite number of squares. >Here's a proof, but beware - I don't do this for a living... Oops! I'm glad about that... >subsquares placed along the top edge of the hollow. But placing two >(or more) unequally-sized squares in a hollow means that you can never >decrease the number (N) of distinct colored depths in S - in the best >case, you'll keep N constant (if the left square matches the level of >the left neighbor, and the right square matches the level of the right >neighbor). If either of the new squares are next to a wall, the best >you can do is (still) keep N constant. Obviously *both* squares being >placed in the hollow can't be next to the left and right walls. This is wrong, sorry. If you place 2 squares in a single hollow, it is possible to decrease N by 1. Should have been obvious, really - my "proof" also showed that you couldn't tile a rectangle. Cheers, Mike. -- Mike McGaughey AARNET: mmcg@bruce.cs.monash.oz.au "His state is kingly; thousands at his bidding speed, And post o'er land and ocean without rest." - Milton.
rmc@snitor.uucp (Russell Crook) (05/29/91)
It is definitely possible; one of Martin Gardner's mathematical
games collections (or another of hius puzzle books) gave some
history and two examples.
Only for some squares, of course.
I may have it at home if you are really interested.
-
--
Russell Crook, Siemens Nixdorf Information Systems Sietec Open Systems Division
2235 Sheppard Ave. E., Willowdale, Ontario Canada M2J 5B5 +1 416 496 8510
"... technology so advanced, even we don't know what it does."
CAN/EU/USA rmc.tor@sni.ca/rmc.tor@sni.de/rmc.tor@sni-usa.com or uunet!snitor!rmc
--
------------------------------------------------------------------------------
Russell Crook, Siemens Nixdorf Information Systems, Toronto Development Centre
2235 Sheppard Ave. E., Willowdale, Ontario, Canada M2J 5B5 +1 416 496 8510
uunet!{imax,lsuc,mnetor}!nixtdc!rmc, rmc%nixtdc.uucp@{eunet.eu,uunet.uu}.net,chisnall@cosc.canterbury.ac.nz (The Technicolour Throw-up) (05/30/91)
From article <9105242046.AA15308@athos.cs.ua.edu>, by borie@ATHOS.CS.UA.EDU (Richard Borie): > Is it possible to partition the interior of a square into > smaller squares, no two of which have the same size? Indeed it is. I found the following in Martin Gardner's "Mathematical Diversions": The best known problem of this type is that of fitting a set of squares no two of which are alike into a larger square without any overlap or leftover space. If we think of the larger square as a lattice of unit squares to be divided along lattice lines into unequal squares, the smallest-known square that can be so divided has a side of 175 units. It can be cut into 24 unequal squares. The reader will find a picture of it on page 206 of "The 2nd Scientific American Book of Mathematical Puzzles & Diversions", in a chapter by William T. Tutte explaining how he and his friends used electrical-network theory to find "squared squares" of this type. In case it sounds like this contradicts Neil Calkin's posting I should reiterate someone else's posting: the 112x112 square is the smallest decomposable square when 'smallest' is measured in terms of the number of pieces required, the 175x175 square is the smallest known when 'smallest' is measured in terms of the length of the sides of the square. -- "Merely corrobarative detail, intended to give artistic verisimilitude to an otherwise bald and unconvincing narrative" -- W.S. Gilbert Name: Michael Chisnall email: chisnall@cosc.canterbury.ac.nz
ajm@mirsa.inria.fr (Alain Jean-Marie,E113,657846) (05/30/91)
From article <9105242046.AA15308@athos.cs.ua.edu>, by borie@ATHOS.CS.UA.EDU (Richard Borie): > Is it possible to partition the interior of a square into > smaller squares, no two of which have the same size? > (Notice that it is trivial to partition a square with side 2 > into 4 squares each with side 1, hence the requirement of distinct sizes.) > The closest I have been able to get is to partition a 32-by-33 > rectangle into squares with sides 1, 4, 7, 8, 9, 10, 14, 15, and 18. > In F. Le Lyonnais' book: "Les Nombres Remarquables" (Hermann Ed.), such a square is called "perfectly perfect". According to this book, the smallest such square is 112 x 112 and is of "order" 21, that is, contains 21 squares. This is the smallest possible order. It has been discovered by A. W. Duijvestijn (1976 or 1978) by computer. Le Lyonnais gives the list of the sizes of the smaller squares: (2,4,6,7,8,9,11,15,16,17,18,19,24,25,27,29,33,35,37,42,50), but no drawing nor precise reference. He quotes other known perfectly perfect squares: one of order 24 and size 175, and one of order 26 and size 608 (Brooks, Smith, Tutte, 1938). A. Jean-Marie
raoult@irisa.fr (Jean-Claude Raoult) (05/30/91)
C A L L F O R P A P E R S | C A A P | | E S O P | | 1 9 9 2 | CAAP '92 Colloquium on Trees in Algebra and Programming ESOP '92 European Symposium On Programming ________________________________________________________________ | | _!_ _!_ _!_ _!_ \ R E N N E S / _!_ _!_ _!_ _!_ /|\ /|\ /|\ /|\ \ / /|\ /|\ /|\ /|\ _!_ _!_ _!_ _!_\ 1 9 9 2 /_!_ _!_ _!_ _!_ /|\ /|\ /|\ /|\ \ / /|\ /|\ /|\ /|\ _________________________________________________________________ CAAP '92 CAAP is the acronym for " Colloque sur les Arbres en Algebre et en Programmation". The previous 16 colloquia were held in France, Italy, Germany, Spain, Denmark, England. Every even year, as in '92, it is held jointly with ESOP, and every other year, it is part of TAPSOFT (Theory And Practice of SOFTware development). In the beginning, CAAP was devoted to algebraic and combinatorial properties of trees, and their role in various Eelds of computer science. Now, the scope of CAAP has been extended to other discrete data structures, like graphs, equations and transformations on them, logical definitions for sets of graphs, etc. Typical applications of interest are the syntax and semantics of programming languages, including concurrent and logic programming. Contributions are also solicited concerning the complexity of algorithms, algorithms on, and visualization of, discrete data structures. CAAP PROGRAMME COMMITTEE J._C. Raoult (Rennes, France), chairman A. Arnold (Bordeaux, France) A. Bertoni (Milano, Italy) P. Darondeau (Rennes, France) M. Dauchet (Lille, France) R. De Nicola (Pisa, Italy) M. Dezani_Ciancaglini (Torino, Italy) J.W. Klop (Amsterdam, Netherlands) H.J. Kreowski (Bremen, Germany) M. Nivat (Paris, France) A. Poigne (St. Augustin, Germany) M. Steinby (Turku, Finland) C. Stirling (Edinburg, Great Britain) W. Thomas (Kiel, Germany) J. Tiuryn (Warsaw, Poland) ESOP '92 ESOP is the acronym of European Symposium On Programming. The previous symposia were held in Germany, France and Denmark. They continue lines begun in France and Germany under the names Colloque sur la Programmation and the GI workshops on Programmiersprachen und Programmentwicklung. ESOP addresses fundamental issues and important developments in the specification and implementation of programming languages and systems. Papers are especially encouraged that describe practical work based on theory or computer experiments implementing theoretical concepts and formal models. ESOP PROGRAMME COMMITTEE B. Krieg_Brueckner (Bremen,Germany) chairman E. Astesiano (Genova, Italy) G. Cousineau (Paris, France) O._J. Dahl (Oslo, Norway) H. Kirchner (Nancy, France) T. Maibaum (London, Great Britain) A. Mazurkiewicz (Warsaw, Poland) P. Mosses (Aarhus, Denmark) B. Nordstroem (Goeteborg, Sweden) F. Orejas (Barcelona, Spain) D. Sannella (Edinburgh, Great Britain) P. Wadler (Glasgow, Great Britain) R. Wilhelm (Saarbruecken, Germany) INVITED SPEAKERS FOR CAAP_ESOP B. Courcelle (Bordeaux, France) O.J. Dahl (Oslo, Norway) H. Ganzinger (Saarbruecken, Germany) A. Tarlecki (Warsaw, Poland) SYSTEMS EXHIBITION Non_commercial software systems may be demonstrated in parallel with the conference. Authors are invited to make a proposal for demonstrations to the chairmen. DATES AND PLACE Deadline for submission: September 6, 1991 NotiEcation of acceptance: November 12, 1991 Final version due: December 23, 1991 Conference: February 24-28, 1992 The conference will be held at the University of Rennes I, on the campus of Beaulieu. Prices will be kept as low as possible. SUBMISSIONS Authors are invited to submit 5 copies of a draft paper limited to 20 pages (in English). Proofs of non trival results should be included. Following the tradition, the members of the programme committee do not submit papers, even co-authored. Send to the CAAP programme chairman: J._C. Raoult, CAAP IRISA, Campus de Beaulieu F_35042 RENNES CEDEX email: raoult@irisa.fr or to the ESOP programme chairman: B. Krieg_Brueckner, ESOP FB Mathematik und Informatik Universitaet Bremen Postfach 330 440 BRD_2800 BREMEN 33 email: bkb@informatik.uni_Bremen.de
bimandre@icarus.cs.kuleuven.ac.be (Andre Marien) (05/30/91)
The prolog system of A. Colmerauer, Prolog III, uses this as a showcase: fill some rectangle with some (!=) squares and comes up with only two solutions. The first is for a 33 /32 rectangle: 9 10 14 1 8 7 4 15 18 I don't have the other one handy. Andre' Marien