Proof with brute-force procedure. Here I used fact that we for sure can cover with 16 pentominoes, so I tried to cover half with 8 or less and then see if two such half-covers cover the whole board. It takes about 15 seconds on my PC to get the answer.
const int kHalfUpperBound = 8;
const int kSide = 8;
I can prove that the answer is exactly
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:
As a first lower bound,
Therefore, we can ...
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 X-pentomino tiles the plane, so that tiling is a good way to start. There are two ways to cut an 8x8 region out of that tiling. If one of the 4 central squares of the 8x8 region has an X centred on it, you get this
or else you get this
The latter can be easily improved by replacing the ones at the edges to give this
A different way to get the same ...
Here's 2 fundamentally different solutions:
I suspect there are many because these are literally the first two things I tried as I was playing around and in both cases I was able to just shove the pieces in and get a solution. I did it in the numerical order shown.