Given two naturals $s<t$. Is there always a square (or at least a bigger rectangle) that can be tiled with $s\times t$ rectangles in an irreducible way (i.e. any grid line splitting it cuts at least one of the $s\times t$ rectangles of the tiling)?

E.g. for $(s,t)=(1,2)$, it is well known that a $\underline{6\times 6}$ square has no irreducible tiling, but a $\underline{8\times 8}$ one does, and so do in fact all other rectangles with even area and sides bigger than $5\times 6$. I think I have seen a similar statement for $(s,t)=(2,3)$ somewhere, but can’t seem to find the article anymore. So:

What is known about the existence of such a rectangle for given $(s,t)$, and maybe even about lower/upper bounds for the sides of a minimal one?

  • $\begingroup$ Note that by "$s\times t$ rectangles" I obviously mean "rectangles with sides $s$ and $t$", not the number of them :) $\endgroup$ – Wolfgang Jul 12 '14 at 17:10
  • 1
    $\begingroup$ You might check Klarner's Theorem (Thm. 5) and its corollary in: Klarner, D. A. (1969). Packing a rectangle with congruent $N$-ominoes. *Journal of Combinatorial Theory, 7*(2), 107-115. $\endgroup$ – Benjamin Dickman Jul 12 '14 at 20:59

The answer is YES, and it's a rather easy claim to prove. I will assume that $k:=gcd(s,t)=1$ since otherwise we can divide everything by $k$. First, note that you can tile square $Q=[st \times st]$ in two different ways. Now take $nQ = [nst \times nst]$ and a standard "brick tiling" of $nQ$, with $stn^2$ copies of translates of $[s\times t]$. There are $\theta(n)$ lines to be "blocked". For every copy of $Q$ inside $nQ$, we can "flip" from one tiling to another. This will block some constantly many lines. Observe that if we flip one $Q$, we cannot flip any neighbors at constant radius. But since the area of $nQ$ grows quadratically and the number of lines linearly, these are plenty of other potential flips to make when $n$ is large enough.

This is not a proof, more like an explanation. Essentially, a random tiling of $nQ$ will work w.h.p. For the real proof, one would need to give an explicit construction of positions of $Q$ which need to be flipped. These can be constructed by starting in the lower left corner $(0,0)$ and making repeated shifts by $(1,\ell)$ for sufficiently large $\ell$; here we take coordinates mod $stn$. E.g. $\ell=2(s+t)$ will work. The details are straightforward.

P.S. Let me mention also a cute paper by Chung, Gilbert, Graham, Shearer and van Lint on such "irreducible" tilings, and our paper which shows how complicated tilings with rectangles can get.


Here's an easy proof in the case that $(h, \ell)=(1, 2k)$, with an explicit bound.

Claim. For $(h, \ell)=(1,2k)$, there is an irreducible tiling of a $8k \times 8k$ square.

Proof. Tile the $(k,2k)$-rectangle horizontally, and the $(2k,k)$-rectangle vertically. Regarding these as $(1,2)$-rectangles and $(2,1)$-rectangles, we then use an irreducible tiling of the $8k \times 8k$ square $S$. Call a line bad if it separates $S$ into two tiled rectangles. Let $b$ be a bad line. By irreducibility and symmetry we may assume that $b$ passes through the interior of some $(k,2k)$-rectangle $R$. In particular, $b$ is horizontal and so $b$ does not meet any vertical rectangle $R$ (including on the boundary of $R$). Therefore, $b$ is actually a bad line for the induced $(1,2)$-tiling, which is a contradiction.

Without loss of generality we may assume that $gcd(h, \ell)=1$, and I think the above proof should work if one of $h$ or $\ell$ is even.

  • $\begingroup$ Why not just stripe each 1 x 2 with k stripes to get an 8k by 8k such division? (I could be overlooking something obvious.) $\endgroup$ – The Masked Avenger Jul 13 '14 at 6:52
  • $\begingroup$ I suppose you mean $k/2$ stripes, and you are right, that works. I guess I did it this way because I was thinking of the case $gcd(h,\ell)=1$ with $\ell$ even, and I think the above proof goes through. $\endgroup$ – Tony Huynh Jul 13 '14 at 7:12
  • $\begingroup$ So basically, I think the only case remaining is $h$ and $l$ both odd. The $gcd$ condition is without loss of generality. $\endgroup$ – Tony Huynh Jul 13 '14 at 7:19
  • $\begingroup$ I think I mean k, as each rectangle becomes 1/k by 2, not 1 by 2/k. Anyway, I suggested that because it is easier for me to follow than your explanation. Of course, I'm falling asleep, so I'm not dissing your explanation. $\endgroup$ – The Masked Avenger Jul 13 '14 at 7:20
  • $\begingroup$ Yes, you are right, I forgot I wrote $2k$ instead of $k$. And come to think about it, this should work in the general case that one of $h$ and $\ell$ is even. So I am dissing my own explanation. I'll edit now and then pass out. $\endgroup$ – Tony Huynh Jul 13 '14 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.