So I was thinking about this and there's the beginnings of a proof. Think about the perimeters of the shapes. The tetronimos have perimeters of length 10 (or less in the case of the square). The outside has 32. There's at least two edges touching at each side, so that removes 8 edges at least, so there's a maximum of 96 free edges. Any additional edge that's touching will reduce that number by 2.
Now count the spaces in between. We intuitively think that these will generally be trionimos, but they could be smaller. They will never share an edge with each other (obviously) just with the outsides and the tetronimos. There are 32 spaces. If they were all dominoes then you'd have a perimeter of 16 dominoes times 6 edges, or a total of at least 96. Since that equals the 96 from the first paragraph we know that if there is just one additional overlap (between the edges of two tetronimos or a tetronimo and the side of the board) then it cannot be done with just dominoes.
The best case for these is that there are 10 trionimos, and 1 domino, for a total of 86. So if we can demonstrate that there have to be more overlaps than the basic 2 per side, we'll get closer. You'd just need 5 additional overlaps to get you there. I think you can get 1 in each corner (at least in certain cases), which would mean you'd need just one more shared edge to be required to blow the solution up.
At the very least this should help people looking for a solution!
Edit to take the proof further:
To summarise where we got to:
- We have a minimum perimeter of 86 from the empty spaces.
- We have a maximum perimeter available of 96 from the tetronimos and outer edges
- Any additional overlaps (apart from the 2 squares per side) reduces the maximum perimeter available by 2.
- Meaning that if we can find at least 6 overlaps, we prove that 8 tetronimos is insufficient.
(Aside: The numbers for an 8x7 square are 76 minimum and 88 maximum, which may explain why this is possible, where the 8x8 is (probably) not.)
I will now show that each corner adds at least one additional overlap, essentially getting us 4 of the 6 overlaps we need to prove our case.
Suppose we have three blanks in the corner, as shown in yellow. Then the squares marked X1 and Y1 must be part of two separate tetronimos (call them X and Y respectively). If the squares marked X2 or Y2 were part of their respective tetronimos (X & Y), then we'd have an additional overlap (between tetronimo and the edge).
Hence suppose that X2 and Y2 are not part of their tetronimos. Then X3 and Y3 are. But then the square marked * must be part of either X or Y, and either way X and Y share an edge.
More or less exactly the same argument, but with a different picture. In this case the * can be X, Y or some third tetronimo (which would give us two overlaps). - Thanks to @Sleafar for point out that this proof is wrong. It can however still be proved, I believe, by considering more elaborate cases.
For case 2, we need to extend the scenario to both corners and look for 2 overlaps. See the above diagram. From the basic blank squares three in the top-left corner, you can build up other parts of the board that must be this way or add an additional overlap. Specifically X extends along the bottom of the blank squares, and Y comes out at Y3. There must be three more blanks in the top right, and Z must be at Z1 and Z2. We know we're going to get an extra overlap where Y and Z join, so we need to find one more.
Scenario 1 has Z3, which leads to Y4 and Z4. The two squares below Z1 must be blank, as well as the one below Z4. This creates 3 blanks together, which must be surrounded by tetronimos. Specifically the square A1 must be a tetronimo. That leaves the square with an *, which is a single blank square. A single blank square will push up the minimum by 2, which is equivalent.
Scenario 2 has Y4. The square below Y3 must be blank, as well as the square below the blank below Y1 (otherwise we'd have a single blank again). That means the square marked with an * must be a tetronimo (either Z or a new tetronimo). Either way, there's an additional overlap.
Easy peasy. X2 has to be part of X, so you get an extra overlap between X and the edge of the board.
Finally, in the case of the a domino on the side, it either reduces to a similar situation to Case 2 above, or it's surrounded by a tetronimo, shown as X1,X2,X3,X4 in the diagram (call this tetronimo X).
In this scenario, consider the yellow squares marked B2. If any of them are part of another tetronimo, then you have an extra overlap. So suppose they are all blank. Then the square Y1 must be part of a new tetronimo, which is an additional overlap.
Other cases are kind of trivial, but for the sake of completeness:
- If the corner is a single blank square this is effectively the same, because two blank singletons adds to the minimum perimeter by 2.
- If the corner has a tetronimo in it, then one of the adjacent edges must have the same tetronimo, and so you have an additional edge.
Where we are
So each corner definitely creates at least one additional overlap. This brings the maximum available perimeter down to 88, which is almost the minimum perimeter (86).
If we can find two more overlaps then we prove that the 8x8 board cannot be covered by 8 tetronimos.
I suspect that this can be done by considering a few more cases. This may be susceptible to a computer search for all possible cases along one edge.
We can also make the following conclusions, based on the above. A 8 piece solutions would:
- Not use any of the straight tetronimo, because the four squares running along-side the tetronimo must have another tetronimo in it, which would be an additional overlap not covered above.
- Not use the square tetronimo, because this would reduce the maximum available because of its lower perimeter (8 vs 10 for the other tetronimos).
- Have 10 trionimos and 1 domino as the blank spaces.
The first of these is particularly interesting. It eliminates the case where the 8 squares touching the edge of the board are 8 separate tetronimos, because the middle four squares could only have one covered by a straight line tetronimo.
These restrictions certainly seem to support the thesis that 9 is the minimum, but we're not quite there! - Thanks, @Sleafar