mathematics - Covering an 8x8 grid with X pentominoes

What is the minimum number of X pentominoes you need to cover every cell of an 8x8 grid? Pentominoes may overlap each other and sit outside the boundary of the grid. An X pentomino looks like this:

Answer

I can prove that the answer is exactly

16 pentominoes

Several people, including Jaap Scherphuis, have shown that the square can be covered with this many pentominoes, so it only remains to show that at least this many pentominoes are needed. (A matching lower bound).

Let us start with the magic board given by A. Rex:

 13  7  6  8  8  6  7 13
  7  1  6  5  5  6  1  7
  6  6  9  3  3  9  6  6
  8  5  3  7  7  3  5  8
  8  5  3  7  7  3  5  8
  6  6  9  3  3  9  6  6
  7  1  6  5  5  6  1  7

 13  7  6  8  8  6  7 13 

As mentioned by A. Rex, any pentomino placed on this board will cover squares totaling at most 27 - exactly 27 if the center is on the board, and at most 13 if not. The numbers on the board total 400.

As a first lower bound,

at least 15 pentominoes are required, because 14 pentominoes can cover squares totaling at most 14*27 = 378, and hence not all of the squares.

However,

15 pentominoes can only cover squares totaling at most 15*27 = 405. This means that if 15 pentominoes cover the board, they cannot double-cover any square or squares totaling at least 6, and no pentomino can be centered off the board. If squares totaling at least 6 were double-covered, then the sum would be at least 406, which is impossible.

Therefore, we can try placing pentominoes

under the assumption that 15 can cover the board, and see what deductions we can make. Let's label the squares like a chess board, and start by looking at the square h1, in the bottom right corner.

To cover that square,

We must place a pentomino centered at either h1, g1 or h2. h2 and g1 are symmetrical, so we only need to consider one.

Let's start by

placing a pentomino centered at h1, and see where that gets us. We now must cover the square g2. We can't do so by placing a pentomino centered at g1, g2 or h2, because those would double-cover too much. Therefore, we must place a pentomino centered at either f2 or g3. These are symmetrical, so without loss of generality let's place a pentomino centered at f2. Next, we must cover the square h3. We can't do so by placing a pentomino centered at h2, h3 or g3, because those would double-cover too much. Therefore, we must place a pentomino centered at h4. Next, we must cover the square g3. We can't do so in any way without double-covering too much. Thus, if we start with a pentomino centered at h1, we will definitely double-cover too much to cover the square with only 15 pentominoes.

On the other hand, let's try starting by

placing a pentomino at g1. I'll abbreviate what follows, using "the only option" to mean "the only option that doesn't double cover squares totaling at least 6". We need to cover h2, the only option is to place a pentomino centered at h3. We need to cover f2, the only option is to place a pentomino centered at e2. We need to cover d1, the only option is to place a pentomino centered at c1. We need to cover a1, the only option is to place a pentomino centered at a2. We need to cover b3, the only option is to place a pentomino centered at b4. There is no option available to cover c3. Thus, there is no way to cover the square with 15 pentominoes starting with a pentomino centered at g1.

As a result, we have found that

It is impossible to cover the square with 15 X-pentominoes. Any such cover must cover h1, so it must include a pentomino centered at either h1 or g1, or equivalently h2. In either case, we would be required to double-cover a set of squares totaling at least 6, which means that the overall squares covered will total at least 406, which is impossible, since each pentomino covers at most 27, for a total of at most 405.

As a result, we have a matching lower and upper bound of

16 pentominoes.