5
$\begingroup$

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

Good luck!

$\endgroup$
8
$\begingroup$

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...
enter image description here
...but now to block these four rectangles, we need to shade both of these two cells, and we can't do that.
enter image description here
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.
enter image description here
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).

enter image description here
The cell in row 3 column 3 must be shaded to avoid a 3x3.

enter image description here
Then, so must the first available cells in row and column 2...

enter image description here

And then, so must the first available cells in row and column 6, and the final cell is shaded in the bottom right corner.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Doh you beat me to it. I was struggling with keeping my <pre> text hidden lol! $\endgroup$ – JS1 Sep 25 at 5:54
  • $\begingroup$ That's a brilliant answer and plenty of details! $\endgroup$ – Dmitry Kamenetsky Sep 25 at 6:00
  • $\begingroup$ 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? $\endgroup$ – Darrel Hoffman Sep 25 at 14:10
  • $\begingroup$ @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. $\endgroup$ – Deusovi Sep 25 at 14:39
  • $\begingroup$ @Deusovi Ah, yeah I see it now. The aspect ratio of the ASCII art makes it look different. I was reading it as only the 2 corners were swapped and the middle portion was the same, but that was just a trick of the eyes. $\endgroup$ – Darrel Hoffman Sep 25 at 15:35
3
$\begingroup$

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.

$\endgroup$

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.