Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!munnari.oz.au!bruce!dec15!mmcg From: mmcg@dec15.cs.monash.edu.au (Mike Mc Gaughey) Newsgroups: comp.theory Subject: Re: Partitioning squares into unequal squares Message-ID: Date: 28 May 91 16:33:07 GMT References: <9105242046.AA15308@athos.cs.ua.edu> Sender: news@bruce.cs.monash.OZ.AU Lines: 50 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.