What is the smallest number of cells you need to paint in an 8x8 grid, such that it contains no unpainted pentominoes? Can you find multiple solutions? Note that a pentomino is a set of 5 adjacent cells (horizontally or vertically).
Here is another solution with the same number of squares as @msh210's:
This looks very different to @msh210's, and has the nice property that
All blank regions are tetrominoes
Furthering on from that:
We might try a perimeter argument. Suppose there were 17 filled squares. Since all the blank regions are tetrominoes or smaller, the total perimeter of the blank regions is at least 2 times the number of blank squares. Also, the total perimeter is 4 times the number of filled squares plus all the border edges minus twice the number of border edges adjacent to a black square (at least six). Thus 94=47*2<=total perimeter<=4*17+32-2*6=88, a contradiction. So there are at least 18 filled squares.