I just looked at Gosper's pix of tilings of rectangles by 1x3s. All seem to have at least one substructure of 3x3 as three 1x3s. Are there tilings without this substructure? Rich rcs@cs.arizona.edu
Don't think so for finite rectangles; sooner or later you get something like... +--+--+--+--+------- | | | |--+--+--+ + | | | +--+--+--+ + | | |??| | + + + +--+ | | | + + + | | | +--+--+ Richard Schroeppel wrote:
I just looked at Gosper's pix of tilings of rectangles by 1x3s. All seem to have at least one substructure of 3x3 as three 1x3s. Are there tilings without this substructure?
Rich rcs@cs.arizona.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Okay, this two weeks old, so I'm pushing folks' memory, but I actually have an answer... On Tue, 8 Apr 2003, Richard Schroeppel wrote:
I just looked at Gosper's pix of tilings of rectangles by 1x3s. All seem to have at least one substructure of 3x3 as three 1x3s. Are there tilings without this substructure?
Theorem: Suppose you tile an axb rectangle with 1xn (and nx1) strips, and suppose a,b are no smaller than n. Then there must be an nxn square tiled with n aligned horizontal or vertical strips. To make life easier, I'll give the proof for Rich's observed n=3, but the general version is exactly the same. Is there any theory that goes with this statement, or is it an isolated phenomenon? --------- Proof: Step 1: Note that once you have three strips aranged thus: A B A B ACCCB you are doomed. Possibly strip CCC could be covered by another horizontal, but then you either need to lay down a third horizontal on those two, or fill the space with three aligned verticals. Call this arrangement of three strips a "valley of length 1". Step 2: Further define a "valley of length k", the arrangement A B A B A111222333...kkkB Claim: a valley of length k must contain a valley of length j for some j<k. Pf: How can a valley possibly be filled in? Of course, you could lay down another row of k horizontal strips, raising the floor of the valley. But after that you need to have some vertical strips appear. If you erect two vertical strips on the valley floor with any horizontal strips paving the floor in between them, you have created a valley of length <k, as claimed. Otherwise all your vertical strips must come in a single block. But the width of this block must be at least 3 (and indeed a multiple of 3), since the valley floor has length 3k and the horizontal strips take the spaces up 3 at a time, and we are not allowed to have three aligned vertical strips. So you cannot avoid a valley of length <k. So by induction, we're done. --------- --Michael Kleber kleber@brandeis.edu
On Tue, Apr 22, 2003 at 11:33:57AM -0400, Michael Kleber wrote:
... Theorem: Suppose you tile an axb rectangle with 1xn (and nx1) strips, and suppose a,b are no smaller than n. Then there must be an nxn square tiled with n aligned horizontal or vertical strips. ... Step 2: Further define a "valley of length k", the arrangement
A B A B A111222333...kkkB
Claim: a valley of length k must contain a valley of length j for some j<k.
Pf: ...
So by induction, we're done.
Why does there have to be a valley at all? Peace, Dylan
Sorry all, I accidentally sent that piece of mail before I was quite done with it. In particular, Dylan asked:
Claim: a valley of length k must contain a valley of length j for some j<k. So by induction, we're done.
Why does there have to be a valley at all?
The induction for an axb rectangle is started by the pseudo-valley consisting of the first three rows of the rectangle, i.e. a 3xa or 3xb hole that needs to be filled. That is, the bottom edge of the rectangle must have some row of horizontal strips along it, bounded either by vertical strips (i.e. you have a valley) or by one or both side walls of the original rectangle, which behaves precisely like a valley for the purposes of the downwards induction argument. The interesting thing to notice here is that, as a result, I'm not really using the fact that you're tiling a *rectangle* per se. All that's needed is that you're tiling a region which (1) forces a valley and (2) doesn't let you out of the nesting of valleys. You can only get out of the nesting of valleys with a funny-shaped bumpy roof -- so with flat roof, as in a rectangle, or any sort of monotone roof, or even no roof at all, the argument goes forwards. So, for example, the half-plane {(x,y):y>0} together with a valley-forcing rectangular dip {(x,y):0<=x<=a, -2<=y<=0} for any a>=2 supports exactly the same proof. It seems to me that this must be stronger than what you can prove with a coloring argument, since it is so insensitive to the shape of the region. Maybe with work this could lead to some sort of lower bound on how many 3x3 squares a tiling of an axb rectangle must contain, but I haven't thought through this at all. --Michael Kleber kleber@brandeis.edu
participants (4)
-
Dylan Thurston -
Hugh Everett -
Michael Kleber -
Richard Schroeppel