O O ctomino

The O O octomino can be generated by removing the central square from a 3 × 3 3\times3 board. The gray shape is an O O octomino: Find the minimum value of n n , such that there exist a 10 × 10 10\times10 board, with n n squares marked with a star \star , so that any O O octomino inside the board covers at least one star \star .


The answer is 12.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

The Icarus
Sep 8, 2018

Let's look at all possible centers of O O octominos.

They are all within the highlighted inner 8 × 8 8\times8 square, since an O O octomino's center (for obvious reasons) can't be on any of the pink colored unit squares.

Our goal is to add a minimum number of stars to specific unit squares in a way that in the end we can not put an O O octomino inside the 10 × 10 10\times10 square without it containing at least one star. In other words with each added star we eliminate possible O O octomino centers, until there aren't any remaining.

We can see that adding a star removes the possible centers around the star (since any O O octomino with a center around the star would cover the star):

The eliminated squares form an O O octomino, (meaning adding a star is equivalent to eliminating an O O octomino from the possible centers)

With all the information so far we can reframe our question in the following way:

How many O O octominos are needed to fully cover an 8 × 8 8\times8 board?

For each square with C in it (on the picture above), there is only one O O octomino that covers it, so we can be certain that these octominos must be used. This means 4 4 octominos so far.

Now to finish off the problem look at the yellow squares. It's clear that no O O octomino contains more than 2 2 of them.

Since there are 16 16 yellow squares, we know that we need at least 16 / 2 = 8 16/2 = 8 more O O octominos to fill the board, which means we need at least 12 in total, this also means we need at least 12 12 stars.

(In the middlle, you can actually place an octomino that covers 3 yellow squares, but that would mean we have 6*2+3 = 15 yellow squares covered, after placing 7 octominos, so again we would need at least 8).

We can show that 12 12 stars are enough. Here's an example:

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...