The Best Way to Choose Spaces for Infection

Question

Consider a 5x7 patch of 1x1 square units. I can choose any 3 of the units in the patch to be infected. After 1 day, an infected square will spread to all the squares adjacent to it (no diagonal spread). My question is: "What 3 squares should i pick such that the entire 5x7 patch is infected in the fastest time possible?" (you can answer in coordinates or as a matrix of x's and o's) Can I also have the proof as well? Thanks!

Answer 1

Suppose the patch is a grid from $(1,1)$ to $(5,7)$. Infecting $(3,1),(3,4),(3,7)$ initially ensures that all cells are infected after $3$ days.

To see why a $2$-day solution cannot exist, note that two cells separated by a giraffe or $(4,1)$ leap $$\begin{array}{ccccc} \circ&\circ&\circ&\circ&B\\ A&\circ&\circ&\circ&\circ\end{array}$$ cannot both be infected by one initial infection after $2$ days. Now consider the points $S=\{(1,1),(5,2),(1,6),(5,7)\}$, which are all at least a giraffe leap apart. Any single initial infection can infect at most one cell in $S$ after $2$ days, but there are $4$ cells in $S$ and only $3$ initial infections, so $S$ cannot be completely infected after $2$ days.