# Holes in double-tileable polynominoes

This question was communicated to me by Evgeniy Romanov.

Consider a connected polyomino $$P$$ that can be completely tiled in two different ways: with disjoint $$2 \times 2$$ square tetraminoes, and with disjoint S-shaped tetraminoes (that we allow to reflect and rotate arbitrarily). Is it true that $$P$$ can not be simply connected, that is, $$P$$ must contain a "hole" in it?

The smallest non-trivial example of $$P$$ is a wedge of four $$2 \times 2$$ squares:

..AA.
BBAA.
BB.CC
.DDCC
.DD..


One can see that $$P$$ can be tiled by S-shapes as follows:

..AA.
BAAC.
BB.CC
.BDDC
.DD..


A brute-force shows that there is no counter-example fitting into an $$9 \times 9$$ square.

• Note that a torus can be completely tiled by both. Gerhard "Let's Redefine The Hole Notion" Paseman, 2018.12.07. Dec 8, 2018 at 3:15
• I suggest the great article A Pedestrian Approach to a Method of Conway by James Propp tandfonline.com/doi/abs/10.1080/0025570X.1997.11996571 It concerns these very two tiles and tile homotopy groups. Dec 8, 2018 at 3:29
• Source of the question is, AFAIK, Moscow Mathematical Festival-2018 (see comments to Problem 7.5 in olympiads.mccme.ru/matprazdnik/image/18/book.pdf [in Russian]) Dec 9, 2018 at 18:43

Now, let's change the coordinate system: rotate everything by $$45^\circ$$ and let integer lattice points correspond to the white cells and unit squares correspond to black cells. Now our white cycle became a polygon with integer coordinates. Let the length of cycle be $$2k$$. Every second edge on the cycle is from $$2\times 2$$-square covering. For every such edge there is corresponding black edge that connects 2 cells on which that edge lies. One of these cells lies inside the cycle, the other outside. So, we found $$k$$ cells inside our cycle. Let's call them special. Let the number of nonspecial cells inside our cycle be $$x$$ and the number of integer points inside the cycle be $$i$$. By Pick's formula we have: $$x + k = i + 2k/2 - 1 \Leftrightarrow i = x + 1$$. This means that either $$i$$ or $$x$$ is odd. If $$i$$ is odd, then we will not be able to find a perfect matching on those $$i$$ vertices. If $$x$$ is odd, we may match some of the cells with special cells. If we do that, it will mean that those cells lie on some black cycle that intersects our cycle. But we know that all such cycles have even number of vertices inside our cycle. So we will have some unmatched cell. In both cases we can't cover everything inside our cycle so there will be a hole for sure.
• Thanks Aydar, that's a great argument! If I'm not mistaken, it can be slightly simplified as follows: let's find any minimal cycle of length $2k$ in the symmetric difference as you've described. Since all of its edges are diagonal, the area $A$ inside of it is even. We can also assign a connected cycle of $2 \times 2$-squares, enclosing some region of cells that can be tiled by squares. By Pick's theorem, the number of cells in this region is $A - k + 1$ with further $k$ occupied by corners of the squares in the cycle, hence it must be odd, so one of the cells inside must be missing. Dec 11, 2018 at 23:33