11
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Wow, that's a brilliant argument! $\endgroup$ – Deusovi Mar 21 '18 at 7:05
  • 1
    $\begingroup$ This is super surprising and beautiful, better than my solution! This is also way more general, working whenever the "friend groups" are all of the form {a,b} x {c,d}, instead of just {a,a+1} x {b,b+1}. Thank you for sharing! $\endgroup$ – Mike Earnest Mar 21 '18 at 7:30
  • $\begingroup$ @MikeEarnest I'm curious about what you had - would you mind posting your solution? $\endgroup$ – Deusovi Mar 21 '18 at 7:38
  • $\begingroup$ @Deusovi done :) $\endgroup$ – Mike Earnest Mar 21 '18 at 8:35
3
$\begingroup$

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

enter image description here

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:

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ How do you know it's impossible with fewer? You've given a solution with $2i-1$ squares for each $i\times i$ board, but you haven't shown that it's impossible with fewer squares. $\endgroup$ – Deusovi Mar 21 '18 at 0:07
  • $\begingroup$ (Put another way, you've given a nice strategy - but the point of the question is to show it can't be done with fewer, not that it can be done with this many. You've brushed off the meat of the question with the phrase "by induction, you can easily see".) $\endgroup$ – Deusovi Mar 21 '18 at 1:14
  • $\begingroup$ @Deusovi i agree :) $\endgroup$ – Oray Mar 21 '18 at 5:02
  • $\begingroup$ I think this is pretty close to a proof: basically the infection starts with three initial cells in a $2 \times 2$, and in order to spread to a new row or column, you need an additional initial cell (since otherwise it'll be quarantined to some $n \times m$ rectangle). So to go from $2 \times 2$ to $8 \times 8$ you need $6 + 6$ additional initial cells. However, to really turn this into a proof would require some work, especially since the infection can start in multiple places at once. I wonder if there is a simpler method ... $\endgroup$ – Tyler Seacrest Mar 21 '18 at 5:07
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "This means that the original board must be infected without any help from the squares in the new row/column." I don't see how that follows - why can't, say, adding 2 squares to the new row/column let us "close in on" the center somehow, letting us need less sick squares overall? Sure, getting the old board sick is sufficient, but I don't think you've quite shown it's necessary. $\endgroup$ – Deusovi Mar 21 '18 at 7:05
  • $\begingroup$ @Deusovi: You're right. If the new column/row contains just non-adjacent infected squares then it is true, but with two or more adjacent ones the argument fails. $\endgroup$ – Jaap Scherphuis Mar 21 '18 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.