Grid infection with diagonal adjacencies

Question

A community consists of 81 houses laid out in a 9 x 9 square grid. Every household is friends with their eight orthogonal and diagonal neighbors (except for the houses on the perimeter which have only three or five friends).

A subset of these houses believe in a certain baseless conspiracy theory. Now, the members of this community are generally reasonable people, but they are swayed by the opinions of their friends. Specifically, if a house has at least four friends who believe the conspiracy, then that house will succumb to the belief as well. The people who become fanatics can infect others with their delusion, so the conspiracy theory spreads like a virus.

What is the fewest number, $k$, of houses that need to initially believe the theory so it will spread to the whole community?

What is an arrangement of $k$ houses that will cause the theory to spread to all?

And finally, how can you be sure that when only $k-1$ initially houses believe the theory, that it will not spread to everyone?

For example, if the 28 blue houses are the initial whackos, then the conspiracy spreads to everyone after 5 steps.

                

Much like this classic puzzle, in addition to efficiently infecting the board, you will need to find some non-increasing quantity to prove that fewer infected houses are insufficient. Perimeter does not work this time...

Answer 1

The nonincreasing quantity $X$ to look at this time is

the amount of pairs of neighboring households of which only one is infected. (To define this number, assume that the considered grid is surrounded by a larger grid of virtual houses, all uninfected). This quantity cannot increase, since whenever a household becomes infected, it contributes to at least four such pairs beforehand, at most four such pairs afterwards, and the pairs not involving this household are unaffected.

Lower bound:

If the infection spreads to the entire grid, the final value of $X$ is equal to $104$ (the amount of neighboring pairs of virtual and non-virtual houses). Since $X$ is nonincreasing, $X$ has to be at least $104$ at the beginning. Let's try to achieve this number by infecting as few houses as possible. Since each house is part of at most $8$ neighboring pairs, we need to infect at the very least $13 = 104/8$ houses.

Considerations:

If this lower bound is reachable, all $13$ infected houses are necessarily nonadjacent, otherwise $X$ is initially less than $104$. If all initially infected houses are nonadjacent, this means that $X$ is initially exactly $104$ and can therefore never decrease during the course of infection. In this case the only possible way for any new house to be infected is by being initially adjacent to infected households on the four diagonal corners. After all such houses have become infected (let's call them Generation 1), only houses next to such houses may become newly infected in Generation 2. For this to happen, such a house must be orthogonally between two Generation 1 houses, which are produced by six Generation 0 houses. Unfortunately, in the area between those six houses it is easy to see that there must be a decrease in $X$ in Generation 4 at the latest, adjacent to one of the two considered Generation 1 houses. This contradicts the requirement that $X$ may not decrease.

Minimal example:

The initial infected population must therefore be at least $14$. Here is an example initial population of $14$ that eventually covers the entire grid:

Pattern code to verify in a CA simulator such as Golly:

x = 9, y = 9, rule = B45678/S012345678
o7bo$2bo$7bo2$2bobo2bo2$2bobo$6bo$obobo3bo!