Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!spool.mu.edu!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: 29 May 91 03:45:06 GMT Article-I.D.: dec15.mmcg.675488706 References: <9105242046.AA15308@athos.cs.ua.edu> Sender: news@bruce.cs.monash.OZ.AU Lines: 32 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.