31
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 23 at 12:01
  • $\begingroup$ 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... $\endgroup$
    – Wolfgang
    Jun 23 at 16:42
  • $\begingroup$ @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?) $\endgroup$ Jun 23 at 17:31
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 24 at 11:25
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 25 at 1:18

0

Your Answer

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

Browse other questions tagged or ask your own question.