🚀 go-pugleaf

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.