15
$\begingroup$

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$?

$\endgroup$
4
  • 1
    $\begingroup$ Perhaps one can restrict to convex polyominoes ? $\endgroup$ Dec 15 '20 at 9:34
  • 2
    $\begingroup$ I am assuming you meant this many polyominoes, right? oeis.org/A000104 $\endgroup$
    – Igor Pak
    Dec 15 '20 at 10:07
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 16 '20 at 3:18
  • $\begingroup$ "Convex" probably means that the intersection with any single (infinite) row or column is connected. $\endgroup$ Dec 16 '20 at 5:02
20
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Clever, and kind of funny! $\endgroup$ Dec 15 '20 at 11:34
  • $\begingroup$ The link at "here" seems broken. I get a 404 error when trying to go there ... $\endgroup$ Dec 15 '20 at 15:20
  • 3
    $\begingroup$ The link works for me. $\endgroup$ Dec 15 '20 at 17:14
15
$\begingroup$

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. enter image description here

$\endgroup$
12
$\begingroup$

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.

Polyominos

To go from $n$ to $n+4$ we can for instance add an additional column and increase the size of the "lump" by $2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.