Home > Uncategorized > More on Pus on a Grid

## More on Pus on a Grid

The solution and comments on the infected squares on a grid puzzle were enjoyable and instructive. The proof of minimality by Marco M:

The minimum number of initially infected squares is 12.

One way to see why this is the minimum is by considering the perimeter of the initial configuration. Think of the infections as a time process, at each tic of a clock, infected-to-be squares become infected, and so on.

The rules are such that, after each tic, the total perimeter is less or equal the total perimeter in the previous moment. Since the final perimeter is 48 (the whole square, considering each square to have a side of length 1 unit), the initial configuration must have a perimeter of 48 or more. Therefore we need, at least, 48/4 = 12 initially infected squares. One configuration that works with exactly 12 squares is by infecting one long diagonal.

I take solace in recognising the diagonal solution promptly (and it was clear that by induction if if an n condiguration solved an n^2  grid then n+1 solves an (n_1_^2 grid, as works for  grids of size,1,4,9 but did not prove minimality).

The following graphics are just some musings:

200 random configurations of 11 infected squares:

200 random configurations of 11 infected squares:

200 random configurations of 13 infected squares:

The statistics for fraction of area of infected cells:

I look forward to the next puzzle…