# Does any set of dominoes tile some common figure?

Let $$D_1,\dots,D_n \subset \mathbb{Z}^2$$ be two-point sets, i.e. 'dominoes' (unlike common dominoes, these are not necessarily connected, but I couldn't come up with a better name).

Does there always exist finite $$B \subset \mathbb{Z}^2$$ that can be partitioned into disjoint translates of $$D_i$$ for all $$i \in [n]$$?

For instance, if $$D_1= {\tiny \square\square} , D_2 ={\tiny \square}\hspace{-6.5pt}{\ ^{^{ _\square}}},$$ one can simply take $$B=\boxplus.$$ However, if we add just one domino $$D_3 = {\tiny \square}\hspace{-1.4mm}{\ ^{^{ _\square}}},$$ or two dominoes $$D_3 = {\tiny \square}\hspace{-1.4mm}{\ ^{^{ _\square}}}, D_4 = \hspace{-1.4mm}{\ ^{^{ _\square}}}\hspace{-1mm}{\tiny \square},$$ then the suitable shapes become much more complex: \begin{align} & \large \square \square \phantom{\square \square \square \square \square \square \square} \large \large\square \square\\[-10pt] \large \square & \large \square \square \square \phantom{\square \square \square \square \square} \square \square \square \square \\[-10pt] \large \square & \large \square \square \square \phantom{\square \square \square \square \square} \square \square \square \square \\[-10pt] \large\square \square & \large \square \square \phantom{\square \square \square \square \square} \square \square \square \square \square \square \\[-10pt] \large\square \square & \large \phantom{\square \square \square \square \square \square \square} \square \square \square \square \square \square \\[-10pt] &\large \phantom{\square \square \square \square \square \square \square \square}\square \square \square \square \\[-10pt] &\large \phantom{\square \square \square \square \square \square \square \square} \square \square \square \square \\[-10pt] &\large \phantom{\square \square \square \square \square \square \square \square \square} \square \square \\[-10pt] \end{align}

I expect the answer to be negative in general, though I do not see a way to prove non-existence of the desired $$B$$ for some specific sets of dominoes. Note that if we don't require $$B$$ to be finite, the question becomes trivial: one can always take $$B = \mathbb{Z}^2$$.

Assuming the negative answer, one can further ask how to decide, for a given set of dominoes, if such $$B$$ exists. Some related polyomino tiling problems are known to be NP-complete, and some are even undecidable. So, this question could also appear to be not so 'elementary' as it might look.

Finally, I am also interested in the natural generalization to $$\mathbb{Z}^m$$. Observe that the case $$m=1$$ is trivial. Indeed, if $$D_i=\{0,d_i\}$$ for all $$i \in [n]$$, then one can take $$B=[2\cdot\text{lcm}(d_1,\dots,d_n)]$$, where $$\text{lcm}$$ stands for the least common multiple.

Perhaps, the questions of this flavor have been already studied, but I was unable to find something related. Though this is not my field of research, so I probably missed something. Apologize in advance if this topic is well known.

• The fist example in my question (the one for $D_1,D_2,D_3$) is due to Ilya Bogdanov. The second one is just the first one plus its reflection. Jun 23 at 12:01
• Here is a formulation in terms of polynomials: associate a 'rising' domino consisting of (0,0) and (m,n) with $p_{m,n}:=(1+x^my^n)$ and a 'falling' domino consisting of (0,0) and (r,-s) with $q_{r,s}=(x^r+y^s)$. Then for a given finite set of non-negative pairs $\{(m_i,n_i)\}\cup\{(r_j,s_j)\}$, the question is about the existence of a polynomial in $\mathbb Z[x,y]$ with coefficients only $0$ and $1$ which is divisible by all the $p_{m_i,n_i}$ and by all the $q_{r_j,s_j}$. This formalizes the problem, but I have no idea whether it helps... Jun 23 at 16:42
• @Wolfgang: it is clear to me your condition is necessary, but is it sufficient? (Could there be some polynomial $f$ that is divisible by all of the $p$'s and $q$'s, but where the coefficients of the quotients are not all just 0's and 1's?) Jun 23 at 17:31
• Your example for $\{D_1, D_2, D_3\}$ can easily be generalized to solve the only difficult possibility in any set of 3 dominoes! So a non-tiling set must consist of at least 4 elements. Jun 24 at 11:25
• If you relax the conditions by allowing "shapes with multiplicity" (i.e., each box in the shape has a positive integer attached, indicating how many times that box needs to be covered by a tile), then there is an easy solution with area $2^n$ (again, "area" is counted with multiplicity). Represent each $D_i$ with an ordered pair $(a_i,b_i)$ of integers, indicating the coordinates of one of its boxes relative to the other; then take all $2^n$ possible subset sums (with multiplicity) as the coordinates of the boxes of your shape. Unfortunately, I don't see how to eliminate the multiplicities. Jun 25 at 1:18