0
$\begingroup$

In an infinite 2-D grid, $n^2$ cells are painted. What is the minimum number of unpainted cells that share a side with at least one painted cell?

The answer should be $4n$, occurring when the $n^2$ painted cells form a square with side length $n$; it is hard to imagine any better configuration. But what would a proof look like? One observation is that the answer must be at least $2n$, because each row/column that has at least one painted cell produces at least two unpainted adjacent cells, and there must be either at least $n$ rows or at least $n$ columns with painted cells. This can be improved to $2n+2$ by taking into account that the other "direction" also produces at least two such cells.

$\endgroup$

1 Answer 1

0
$\begingroup$

A diagonal square is more efficient then a horizontal one. For example, when $n=5$, this arrangement has a border of only $16<4n=20$.

    .
   .X.
  .XXX.
 .XXXXX. 
.XXXXXXX.
 .XXXXX.
  .XXX.
   .X.
    .

In general, a diagonal square with $k$ cells to a side (above, $k=4$) will consist of $k^2+(k-1)^2\approx 2k^2$ cells, and be adjacent to $4k$ adjacent cells, so choosing $k\approx n/\sqrt{2}$ results in an arrangement of $n^2$ cells with a border of $2\sqrt{2}n\approx 2.82n$, much better than $4n$.

Towards an optimality proof, call a shape $S$ efficient if among all other shapes which touch the same number of empty cells, $S$ has the largest area. Any shape whose border has a side of length $3$ or more is inefficient, since you can add cell to it without increasing the number of adjacent cells:

            .
...        .X.
XXX   ->   XXX

Therefore, the border of any efficient shape will have only side lengths of $1$ or $2$. With a little more work, you should be able to every efficient shape has a border which mostly consists of "staircases," possibly with the addition of two or four sides of length $2$, and these staircases must all have the same length.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .