Michael Reid wrote:
check out "tiling a polygon with rectangles" by claire and richard kenyon, proceedings of the 33rd foundations of computer science (FOCS), 1992, pp. 610-619.
Thanks for the reference -- I knew about this work (from listening to Jim Propp over the years), but didn't have the paper. Even with this bibliographic citation I seem to be unable to locate a hard copy in a local library -- I've printed out the .ps file at http://topo.math.u-psud.fr/~kenyon/papers/rectiles.ps.Z but this lacks all the pictures, which cover 6 out of the 10 pages!
theorem 3 of that paper asserts that, given a simply connected polyomino region tiled by m x 1 (vertical) polyominoes and 1 x n (horizontal) polyominoes, then any two such tilings can be obtained from one another by steps of the form
replace an m x n subrectangle tiled by horizontal tiles by one tiled by vertical tiles
or the inverse operation.
Oof, I should have known this; I've seen Jim Propp give a talk on the subject. Brief summary: define the height function, then show that there must be a tiling where the height function attains its maximum on the boundary of the region to be tiled -- and moreover that any tiling without this property can be turned into one with it by a sequence of the above operations (which pointwise lower the height). Then give an algorithm to take the height function on the boundary (which is determined by the shape of he region) and construct the unique tiling which attains its maximum on the boundary; in fact this can be done in linear time.
this easily implies that the answer to rich's question is "no".
Er, only if the number of tilings is larger than one, right? Ah, but in the rectangle case that's clearly satisfied: for Rich's 1x3 instance, you can always tile using only strips running in the direction of the edge whose length is a multiple of 3, and then there's clearly a 3x3 box to rotate, so we have two tilings and we're done. In tiling a rectangle with nx1 and 1xn strips, it's not a priori obvious that there can't be a unique tiling, but the result of de Bruijn that Thane Plambeck cited likewise does the trick. Probably getting to {mx1, 1xn} from there isn't hard. My valley-building argument also works with {mx1, 1xn} strips, happily. And as I mentioned, it's insensitive to some of the shape of the region, so for example applies to some unbounded regions, and some regions with holes, both of which kill the (vastly more powerful) height function technique. Come to think of it, the valley argument also bounds the maximum possible distance from the edge of the rectangle to the nearest mxn subrectangle -- er, not just as a function of m,n, but if you keep one edge length constant and let the other run off to infinity, there is a bound on how far you need to look. (Hmm, but possibly not much better than a combinatorial "pumping lemma" type argument based on counting how many ways the top edge of the tiling can look.) --Michael Kleber kleber@brandeis.edu