Can you paint 7 cells of a 7x7 grid such that the largest unpainted rectangle has area of 6 cells?
Since the largest unpainted rectangle has an area of 6,
there must be no empty row or column. So each row and column has exactly one painted cell.
consider the columns with the bottom four cells empty. (Let's call these "top-heavy columns".) No two of these can be adjacent, because that would make a 2x4 rectangle. Similarly, there can't be two adjacent "bottom-heavy" columns (with the top four cells empty).
The same applies to the rows, of course: no two "left-heavy" or "right-heavy" rows can be adjacent.
Time for some case bashing!
Let's say the central cell is shaded. Then the pattern of top- and bottom-heavy columns must give this...
...but now to block these four rectangles, we need to shade both of these two cells, and we can't do that.
So the central cell is unshaded.
Continuing from there,
let's arbitrarily say that the central column is bottom-heavy and the central row is right-heavy: that is, the first four cells of row 4 and column 4 are unshaded.
Then column 3 must be top-heavy, column 2 must be bottom-heavy, and column 1 must be top-heavy (and same for the rows 1-3).
The cell in row 3 column 3 must be shaded to avoid a 3x3.
Then, so must the first available cells in row and column 2...
And then, so must the first available cells in row and column 6, and the final cell is shaded in the bottom right corner.
I got this:
. . . . . . x . . x . . . . . . . . x . . . x . . . . . . . . . . x . . . . x . . . x . . . . . .
1. Each row and column must have 1 painted square because otherwise one unpainted row/column would be a 1x7 rectangle.
2. I started with two opposite corners because that seemed optimal for taking care of all four edges.
3. I tried placing the 2nd row square at (2,2) but it didn't work out because it left too much open space to its right. I moved it to (2,3).
4. From there it was a bit of trial and error to place the next 4 squares, but there weren't too many possibilities left.