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:

ingr1

 

200 random configurations of 11 infected squares:

ingr2

200 random configurations of 13 infected squares:

ingr3

 

 

The statistics for fraction of area of infected cells:

iingrt

 

 

I look forward to the next puzzle…

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: