Can the $X$ pentomino and the $2\times 2$ square mutually tile any nontrivial cofinite region?

Question

It is easy to see that there is no nonempty finite region in the square grid that can be tiled by both the $X$ pentomino and the $2\times 2$ square: if we look at any cell of maximal $y$-coordinate, a $2\times2$ tiling would force one of its left or right neighbors to be in the region, but the $X$ tiling would force neither to be included.

On the other hand, there are infinite regions that both can tile. The entire plane is one example, but there are also regions like the following:

                                                             

Note that this region contains infinitely many cells and infinitely many missing cells. I am interested in whether the complement of a nonempty finite region can ever be tiled by both shapes. After trying several initial candidates, I suspect not, but I haven't found a proof yet.

Answer 1

Alright, I've found a proof via some fairly straightforward (if tedious) casework that any mutually tileable region has a set of holes that is unbounded in all cardinal directions.

For the sake of contradiction, consider a cell of maximal $y$-coordinate WLOG, and translate things so it is placed at $(0,0)$ (for ease of referring to nearby cells later). First, we observe that there cannot be an $X$ at $(0,2)$ (we refer to all $X$ pentominoes by the coordinates of their center):

In the above diagram, black dots indicate locations where we consider possible placements of $X$ pentominoes, and red dots locations whose consideration leads to a contradiction.

So the cell at $(0,1)$ must be part of an $X$ centered at $(-1,1)$ or $(1,1)$; without loss of generality, we assume the latter. Note also that there cannot be a hole at $(-1,0)$, since by the same logic as before it would require an $X$ at $(-2,1)$, which causes problems at $(-1,2)$ and $(0,2)$.

Suppose that there is an $X$ centered at $(1,-1)$:

If the dotted cell is part of an $X$ at $(-2,1)$, then consideration of $(-1,2)$ and $(0,2)$ leads to a contradiction. On the other hand, if it is part of an $X$ centered at $(-1,2)$, then there must be a hole at $(-2,0)$ (since no hole has a positive $y$-coordinate):

But then the cell at $(-1,0)$ can't be filled by a square. So there is not an $X$ centered at $(-1,-1)$, which means that $(-1,0)$ must be part of an $X$ centered at $(-2,0)$. This now forces several more $X$ locations (deductions left to the reader, it's not difficult):

Now, let's consider the cells at $(-1,-1),(0,-1),(1,-1),$ and $(2,-1)$. If there are holes on the left and right sides of a non-hole, the region can't be tilied by $2\times 2$s. If there are holes at $(-1,-1)$ and $(1,-1)$, then the placement of $2\times 2$s above them causes problems. Finally, no two adjacent dotted cells can be left open, or the $X$ pentominoes that must be centered below them will overlap. Subject to these restrictions, we can conclude that there are holes at $(0,-1)$ and $(1,-1)$, and no hole at $(-1,-1)$.

This leads us to:

But the red dotted cell cannot be filled by an $X$ pentomino, so it must be a hole. But then we run into a contradiction with $2\times2$ tiling: we can successively conclude that there must be squares whose SW corners are at $(1,0), (-1,1), (-2,-1) (-2,1),$ and $(-4,-2)$ - but this last square placement forces $(-3,-1)$ to not be a hole! This contradiction completes the proof.

Would love to see if anyone can simplify this argument! I'd be very interested in any more "natural" proofs of this statement.

Answer 2

1. If the complement if a finite region can be tiled with X polyominoes, then so can the region itself.

Essentially, up to translation/reflection there is a unique way for the X's to tile a half-infinite plane, and stitching four such half-planes together to get a tiling of the whole plane except for some finite region can also only be done in one way, resulting in the standard infinite tiling with some tiles taken out. This is a little handwavey, but quite obvious when you try it out. It should be possible to formalise it into a proof without too much trouble.

2. If you have any finite region tiled with X polyominoes, then the rest of the plane cannot be tiled with 2x2 squares.

If (x,y) is an X-cell in the finite region with the largest possible y-coordinate, the centre of the associated X is at (x,y-1). This means that (x-1,y-1) and (x+1,y-1) are also part of the X in that region, but the adjacent cells (x-1,y) and (x+1,y) are not. Those adjacent cells can only be filled by a 2x2 square in one way (since the cells below them are part of the X), and this makes (x,y+1) unfillable.

The result then follows.