algorithm - Checkerboard Infection

There is a dangerous bacteria, Checkerichia Coli, (or C. Coli for short) which lives in the squares of checkerboards. Squares with this bacteria living in their digestive systems are said to have "C-sickness". Once a square has "C-sickness," it is stuck with it forever!

Excessive contact with C-sick squares will cause a square to become C-sick. Specifically, if a healthy square has at least two C-sick neighbors (orthognal, not diagonal), then that square becomes C-sick the next day.

For example, on the left we the photo of a see a partially infected checkerboard which was taken yesterday. On the right is a photo taken today.

• Warmup: A bioterrorist has 8 samples of the C. Coli strain, each of which can infect a single square. Which squares of an 8 by 8 chessboard can he infect so the infection will spread to the entire board?


• Challenge: If the terrorist has only 7 samples, can he still infect the whole board?

I didn't invent this puzzle, it is quite famous, but the puns are my own.

Answer

This is a pretty common puzzle.

Warm up Answer:

The 8 cells along the diagonal.

Advanced Answer Explanation:

No, it is impossible. However, we are instead looking at the number of edges rather than pieces. In an $n$ x $n$ checkerboard, the perimeter is $4n$, which means that the number of edges our infection must have when fully covering the board is $4n$. When initially starting with $n-1$ infections, the maximal perimeter of these infections is $4(n-1)$. Now, I am going to show that new infections at best, maintain the perimeter rather than enlarging it.

If the infections enclose an open cell (bordering all 4 sides), it clearly turns into further infection. However this case causes the overall perimeter of the infection to decrease by 4 because it loses 4 edges and gains 0 new ones.

If an infection borders a cell on 3 edges (which is rotationally equivalent), then it will infect the cell causing it lose these 3 edges and gain only 1 new edge, for a loss of 2 edges.

Finally is the case where a cell is bordered on 2 edges by other infected cells. This can either be top/bottom (which is rotationally equivalent to left/right), or the 2 infected cells are touching diagonally and so the healthy cell is bordered by both sides along a corner. However in either case, this healthy cell gets infected and creates 2 new edges, while losing 2 edges in the process remaining edge neutral. Thus this shows that edges can never be created, and it is therefore impossible to have less than $n$ initial infections.