Is every "even" polyomino with one hole tileable by dominoes?

Solution 1:

It is true! An even polyomino with one hole is tileable by dominoes.

The proof below has a few sketchy elements; a proof without those will be nice.

Proof. For this proof to work, we will manipulate the border (either the outside or inside border) to give a new polyomino with a hole, and we will consider regions where borders overlap also valid polyominoes, and they are even if the corners are black as with the regular definition. Here are some examples of such polyominoes (the outside border has been slightly displaced where it coincides with the inside border).

Here, tileable means tileable by dominoes.

1. A ring is a polyomino where each cell has exactly two borders. All rings are tileable.

2. A peak is a cell with exactly one neighbor. In an even polyomino, all peaks must be black (otherwise there are white corners). Also, all black peaks must be attached to a white cell with exactly two neighbors. Therefor, in an even polyomino, if we move the border to exclude the peak and it's neighboring cell, we are still left with an even polyomino.

An example of this manipulation:

3. A $2 \times 2$ square can be of two types. Type I has a black square in the top right, a Type II square has a black square in the top left. If a Type I square occurs in a corner of the polyomino, we can move the border to exclude it, and keep the polyomino even.

An example of this manipulation:

4. All convex corners of a even polyomino are one of these four types:

(This part is a bit sketchy; it requires considering many cases.)

5. If we perform the manipulations in 2 and 3 until we cannot, we are only left with the following types of convex corners:

6. A figure with only type 3 and 4 convex corners and one hole cannot contain a $2\times2$ subfigure.

Suppose there is such a square. Find the largest connected set of cells that contains this square such that each cell is part of a $2\times 2$ subfigure. This set of cells must have at least four convex corners (as do all rectilinear figures). For these corners to not be corners of the entire figure, each needs to be "covered" by a "strand" (the picture below shows a possibility.) These strands must either result in peaks, or they must connect in pairs. If they connect in pairs, there are two holes, and this is impossible. Therefor, there cannot be any $2\times 2$ subfigure.

In this^ image, there is a $2 \times 2$ square, contained in a $3\times 3$ square where each corner is covered by a white cell that stars the strand. In this example, the strands connect in pairs, leading to two holes.

7. We cannot have any X or T junctions in a figure with no $2\times2$ subfigures, no peaks, and one hole.

Suppose we have an X junction. Each of the four connectors must eventually lead to a peak, or pairs of them must join. In the latter case, we have two holes, which is impossible. Therefor there are no X junctions.

Suppose we have a T-junction. Each of the three connectors must either lead to a peak, or they must join other connectors. We can only join up if we have at least another T junction, in which case we will have at least have two holes, which is impossible. Therefor there are no T junctions.

8. This means we either have a ring, or a polyomino with no area (thus the inner and outer border coincide completely).

(This is also sketchy, and require cases to make sure we cannot have other possibilities.)

7. This procedure shows we can partition any even polyomino with one hole into a set with $dominoes$, $2\times2$ squares, and either a ring or empty polyomino. All the elements of this partition are tileable, and therefor, so is the whole figure.

Some remarks:

• The double border definition is necessary to deal with polyominoes such as this below. If we did not have that, removing a $2\times 2$ corner would not leave an even polyomino. (It would be nice to find a proof that does not require this trick.)

• An algorithm follows immediately from the border manipulations.