24
$\begingroup$

All twelve pentominoes can be obtained by attaching a single unit square (edge to edge) to one of the squares that make up one (or more) of the following four tetrominoes:

“L” tetromino

“I” tetromino (four in a row)

“T” tetromino

“S” tetromino

a) What is the least number of pentominoes required so that all 35 hexominoes can be obtained by attaching (edge to edge) a single square to one of the squares that make up one (or more) of those chosen pentominoes?

b) What about the least number of hexominoes in order to obtain in a similar way all 108 heptominoes?

$\endgroup$
7
  • 1
    $\begingroup$ c) Try to get a recurrence relation for P(n+1) in terms of n, P(n), P(n-1) etc. $\endgroup$
    – smci
    Mar 7 at 4:01
  • $\begingroup$ Do you allow holes inside the polyominoes, or not? possible for n >= 7 $\endgroup$
    – smci
    Mar 7 at 4:03
  • 2
    $\begingroup$ @smci Presumably with holes, given the count of 108 heptominoes. $\endgroup$
    – PM 2Ring
    Mar 8 at 13:04
  • $\begingroup$ Ivan Hetman already wrote the program. It showed that in there are five generating pentomino subsets of size $8$ each. The program already started to check the hexomino case, so we expect to obtain the answer soon. $\endgroup$ Mar 11 at 20:41
  • $\begingroup$ @AlexRavsky: is that program (link?) a heuristic, not a recurrence relation in terms of A(n-1)? (hard to get a closed-form on when extending different families gives you duplicate shape). Also can't see one in the Formulas listed at the bottom of oeis.org/A000105 . $\endgroup$
    – smci
    Mar 11 at 22:53

2 Answers 2

6
+100
$\begingroup$

You can solve this set covering problem via integer linear programming as follows. Let $P$ be the set of larger polyominoes, let $Q$ be the set of smaller polyominoes, and for $p\in P$ let $Q_p \subset Q$ be the polyominoes that can construct $p$ by adding a cell. For $q\in Q$, let binary decision variable $x_q$ indicate whether $q$ is selected. The problem is to minimize $\sum_{q\in Q} x_q$ subject to linear constraints $$\sum_{q\in Q_p} x_q \ge 1 \quad \text{for all $p\in P$}$$ that enforce that each larger polyomino can be constructed from some selected $q$.

The minimum for part a is

8, with the following free pentominoes:

{(1,1),(2,1),(2,2),(2,3),(3,2)}
{(1,1),(2,1),(2,2),(3,2),(3,3)}
{(1,1),(2,1),(2,2),(3,2),(4,2)}
{(1,1),(2,1),(2,2),(3,1),(3,2)}
{(1,1),(1,2),(1,3),(2,2),(3,2)}
{(1,1),(1,2),(2,2),(3,2),(4,2)}
{(1,1),(1,2),(1,3),(2,1),(3,1)}
{(1,1),(2,1),(3,1),(4,1),(5,1)}

If I have constructed the sets correctly, the minimum for part b is

19, with the following free hexominoes:

{(1,5),(2,1),(2,2),(2,3),(2,4),(2,5)}
{(1,4),(1,5),(2,1),(2,2),(2,3),(2,4)}
{(1,1),(2,1),(2,3),(3,1),(3,2),(3,3)}
{(1,1),(2,1),(2,2),(2,3),(3,1),(3,3)}
{(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)}
{(1,1),(2,1),(2,2),(2,3),(3,3),(4,3)}
{(1,3),(2,2),(2,3),(3,1),(3,2),(4,1)}
{(1,3),(2,1),(2,2),(2,3),(3,3),(3,4)}
{(1,3),(2,2),(2,3),(2,4),(3,1),(3,2)}
{(1,2),(2,1),(2,2),(2,3),(2,4),(3,4)}
{(1,3),(2,3),(3,2),(3,3),(4,1),(4,2)}
{(1,3),(2,1),(2,2),(2,3),(3,3),(4,3)}
{(1,3),(2,1),(2,2),(2,3),(2,4),(2,5)}
{(1,3),(2,3),(3,3),(4,1),(4,2),(4,3)}
{(1,4),(2,1),(2,2),(2,3),(2,4),(3,4)}
{(1,2),(1,4),(2,1),(2,2),(2,3),(2,4)}
{(1,2),(2,1),(2,2),(2,3),(3,1),(3,2)}
{(1,1),(1,2),(1,3),(2,1),(2,3),(2,4)}
{(1,1),(2,1),(3,1),(4,1),(5,1),(6,1)}
$\endgroup$
39
$\begingroup$

Let us start by considering this hexomino:

It is clear that there is only one pentomino that can be extended to this:

And since we have to use that pentomino, we can tick off several hexominoes that can be made from it:

Now consider this set of hexominoes:

The only way to make these from a pentomino is to add one of its extremal squares, and in each case this gives the single pentomino it can be made from: W, N and L, respectively. We add these to our set and tick off each hexomino that can be made from them.

So far, so good. Sadly, no more hexominoes have a unique requirement. Let's label them with all the pentominoes they can be made from:

We can note that we need P or Y, P or U, F or Y and F or U, and that these four requirements can be simplified to (P and F) or (U and Y). Looking at each of these pairs, we see there is no single other pentomino that provides a complete covering, but there are several pairs of other pentominoes that do so. Thus our minimal covering set is 8, for example:

$\endgroup$
1
  • $\begingroup$ Nice answer! And thank you for not using spoilers. They are so annoying. $\endgroup$
    – JLee
    Mar 9 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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