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.

Improve this question
$\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$
    – Arsenii Sagdeev
    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$
    – Anthony Quas
    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$
    – Yaakov Baruch
    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$
    – Timothy Chow
    Jun 25 at 1:18

0

Reset to default

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.