# Covering an 8x8 grid with W pentominoes

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:

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

This is a solution with 15 pentominos.

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.

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.

• Nice! I'm thinking that's optimal.
– Avi
Commented Oct 16, 2019 at 13:26
• Very well done indeed, both the solution and the optimality proof! Commented Oct 17, 2019 at 2:45

Here is a solution with 16 pentominos: