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).
Good luck!
Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this communityWhat 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).
Good luck!
Certainly 24 suffices: the c and f files and 3 and 6 ranks, minus their intersections. That leaves 2×2 and 1×1 squares.
But I don't know whether that's the least.
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.