5
$\begingroup$

Imagine a grid of size n x n of squares, where each square is colored either white or black. Black spreads as follows: At each step, all the white squares which have at least two black neighbors (where neighbors must share a side – they can not be diagonal neighbors) become black. What is the minimum number of black squares needed at the beginning for the grid to be completely black at some point? (This is from a puzzles Collection by Sophia Yakoubov, January 28, 2019, found in web.mit.edu website).

For $n = 3$, I found 3 and for $n = 4$, I found 7. I am trying to find a recursive relation but am not getting anywhere.

(This is not homework or anything; just challenging myself with nice puzzles!).

Any ideas?

Many thanks!

$\endgroup$
2
  • 2
    $\begingroup$ Can you not just color the diagonal black and after (n-1) steps everything is black? $\endgroup$
    – Control
    Mar 31, 2020 at 8:21
  • $\begingroup$ This does not seem to satisfy the requirement that "neighbors must share a side". $\endgroup$
    – lmsteffan
    Mar 31, 2020 at 8:31

1 Answer 1

3
$\begingroup$

I think I saw this one in "Coffee Time in Memphis". As Control's comment shows, $n$ squares are sufficient, since we can start with the diagonal. To see that $n$ squares are necessary, note that the perimeter of the black area never increases. When we color a square black, the two edges from its black neighbors become part of the interior, and are no longer on the perimeter. The other two edges of the newly-colored square square may become part of the perimeter, if they weren't already, but the perimeter can't increase.

If it is to be $4n$ at the end, then we need at least $n$ black squares to start with.

$\endgroup$
4
  • $\begingroup$ Dear saulspatz, so does this mean that for $n=4$ we need 4 squares?? How? $\endgroup$ Mar 31, 2020 at 8:38
  • $\begingroup$ Just start with the $4$ diagonal squares, as Control stated in his comment. $\endgroup$
    – saulspatz
    Mar 31, 2020 at 8:39
  • $\begingroup$ OK thank you. Can you explain a bit further what you wrote about the perimeter of the black area and $4n$? Thank you! $\endgroup$ Mar 31, 2020 at 8:44
  • 1
    $\begingroup$ Certainly. Done. $\endgroup$
    – saulspatz
    Mar 31, 2020 at 8:48

You must log in to answer this question.

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