# Paint 10 cells of a 10x10 grid

Can you paint 10 cells of a 10x10 grid such that the largest unpainted rectangle has area of 10 cells?

Here is a similar question for the 7x7 grid: Paint 7 cells of a 7x7 grid

Good luck!

• I will delete my incorrect solution and retry – JS1 Sep 25 '19 at 7:38
• Ok I came up with a new solution. – JS1 Sep 25 '19 at 7:46

I came up with:

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

Method:

1. The edges should not be painted because anywhere you would paint an edge, you could do the same or better by painting one in from the edge instead.

2. Basically, I tried to leave areas of 3x3 and 2x5 and only "block" areas when they threatened to become 2x6 or 3x4. It was a lot of trial and error.

• I think you've done it this time - great work! – Dmitry Kamenetsky Sep 25 '19 at 7:57

It seems to be possible to do this with nine painted cells.

• Very nice. The solution seems to be unique (up to rotation). – Jaap Scherphuis Sep 25 '19 at 11:27
• Very nice indeed. I didn't know it was possible. – Dmitry Kamenetsky Sep 25 '19 at 12:19

Using a computer I found there are quite a few solutions, so I decided to tighten the conditions a bit. If you also disallow unpainted rectangles of size $$2\times5$$ and $$5\times2$$, there seems to be only one solution left.

. . . . . . . . . .
. . . . X . . . X .
. X . . . . . . . .
. . . . . . X . . .
. . . X . . . . . .
. . . . . . . . X .
. X . . . X . . . .
. . . . . . . . . .
. . . X . . . X . .
. . . . . . . . . .

• If you are interested you can try fitting n mines on n by n grids that are larger. I have results for that – Dmitry Kamenetsky Sep 25 '19 at 12:20