6
$\begingroup$

You can consider this a "warmup" to my other question about infected squares.

On a $7\times7$ square, some cells are infected; if a cell shares an edge with $3$ infected squares, it becomes infected. Show that we can infect the whole square with only $21$ initially infected cells.

$\endgroup$

1 Answer 1

7
$\begingroup$

 XOXOXOX
 OXOOOXO
 XOXOXOX
 OOOXOOO
 XOXOXOX
 OXOOOXO
 XOXOXOX

X is infected. O is not.

$\endgroup$
4
  • $\begingroup$ Perfect! This is the unique solution. (As a bonus: how many do you think you need for 15x15?) $\endgroup$ Dec 5, 2022 at 3:46
  • $\begingroup$ @AkivaWeinberger is it 85? I would guess it's the solution of this one from each corner, plus a single one in the center $\endgroup$
    – Ivo
    Dec 5, 2022 at 13:37
  • $\begingroup$ @Ivo Indeed it is. This generalizes to give the (unique!) optimal solution for board sizes one less than a power of two. $\endgroup$ Dec 5, 2022 at 14:40
  • $\begingroup$ Proof of optimality: The value (2*Infected area + perimeter) is a monovariant. (Stays same when an empty surrounded by three infecteds becomes infected; shrinks if an empty surrounded by four infecteds becomes infected.) Less than 21 infected has a smaller value than the target position. $\endgroup$ Dec 5, 2022 at 23: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.