mathematics - Paint 7 cells of a 7x7 grid

Can you paint 7 cells of a 7x7 grid such that the largest unpainted rectangle has area of 6 cells?

Good luck!

Answer

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.

So,

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.