Return to Question

Edit: fixed the values of $S_5$ and $S_7$, many thanks a lot to @RobPratt for noticing and reporting the errors!

Edit: fixed the values of $S_5$ and $S_7$, many thanks to @RobPratt for noticing and reporting the errors!

• We have $S_5 = 15$, with the unsurprising shape:

• We have $S_7 = 23$, the shape is similar to $n=5$ but with two "holes":

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

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

Acknowledgement: This question is by Thomas Colcombet and Antonio Casares.

• We have $S_5 = 13$, with the unsurprising shape:

• We have $S_7 = 24$, the shape is similar to $n=5$ but with a hole:

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

There are matching sequences for these terms in OEIS, but their definitions do not seem relevant... Edit: maybe https://oeis.org/A203567 https://www.sciencedirect.com/science/article/pii/S0012365X01003570 would be worth investigating.

Acknowledgement: This question is by Thomas Colcombet and Antonio Casares.

Edit: fixed the values of $S_5$ and $S_7$, many thanks a lot to @RobPratt for noticing and reporting the errors!

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...

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...

Acknowledgement: This question is by Thomas Colcombet and Antonio Casares.