# Infected squares warmup: infect a 7x7 board with 21 squares

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.

 XOXOXOX
OXOOOXO
XOXOXOX
OOOXOOO
XOXOXOX
OXOOOXO
XOXOXOX


X is infected. O is not.

• Perfect! This is the unique solution. (As a bonus: how many do you think you need for 15x15?) Dec 5, 2022 at 3:46
• @AkivaWeinberger is it 85? I would guess it's the solution of this one from each corner, plus a single one in the center
– Ivo
Dec 5, 2022 at 13:37
• @Ivo Indeed it is. This generalizes to give the (unique!) optimal solution for board sizes one less than a power of two. Dec 5, 2022 at 14:40
• 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. Dec 5, 2022 at 23:20