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

4 Answers 4

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$ Commented Dec 15, 2020 at 11:34
  • $\begingroup$ The link at "here" seems broken. I get a 404 error when trying to go there ... $\endgroup$ Commented Dec 15, 2020 at 15:20
  • 4
    $\begingroup$ The link works for me. $\endgroup$ Commented Dec 15, 2020 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$
2
$\begingroup$

I believe $n = 17$ is also impossible for a similar reason as $n \geq 18$. According to a computer search, there are $219$ hole-less 17-ominoes that create a $4\times 3$ rectangular cavity, but only $180$ 17-ominoes that can fill the cavity. Helpful image

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .