Skip to main content
1 of 5
a3nm
  • 431
  • 3
  • 9

What is the smallest size of a shape in which all fixed $n$-polyominos can fit?

Let $n$ be an integer and consider all fixed $n$-polyominos, i.e., without rotation or reflection. I am interested in finding a shape in which all polyominos can embed. (It is OK if multiple polyominos overlap.)

For instance, for $n=3$, the fixed 3-polyominos are:

###  #..  ##.  ##.  #..  .#.
...  #..  #..  .#.  ##.  ##.
...  #..  ...  ...  ...  ...

and these polyominos all embed in the following shape with 5 cells, which is the best possible:

.#.
###
.#.

More generally, a suitable shape for arbitrary $n$ is the $n \times n$ square (with $n^2$ cells) and a naive lower bound would be $2n-1$ cells (necessary to embed the horizontal and vertical line $n$-polyomino).

I define an integer sequence $S_n$ to be the minimal number of cells of a shape in which all $n$-polyominos embed, and I am interested in understanding this sequence. In particular, specific questions are:

  • Can we always find an optimal shape that fits into an $n \times n$ square? (this seems intuitively reasonable but I do not know how to prove it)
  • Can we prove that, asymptotically, $S_n = \Theta(n^2)$? (the challenge is to show an $\Omega(n^2)$ lower bound -- maybe this is already possible by simply looking at a subset of the polyominos, but I couldn't see how to do it)

More generally, has this sequence already been studied?

To understand what happens here, I was able to compute by bruteforce computer search the first values of $S_n$, making the assumption that optimal shapes always fit in an $n$ by $n$ square (first point above) -- these values may turn out not to be optimal if this assumption is wrong:

  • We have $S_1 = 1$, $S_2 = 3$ (easily), and $S_3 = 5$ (see above)
  • We have $S_4=9$ with a surprising shape:
..#.
.##.
####
.##.
  • We have $S_5 = 15$, with the unsurprising shape:
..#..
.###.
#####
.###.
..#..
  • We have $S_6 = 18$ with a surprising shape:
..##..
..##..
######
#####.
..##..
..#...
  • We have $S_7 = 23$, the shape is similar to $n=5$ but with two "holes":
...#...
..###..
.#.#.#.
#######
.#####.
..###..
...#...
  • I do not know $S_8$

There are matching sequences for these terms in OEIS, but their definitions do not seem relevant...

a3nm
  • 431
  • 3
  • 9