Minimum Polyomino Cover

When I taught elementary school (1971-1981 or so) I had more time for “enrichment”, which for me meant excursions off the beaten curricular path, especially into the world of recreational math. As a result, my first publications were largely about geometric puzzles. (Those books were assembled a few years later. More info about my books.)

Anyway, one of those books was Polyomino Lessons (free download.) Polyominoes are the figures one can make by joining unit squares edge-to-edge. The five tetrominoes consist of four squares each, and are the raw ingredients for the game of Tetris:

UntitledImage

There are twelve pentominoes (five squares each), which are used in many, many puzzles of all types, some of which are included in my book Working with Pentominoes, which is available from Didax.

One question I asked my students (and myself) was: what is the minimum figure that can cover all the polyominoes of a given area? For example, this figure works as a minimum tetromino cover:

UntitledImage

The figure has area 6, and can accommodate any of the tetrominoes. No figure of area 5 would work.

What I love about this problem is that it is fun and interesting to students as well as teachers. Or, at any rate, I find it fun and interesting.

Recently, I read an excellent article by Patrick Honner about minimal covers. It is not related to polyominoes, but it did remind me of the minimal polyomino cover question. A little internet research yielded nothing, so I decided to see if I could figure something out beyond what I found in the 1970’s and 80’s. Back then, I concluded that the minimal covers from monominoes to hexominoes had areas 1, 2, 4, 6, 9, and 12, respectively. See if you can find those covers. If you tire of the problem, or to confirm your solutions, look at pages 17 and 47 of Polyomino Lessons. I also included the same exploration in Lab 4.7 of Geometry Labs(Answers on page 189.)

To go beyond that, I decided to find a minimum cover for heptominoes (7-ominoes.) This turned out to be more challenging than I thought. After several false starts, I ended up understanding the question a little better, and found a cover with area 17: 

UntitledImageI am confident that no square can be removed from this shape: every single one is needed by one or another heptomino.  I don’t think a shape with area 16 would work, but I don’t have a proof that such a shape does not exist. So at this point, I think the sequence is 1, 2, 4, 6, 9, 12, 17.

If you find a heptomino cover with area less than 17, please let me know! Likewise, if you can prove me right that 17 is optimal, and/or if you explore this question with a computer program.

Thanks in advance!

———————————————————————

Minutes after I posted the above, Benjamin Dickman replied on Twitter:

17 appears to be correct: oeis.org/A327094

Specifically, this was solved on code golf: codegolf.stackexchange.com/q/167484

In response to an earlier MSE question: math.stackexchange.com/q/2831675

Thanks, Benjamin! I had actually looked for the sequence on OEIS, but didn’t find it  because when I looked I thought it was 16 for heptominoes! I should have looked again once I convinced myself about 17… Or I should have done it the way Benjamin did it. He searched for:

“1, 2, 4, 6, 9, 12” polyomino

Still it was a fun exploration, and I got to share the question with math teachers! Certainly the problem up to pentominoes or hexominoes is suitable for a math club, math circle, or math team.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s