What rectangles can a set of rectangles tile?
If we have a set of $p_i \times q_i$ rectangles, with $p_i, q_i \in \mathbf{N}$, which $m \times n$ rectangles can be tiled with copies from the set? (No rotation allowed.)
What I know so far:
- We need $mn = \sum p_iq_ic_i$ for some $c_i \geq 0$.
- Considering how rectangles form the border, we need at least $m = \sum a_ip_i$ and $n = \sum b_iq_i$ for some $a_i \geq 0$ and $b_i \geq 0$.
These is not enough, for example we cannot tile a $5\times 5$ square with a $2 \times 2$ and $3 \times 3$ square.
- Tilings are possible for when there is a subset such that all the $p_i$ divides $m$ and $n = \sum b_iq_i$ for some $b_i \geq 0$. Not all tilings are of this type (see for example the figure below).
It also looks like for the case of two rectangles, one of $p_i$ needs to divide $m$ or one of $q_i$ needs to divide $n$. (The argument is roughly that if it doesn't, there is no path from one border of the big rectangle to the opposite border with only one type of rectangle. This is only possible if the two types of rectangles form regions that make some checker board pattern, in which case the regions are all of the form $p_1p_2c \times q_1q_2d$.)
I did quite a bit of searching, but could not find an answer.
(Some context: I was looking into prime rectangles of polyominoes. I thought knowing the prime rectangles will give a complete description of all rectangles that can be tiled by the polyomino... but then I realized I did not in fact know which rectangles can be made from another set.)
(Update: I took these initial findings and asked a question on Math Overflow. There are some more answers there.)
It seems the problem is much trickier than I thought. After some more investigation, I have gathered the following, which only provides a partial answer.
Theorem 1 For two rectangles with $\gcd(p_1, p_2) = \gcd(q_1, q_2) = 1$, a tiling exists if and only if one of the following holds [1]:
- $p_1 \mid m$ and $q_1 \mid n$
- $p_2 \mid m$ and $q_2 \mid n$
- $p_1q_1 \mid m$ and $ap_2 + bq_2 = n$ for some integers $a, b$
- $p_2q_2 \mid n$ and $ap_1 + bq_1 = n$ for some integers $a, b$.
Theorem 2 For any number of rectangles, if any side of all rectangles share a common factor, then they can only tile a large rectangles if one side has the same common factor [2].
For two rectangles that do not satisfy the conditions of Theorem 1, we can divide the sides of the two rectangles and the corresponding side of the big rectangle by the common factor and then test with Theorem 1.
Theorem 3 A set of rectangles satisfying $\gcd(p_i, p_j) = \gcd(q_i, q_j) = 1$ for $i \neq j$, there exist some $C$ such that the set will tile any rectangle with $m, n > C$ [3, 4].
How to find such a $C$ is given in [3]. Unfortunately, this $C$ can be quite large, and is not generally tight (there is a smaller $C$ that also works). So there is a whole bunch of rectangles for which it says nothing.
In addition, it says nothing about rectangles that do not satisfy the conditions. For example, it is hard to know much about which rectangles can be tiled by a set with a $6\times 6, 10\times 10$ and $15 \times 15$. In this example, pairs of squares share a common factor, but we cannot reduce the tiling problem because there is not a common factor among all tiles.
Theorem 4 For every finite set of rectangular tiles, the tileability problem of an $m\times n$ rectangle can be decided in $O(\log mn)$ time.
This result is mentioned in [4] (and some others), but unfortunately it references a mysterious unpublished manuscript, and there is no details available. This is frustrating because it answers my question exactly if they also gives the algorithm.
[1] Bower, Richard J.; Michael, T.S., When can you tile a box with translates of two given rectangular bricks?, Electron. J. Comb. 11, No. 1, Research paper N7, 9 p. (2004). ZBL1053.05027.
[2] de Bruijn, N.G., Filling boxes with bricks, Am. Math. Mon. 76, 37-40 (1969). ZBL0174.25501.
[3] Labrousse, D.; Ramírez Alfonsín, J.L., A tiling problem and the Frobenius number, Chudnovsky, David (ed.) et al., Additive number theory. Festschrift in honor of the sixtieth birthday of Melvyn B. Nathanson. New York, NY: Springer (ISBN 978-0-387-37029-3/hbk; 978-0-387-68361-4/ebook). 203-220 (2010). ZBL1248.11022.
[4] Pak, Igor; Yang, Jed, Tiling simply connected regions with rectangles, J. Comb. Theory, Ser. A 120, No. 7, 1804-1816 (2013). ZBL1314.05034.