# Tiling a rectangle with all simply connected polyominoes of fixed size

For which values of $$n$$ can we tile some rectangle with one copy of each free simply-connected $$n$$-omino (that is, each polyomino with $$n$$ squares that has no holes)?

It appears that it is possible for $$n=1$$ (trivial), $$n=2$$ (trivial), $$n=5$$ (see here), and $$n=7$$ (see here); and impossible for $$n=3$$ (trivial), $$n=4$$ (by a parity argument), and $$n=6$$ (by a parity argument). Is it known to be possible or impossible for any $$n\geq 8$$?

• Perhaps one can restrict to convex polyominoes ? – Per Alexandersson Dec 15 '20 at 9:34
• I am assuming you meant this many polyominoes, right? oeis.org/A000104 – Igor Pak Dec 15 '20 at 10:07
• Per: By convex polyominoes do you mean polyominoes whose minimal bounding box has the same perimeter? That would be an interesting case to restrict to--especially because it seems more hopeful that tilings would be possible. Igor: yes, that's the number of polyominoes I meant for each n. Of course, we can also ask the question in the case of one-sided polyominoes, or fixed polyominoes, in which case there will be more. – Ralph Morrison Dec 16 '20 at 3:18
• "Convex" probably means that the intersection with any single (infinite) row or column is connected. – Timothy Chow Dec 16 '20 at 5:02

A tiling is not possible for $$n=77$$. Consider the polyomino of order 77 here. The two $$4\times 19$$ missing rectangles can be filled with only one tile, so this tile must be repeated. It should be possible to use this method to show that no tiling is possible for $$n$$ sufficiently large.

• Clever, and kind of funny! – Yaakov Baruch Dec 15 '20 at 11:34
• The link at "here" seems broken. I get a 404 error when trying to go there ... – Jochen Voss Dec 15 '20 at 15:20
• The link works for me. – Richard Stanley Dec 15 '20 at 17:14

Continuing Richard Stanley's thought, here are two tiles that show that it is not possible for $$n=25$$ and $$n=20$$. The 25-omino is hostile (pun intended), in the sense that its complement does not admit any tiling by 25-ominoes. The $$20$$-omino has many siblings (by moving around the lump) that each require the same $$20$$-omino to fill their gap. Timothy Budd's construction for $$n =20$$ actually shows that it is impossible for $$n \geq 18$$. The following images show constructions for $$18 \leq n \leq 23$$. For each of them, the polyomino containing the red square must fill the cavity and there are not enough possible ways of attaching the remaining (at most $$2$$) squares to cater for all siblings. To go from $$n$$ to $$n+4$$ we can for instance add an additional column and increase the size of the "lump" by $$2$$.