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.
 A: Let's color all cells like a chessboard. Then every tetramino has exactly 2 white and 2 black cells. Let's connect cells of the same color covered by the same tetramino with an edge, these edges will form 2 perfect matchings. Let's take their symmetric difference. Obviously it's not empty. Let's take a cycle such that there is no other cycle completely inside it (but there can be some cycles intersecting it). Without loss of generality let's assume that this cycle is white. Then all cycles intersecting it are black. Notice that if there are two intersecting edges, then they correspond to some square tetramino. That means that if some black cycle intersects our cycle, then both intersecting edges are from the same matching. All the cycles are alternating, so we conclude that the number of vertices of that black cycle inside our cycle is even.
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.
