7
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ I will delete my incorrect solution and retry $\endgroup$ – JS1 Sep 25 at 7:38
  • 1
    $\begingroup$ Ok I came up with a new solution. $\endgroup$ – JS1 Sep 25 at 7:46
8
$\begingroup$

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.

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

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

enter image description here

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

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 . .
. . . . . . . . . .

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.