7
$\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

8
$\begingroup$

 XOXOXOX
 OXOOOXO
 XOXOXOX
 OOOXOOO
 XOXOXOX
 OXOOOXO
 XOXOXOX

X is infected. O is not.

$\endgroup$
4
  • 1
    $\begingroup$ Perfect! This is the unique solution. (As a bonus: how many do you think you need for 15x15?) $\endgroup$ Commented Dec 5, 2022 at 3:46
  • 1
    $\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
    Commented Dec 5, 2022 at 13:37
  • 1
    $\begingroup$ @Ivo Indeed it is. This generalizes to give the (unique!) optimal solution for board sizes one less than a power of two. $\endgroup$ Commented Dec 5, 2022 at 14:40
  • 1
    $\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$ Commented Dec 5, 2022 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.