4
$\begingroup$

What is the minimum number of W pentominoes you need to cover every cell of an 8x8 grid? Pentominoes may overlap each other and sit outside the boundary of the grid. They can also be rotated in any way. An W pentomino looks like this:

enter image description here

Here is a similar puzzle with X pentominoes: Covering an 8x8 grid with X pentominoes

$\endgroup$
6
$\begingroup$

This is a solution with 15 pentominos.

enter image description here

Here is a proof that this is optimal.

Consider the top and bottom rows, left and right columns, which form the border of the area to cover. Most of the time a W-pentomino covers one or two cells of the border. There are only two ways for a piece to cover more than two border cells. These occur only at the corner of the 8x8 region, and are pictured below.

enter image description here

In both cases, only one extra border cell is covered over the usual two cells per piece. This can be done at most 4 times, once at each corner, so you need at least 12 pieces to cover he 28 border cells.

None of the border pieces can cover the 2x2 central area. To cover that central area you need at least two more pieces, which makes at least 14 all together.

Now let's show that 14 is not possible.

The 14 pieces have a total area of 70, only 6 cells more than the region we are covering. We need exactly 12 pieces along the border, so at all four corners we need to use one of the pictured corner configurations. However, they each waste at least 2 cells, more than the 6 we can afford. Therefore using only 14 pieces is impossible.

$\endgroup$
  • 1
    $\begingroup$ Nice! I'm thinking that's optimal. $\endgroup$ – Avi Oct 16 at 13:26
  • $\begingroup$ Very well done indeed, both the solution and the optimality proof! $\endgroup$ – Dmitry Kamenetsky Oct 17 at 2:45
1
$\begingroup$

Here is a solution with 16 pentominos:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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