Checkerboard Infection Variant

Question

There is an insidious virus (less contagious than C. Coli, but still dangerous) which plagues the squares of checkerboards. This virus spreads through social interaction: whenever the majority of a friend group becomes sick, the entire group becomes sick.

Specifically, any four squares which meet at a common vertex are mutual friends. Whenever three out of four squares in a friend group are sick, the remaining friend becomes sick the next day. This is the only way the infection can spread.

Initially, 14 squares of a checkerboard are infected. Is it possible for the infection to spread to the entire board?

The answer would be yes if 14 was replaced with 15, as shown below.

 

Hint:

See the solution to Checkerboard Infection. This puzzle also has a simple answer.

Answer 1

I know it is a checkerboard but this problem may need a bit of chess:

Say that a set of infected cells $C$ is rookable if a chess rook could travel from any square in $C$ to any other by a series of rook moves that all end on a cell in $C$. For example, two opposite corners of the board would not be rookable, but adding a third corner would be rookable. Clearly, if the whole board is infected, that forms a rookable set. Notice that if you run the infection backwards in time it will always still be a rookable set. Why? Well, removing one corner of a $2 \times 2$ still allows the rook to move around the other side of the $2 \times 2$ and access any row or column that it could before. Therefore, the initial infected cells formed a rookable set.

Notice also that the initial cells also must occupy every row and column. What is the smallest rookable set that also hits all the rows and columns? Well, imagine the rook starting somewhere and then having to hit the seven other columns and seven other rows. Any given move can enter a new row, or a new column, but not both. There for, there must be at least $7+7$ other initial cells besides the one the rook starts in, for a total of at least $15$.

Answer 2

The answer is

No, it is impossible to make it with less than 15.

Because

Imagine this problem was asked for 3x3, then you need to have at least 3 square filled next to each other at some place randomly at least to start to spread

and it will become like below

But with this,

you need to put another two square which should be anywhere except the middle. Otherwise there will be no solution.

Likewise

With 4x4, the same principle,

As shown below:

So

to spread it out everywhere, you just need to put two infected square not at the same square you had before every time the dimension increases.

As a result, We can conclude that to find it with any kind of dimension how many infected square you need, the formula will be as below:

$n_i=3+2(i-2)$

Note: This may not be the best way or the actual way to show it is

impossible with less than $n_8$ but by induction, i found this result.

Answer 3

In the original problem, there was the handy observation that

as the infection spreads, the perimeter of the infected cells does not increase.

That still holds true in this problem, but it is no longer enough to prove what we want. Fortunately, the same argument can be salvaged with a tweak:

Let P be the perimeter of the infected cells, and let N be the number of contiguous groups of infected cells. As the infection spreads, the quantity Q = P – 2N does not increase. This is because any merging of two groups must be accompanied by a decrease in perimeter by 2 (and when 3 groups merge, perimeter decreases by 4).

Furthermore, when $k$ cells are initially infected, the initial value of Q is at most $2k$. Indeed, suppose these initial infections form N contiguous groups with sizes $k_1,k_2,\dots,k_N$. Each group has a perimeter of at most $4k_i - 2(k_i-1) = 2k_i + 2$; each cell contributes 4 edges, but we must subtract out the $k_i-1$ overlaps. Adding these all up, the total perimeter P of all these groups satisfies $P\le 2k+2N$, implying $Q\le 2k$.

Therefore, when you initially infect 14 cells, Q is at most 28, but to infect the whole board, Q needs to end at 32 – 2 • 1 = 30.

Answer 4

To infect an $m \times n$ board, you need at least

$m+n-1$

infected cells to start with.

Proof:

Note: This proof is incorrect, and I don't think it can be easily fixed. Nevertheless I'm leaving this answer up because it shows the difficulty of this straightforward approach.

The proof is by induction.

Base case: It is obviously true that you need $1$ infected square to infect a $1 \times 1$ board. That may seem too trivial to work as a base case (though it is perfectly valid), so if you prefer you can use the fact that a $2\times2$ board needs at least $3$ infected squares to also infect the fourth.

Induction step: Suppose for the sake of induction the hypothesis holds for a particular board size $m \times n$. Add a new row or column to the side of that board. Every newly added square has only a single neighbour that is part of the old board, so if none of the added squares are infected, they can never have two infected neighbours and so will remain healthy. Therefore, to infect the newly added row/column, at least one of the new squares must start off sick. Furthermore, you cannot infect any of the new squares before its adjacent cell on the original board is infected. This means that the original board must be infected without any help from the squares in the new row/column (*). The original board needed at least $m+n-1$ infected squares, so the expanded board must therefore need at least one more, i.e. $(m+n-1)+1$ infected squares.
You can rewrite this as $(m+1)+n-1$ or $m+(n+1)-1$ depending on whether you added a row or a column to the board.

By induction the result follows: $m+n-1$ infected squares are needed on an $m \times n$ board.

The flaw at (*) is:

If you place two or more adjacent infected squares in the extra row/column, then the extra row/column helps infect the rest of the board, and maybe that allows the rest of the board to have fewer initially infected squares to compensate. The argument I used does not disprove the possibility of having an extra infected square in the extra column which then saves 2 or more initial infected squares from the rest of the board.