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 '20 at 8:21
  • $\begingroup$ This does not seem to satisfy the requirement that "neighbors must share a side". $\endgroup$ – lmsteffan Mar 31 '20 at 8:31
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$ – Pradeep Suny Mar 31 '20 at 8:38
  • $\begingroup$ Just start with the $4$ diagonal squares, as Control stated in his comment. $\endgroup$ – saulspatz Mar 31 '20 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$ – Pradeep Suny Mar 31 '20 at 8:44
  • 1
    $\begingroup$ Certainly. Done. $\endgroup$ – saulspatz Mar 31 '20 at 8:48

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.