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