# What is the minimum size of a region that can be tiled by every polyomino on up to $4$ cells?

I am interested in regions that can be tiled by all $$k$$-ominoes for each $$k\le n$$.

If we take $$n=3$$, it is obvious that the $$2\times 3$$ rectangle is the minimal region that can be tiled by the monomino, the domino, the $$L$$-tromino, and the $$1\times 3$$ rectangle.

If we take $$n=5$$, any such region must be unbounded: consider the interaction between the $$X$$ pentomino and the $$2\times 2$$ tetromino.

But at $$n=4$$ the question is rather interesting. There do exist solutions, like the following $$96$$-celled region formed from four $$2\times 12$$ rectangles:

However, I suspect this is not minimal; I am curious whether improvements can be made. As asked in this related question and proven here, there cannot be any simply-connected solutions.

What is the smallest such region known? This page has many related problems, but does not seem to tackle this one.

## 1 Answer

The following is still far from a complete answer but it narrows the possibilities.

We know that the area must be divisible by 12. The square is balanced*, so the region you are looking for must be balanced too. But since the T-tetronino is not balanced, we need an even number of them, so the area must be divisble by 8. So that leaves regions with areas 24, 48 and 72 as the only smaller possibilities.

(*Balanced means if we color the polyomino with the checkerboard coloring, it has the same number of black and white cells).

The smallest known figure tileable by each of tetrominoes has 32 cells, so we are left with 48 and 72 as the only possibilities.

(From the link in your question).

As you point out any figure tileable by both square and skew tetrominoes must have a hole.

Because of the square, the polyomino cannot be thin.

Also, because it's tileable by bars of length 3 and 4, it must have a side divisible by each (it can be the same or different sides) as shown in "On tileable orthogonal polygons" (Csizmada et al, 2004) (although here I'm not fully convinced by their proof; caveat emptor).

Because of the square, all "knobs" must be divisible by 2. (A knob is a side between two convex corners).

I don't think all this constrains the problem enough to exhaustively search by computer. However, if there is a smaller solution we can make a guess to find it faster: we can assume it has 90 degrees rotational symmetry.

We can then generate all regions formed by squares, and check if they are tileable in order by skew, bar tromino, T-tetromino, and the rest. This may be doable.

• The number of regions formed by $n$ square tetrominoes grows very quickly; I expect there will be at least hundreds of millions for $12$ squares, possibly billions. (Restricted to $90$ degree symmetry, though, I think would be manageable.) I was at least able to check all the regions with $6$ squares and confirm that none of them work for all the tetrominoes, so the $32$-celled example is in fact provably minimal for the tetrominoes. Commented Jun 11, 2021 at 4:22