A square region $2020 \times 2020 \text{ km}^2$ divided into $2020^2$ cells. Some cells are contaminated by covid-19. Every week the virus spread to those cell which have at least $2$ side in common with contaminated cells. Find the maximum number of contaminated cells such that no matter where they are located the covid-19 pandemic will not spread to the entire region.
My school friend gave me this problem( better to say a puzzle) may be during the lockdown period(July-August) but I forgot it and yesterday he asked me if I have been able to solve the problem or not? And then the answer was obviously not, although I put a sufficient effort behind the problem that time and after the meet yesterday and also today I gave a lots of time but unable to figure it out. Thanks for your attention!
Claim: On an $n$ by $n$ grid, if there are fewer than $n$ squares initially infected, then the infection will not spread to the entire region.
Define a edge of a square to be a frontier edge if one side of the edge is infected but the other side is uninfected. (The region outside the entire $n$ by $n$ grid is considered to always be uninfected.)
Key lemma: As the infection propagates, the number of frontier edges can never increase.
Proof of key lemma: Whenever the infection spreads to a new square, then at least two of its neighbors was already infected, hence you lose at least two frontier edges and gain at most two. End of proof.
Proof of claim: Suppose the infection spreads to the entire region. At that time, the number of frontier edges is $4n$ (the entire outer edge of the board). By the key lemma, the number of initial frontier edges must be at least $4n$. Therefore, there must have been at least $n$ initial squares infected. Put another way, if there were fewer than $n$ squares initially infected, then the infection will not propagate to the entire region.
(By the way, there are many initial configurations of size $n$ that lead to the whole board becoming infected, not just the diagonals.)