8
$\begingroup$

Suppose that we are trying to tile $\mathbb{Z}^3$ with dominoes, i.e., two face-adjacent cubes. We start going about this haphazardly, laying dominoes in random spots. How long can we keep this up before it becomes impossible to extend existing domino placements to a complete tiling?

Obviously, with $6$ tiles we can make it impossible to extend: surround every face of a single-cube hole that cannot be filled. I think I've got a proof that any $3$ dominoes can be extended to a tiling of space, but I don't know how to resolve the cases of $4$ or $5$ without extremely involved casework.

In two dimensions, it is relatively easy to show that any $3$ dominoes extend to a tiling of the plane, but $4$ dominoes obviously do not in general. This makes me weakly suspect that the answer is $6$ in three dimensions, and $2n$ in dimension $n$ more generally, but I don't trust my intuition to be particularly reliable here.

Edit: I can prove that any $4$ dominoes can be extended to a tiling of $\mathbb{Z}^3$, as follows:

Define a blob to be any domino or single cell. First, we prove that the complement of any three disjoint blobs in the plane can be tiled by dominoes (this is a bit of work; I found it helpful to first prove any one blob in a quadrant extends to a tiling of that quadrant, then that any two blobs extend to a tiling of the half-plane, then the planar case).

Then, take an arrangement of four dominoes. Choose any pair of them; there is at least one axis-aligned plane separating that pair. Then, look at the unit-width "slabs" parallel to this plane; each such slab contains at most three blobs (because a domino's intersection with a planar slab is either a domino, a single cell, or empty), and so can be tiled by dominoes. (In fact, this proof generalizes to four blobs in $\mathbb{Z}^3$, not just four dominoes.)

So only the case of $5$ dominoes remains.

$\endgroup$
4
  • 3
    $\begingroup$ This is a nice question! I believe the answer is 6 in three dimensions as well. I think the easiest way would be to show that in the plane, the only configurations of four dominoes or even monominoes(?) that don't extend to a domino tiling are those that have a single square surrounded. This would imply that the only 3d obstructions are those where one plane has a single square surrounded, and then the case analysis gets a lot easier. (For instance, that rules out the 4-domino case immediately.) $\endgroup$ – Steven Stadnicki Jan 14 at 18:31
  • $\begingroup$ @StevenStadnicki: Yeah, that seems like a good direction for the $4$-domino case; I worry one might run into some difficulty in the $5$-domino case, because there are arrangements of $5$ dominoes in the plane whose complement is connected but non-tileable. (I suppose one can ask analogously if the only $6$-domino impossible configurations are those with a disconnected complement.) $\endgroup$ – RavenclawPrefect Jan 14 at 18:41
  • $\begingroup$ I'm having a hard time visualizing that — can you give an example of such a 5-domino configuration? $\endgroup$ – Steven Stadnicki Jan 14 at 19:20
  • 1
    $\begingroup$ Sure! $\endgroup$ – RavenclawPrefect Jan 14 at 19:22
2
$\begingroup$

Consider a large 3d torus with even side lengths that contains the configuration of 5 starter dominoes. Colour the cells making up the torus white and black in an alternating 3d checkerboard pattern. (Each white cell has 6 black neighbours, and vice-versa. This is possible because the torus has even side lengths.)

Let $X$ be the set of black squares not covered by any of the 5 starter dominoes and $Y$ be the set of white squares (including the 5 covered by starter dominoes). Note that $|X|+5 = |Y|$. For every set $B\subset X$, define $N(B)$ to be the set of all neighbours of the elements of $B$. (So $y\in Y$ will be an element of $N(B)$ if and only if it is neighbours with some $x\in B$.)

According to Hall's marriage theorem, it will be possible to tile the torus with dominoes (and thus the whole plane, since the torus tiling can just be repeated) if the following condition is met: "For all sets $B\subset X$, $|N(B)| \geq |B| + 5$." i.e. each subset of $n$ black cells has at least $n+5$ white neighbours. (This is so that even if all 5 starter dominoes happen to be covering our neighbours, we still have $n$ neighbours left over to satisfy the Hall marriage criterion. This is a sufficient condition, but not a necessary one.)

This seems obviously true after a bit of thought, but I found it very difficult to come up with a proof. Here is a messy one with 3 separate cases. Maybe it's possible to come up with a better proof.

Proof:

Make the torus very large: at least $4\cdot 21600$ cells long in each direction. (It may need to be bigger in order to contain the full configuration of starter dominoes which could be spaced very far apart, but that's fine for our proof.)

We will show that $|N(B)| \geq |B|+5$ for each of 3 cases.

Case 1: $|B| < 216000$

Write down the $x$ coordinates of all elements of $B$ and all neighbours of $B$ (i.e. elements of $N(B)$). If the $x$ coordinates of the elements of $B$ are $x_1, x_2, \dots$, then the coordinates of the elements and their neighbours are $x_1, x_1-1, x_1+1, x_2, x_2-2, x_2+2, \dots$. We've just written down less than $3|B| < 3\cdot 216000$ unique $x$ coordinates. Since the side length of the torus is at least $4\cdot 216000$, we can find an $x$ coordinate that belongs to no elements of $B$ and no neighbour of $B$. This defines of plane of cells that all have that as their $x$ coordinate and are neither contained in $B$ nor neighbours of $B$.

Using the same method, find unused $y$ and $z$ coordinates, which also define planes that do not contain any elements of $B$ or neighbours of $B$. Remove these 3 planes from the torus, leaving behind a large block, without the wraparound structure of the torus.

Now construct the set $B$ in layers, starting from a single cell that has no other elements of $B$ below it. This single cell has $6$ white neighbours. $6 \geq 5+1$, so this will serve as our base case. Add the elements of $B$ one at a time, always making sure to complete 1 layer before moving on to the next. Each black cell we add to $B$ always adds at least 1 new white cell to $N(B)$, namely the cell just above it. So we always have $|N(B)| \geq 5+|B|$ at each step of the process.

Case 2: $216000 \leq |B| \leq |Y|-216000$

Divide the space up into $2\times 1\times 1$ blocks. (Do this so that the edges of the blocks are all lined up: We map $(x,y,z)$ to $(x, y, \lfloor z/2 \rfloor)$, and any two cells mapped to the same final coordinates belong to the same block.) We say a block is full if its black cell is an element of $B$, and empty otherwise. An empty cell may or may not contain a white neighbour of $B$, but all full cells contain one. We just need to show that there are at least 5 empty cells containing white neighbours of $B$. Since there are between 216000 and $|Y|-216000$ full blocks, the boundary between full blocks and empty blocks must contain at least 60 faces. (Faces are just the sides of the blocks. A face can have a surface area of 1 or 2. If we shrink the blocks by a factor of 2 in the $z$ direction, so that the blocks become cubes, we're claiming that any set of between 216000 and $|Y|-216000$ unit cubes in a torus of size at least $216000\times216000\times108000$ must have a surface area of at least 60. This really needs a proof of its own, but it seems likely enough to be true, so I'll leave it as an "exercise for the reader".)

Since each empty block that neighbours a full block can have at most 6 of these faces as neighbours, there must be at least 10 empty blocks with full blocks as neighbours. Any empty block with a full block to the north, south east, or west must have its white cell be a neighbour of $B$ (its white cell touches the black cells of all horizontally adjacent blocks). As for vertical neighbours: In some columns of blocks, the white cell in a block is below the black cell. In that case all empty blocks with a full block underneath will contain a white neighbour of $B$. In other columns, the white cell is above the black cell in each block, so all empty blocks with a full block above will contain a white neighbour of $B$. Note that in each column, there will be exactly as many empty blocks with full blocks above them as there are empty blocks with full blocks below them. (Because runs of empty and full blocks must alternate and the torus loops around.) Therefore, if there are $n$ empty blocks with full blocks as neighbours, at least $n/2$ empty blocks must contain white cells neighbouring $B$.

We now know that there are at least $10/2=5$ empty blocks containing white neighbours of $B$, which completes the proof for this case.

Case 3: $|Y|-216000 < |B|$

By the same argument as case 1, we can split the torus along 3 planes so that none of the planes contain any black cells not in $B$ or their neighbours. Then we start with the set of all black cells, and remove elements from it 1 at a time until we are left with $B$. As before, we proceed in layers. After removing 5 black cells, we have $|Y|$ neighbours, and $|Y|-5$ black cells. (We still have |Y| neighbours at this point because we started with all white cells being neighbours to the set of all black cells, and to get rid of a white cell as a neighbour, we'd need to remove all 6 black cells surrounding it, not just the 5 we have actually removed. Note that $|B| \leq |X| = |Y|-5$, so we always have to remove at least 5 black cells to get to $B$. So this will serve as our base case.

We continue removing cells 1 layer at a time. Each black cell we remove can only remove 1 neighbour when we take it away, namely the white cell directly below it, since to eliminate a white cell as a neighbour, we certainly must eliminate the black cell just above it first. And because we are proceeding in layers, the cell above will be the last of a white cell's neighbours to be removed. So the desired property is preserved with each cell we remove.

Q.E.D.

Commentary: This proof looks like it can be generalized to prove your conjecture in higher dimensions too.

$\endgroup$
4
  • $\begingroup$ Thanks for the proof! I have a few questions about the different cases. I think there might be a subtle issue in cases 1 and 3 of the proof: what if the cell above the topmost cell is the same as the cell below the bottommost cell? (To repair this, I think it suffices to replace the $4$ multiplier with $7$, so we can find two adjacent empty slabs.) $\endgroup$ – RavenclawPrefect Jan 17 at 22:13
  • 1
    $\begingroup$ In case 2, I don't follow why "a full block can have at most 6 of these faces as neighbours" - couldn't it be fully surrounded, with all $10$ faces of the block covered? $\endgroup$ – RavenclawPrefect Jan 17 at 22:14
  • 1
    $\begingroup$ Oh, sorry, that was very unclear. By face, I just mean the sides of the block, so it will have 4 faces with area 2 and 2 faces with area 1. I'll fix post to make this clear. $\endgroup$ – Ricky Tensor Jan 17 at 22:34
  • 1
    $\begingroup$ I don't think we need to replace 4 with 7. As long as the plane we're removing contains none of the blocks we're interested in, and it contains none of their neighbours, we should be okay to ignore it. $\endgroup$ – Ricky Tensor Jan 17 at 22:44

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.