# Paint 7 cells of a 7x7 grid

Can you paint 7 cells of a 7x7 grid such that the largest unpainted rectangle with grid-aligned sides has an area of 6 cells?

Good luck!

• There is a skew rectangle with area more than 6 in the intended solution. Jan 31 at 2:48
• A very elegant puzzle! Jan 31 at 15:52

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.

• Doh you beat me to it. I was struggling with keeping my <pre> text hidden lol!
– JS1
Sep 25, 2019 at 5:54
• That's a brilliant answer and plenty of details! Sep 25, 2019 at 6:00
• Follow up question: How many possible arrangements are there that meet the criteria (excluding rotations and mirroring)? The two answers given are not the same, but both are valid. So we know there are at least 2. Are they the only ones? Sep 25, 2019 at 14:10
• @DarrelHoffman The answers are the same - JS1's is just mine rotated 90 degrees clockwise. And because the only assumption I made was the one that broke symmetry, the solution is unique up to rotation/reflection.
– Deusovi
Sep 25, 2019 at 14:39
• It is probably cheating, (and useless), but I did a quick computer search. This is the only solution, modulo a rotation. Sep 30, 2019 at 20:56

I got this:

. . . . . . x
. . x . . . .
. . . . x . .
. x . . . . .
. . . . . x .
. . . x . . .
x . . . . . .

Method:

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.