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