OFFSET
0,3
COMMENTS
a(n) <= n*(n - 1)/2 for n > 1, by using a right triangular polyomino with the topmost cell moved to the bottom row.
##
###
####
######
Conjecture: a(9) = 26, a(10) = 31, a(11) = 37, and a(12) = 43.
From Peter Exley, Mar 08 2026: (Start)
a(9) = 26 confirmed by exact SAT solver using PySAT/CaDiCaL. The solver uses Boolean variables for cell occupancy on an n X n grid, auxiliary variables for each valid placement of each free n-omino, a cardinality constraint for the cell count, and iterative connectivity cuts. Shape constraints (contiguous rows, exactly one full row of width n, symmetry breaking) reduce the search space. Top-down search from upper bound proves optimality: SAT at k=26 (solution exists), UNSAT at k=25 (no solution with 25 cells). All previously known terms a(0)-a(8) matched by solver.
The upper bound a(n) <= n*(n-1)/2 holds for n >= 4 but not for n = 2 or n = 3. (End)
From Peter Exley, Mar 23 2026: (Start)
a(10) = 31, proved by CP-SAT (OR-Tools) with CEGAR connectivity. SAT at k=31 on 5 X 10 grid (54.9s). UNSAT at k=30 proved on all grids satisfying the spanning bound (H+W-1 <= 30, H >= 5, W >= 10), with I-piece symmetry break. Cross-validated using CaDiCaL.
The optimal container for n=10 has the "staircase" structure with row widths 10, 8, 6, 4, 3 on a 5 X 10 grid.
Conjecture: a(n) = floor((n+1)^2/4) + 1 for n >= 9. This matches the conjectured values a(11) = 37, a(12) = 43. The formula floor((n+1)^2/4) = A002620(n+1) counts cells in the "staircase" polyomino with row widths n, n-2, n-4, ..., which is optimal for n <= 6 and n = 8 but requires one extra cell for n >= 9.
Observation: a(n) >= floor((n+1)^2/4) for all n, with equality for n = 0..6 and n = 8. The staircase lower bound arises because the container must span at least ceil(n/2) rows (spanning bound theorem: |P| >= H + W - 1 for connected polyomino P) and n columns (to contain the straight n-omino).
All optimal containers for n = 3..10 have bounding box ceiling(n/2) X n. (End)
LINKS
Code Golf Stack Exchange, Smallest region of the plane that contains all free n-ominoes
Peter Exley, Solver code, data, and figures, GitHub.
EXAMPLE
For n = 5 the smallest polyomino that contains all 5-ominos is a polyomino with a(5) = 9 cells. One such 9-omino that works is
###
#####.
#
For example, the "L"-shaped, "+"-shaped, and "I"-shaped 5-ominoes fit in the following ways:
+---+---+---+
| * * * |
+---+ +---+
| * |
+---+---+---+ +---+
| * |
+---+
.
+---+---+---+
| * |
+---+ +---+
| * * * |
+---+---+---+ +---+
| * |
+---+
.
+---+---+---+
| |
+---+ +---+
| * * * * * |
+---+---+---+ +---+
| |
+---+
All other 5-ominoes can fit into this 9-omino too.
From Peter Exley, Mar 08 2026: (Start)
For n = 9, the minimal container has a(9) = 26 cells:
.
+---+---+---+---+---+---+---+---+---+
| * | * | * | * | * | * | * | * | * |
+---+---+---+---+---+---+---+---+---+
| * | * | * | * | * | * | * |
+---+---+---+---+---+---+---+
| * | * | * | * | * |
+---+---+---+---+---+
| * | * |
+---+---+---+
| * | * | * |
+---+---+---+
. (End)
From Peter Exley, Mar 23 2026: (Start)
For n = 10, the smallest container has a(10) = 31 cells on a 5 X 10 grid:
+---+---+---+---+---+---+---+---+---+---+
| * | * | * | * | * | * | * | * | * | * |
+---+---+---+---+---+---+---+---+---+---+
| * | * | * | * | * | * | * | * |
+---+---+---+---+---+---+---+---+
| * | * | * | * | * | * |
+---+---+---+---+---+---+
| * | * | * | * |
+---+---+---+---+
| * | * | * |
+---+---+---+
(End)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Peter Kagey, Sep 13 2019
EXTENSIONS
a(9) from Peter Exley, Mar 08 2026
a(10) from Peter Exley, Mar 23 2026
STATUS
approved