Parando o quebra-cabeça do Coronavirus [fechado]

Question

Uma região quadrada $2020 \times 2020 \text{ km}^2$ dividido em $2020^2$células. Algumas células estão contaminadas por covid-19 . Todas as semanas, o vírus se espalha para as células que têm pelo menos$2$lado em comum com células contaminadas. Encontre o número máximo de células contaminadas de forma que, não importa onde estejam localizadas, a pandemia covid-19 não se espalhe para toda a região.

Meu amigo da escola me deu este problema (melhor dizer um quebra-cabeça) pode ser durante o período de bloqueio (julho-agosto), mas esqueci e ontem ele me perguntou se eu consegui resolver o problema ou não? E então a resposta foi obviamente não, embora eu tenha colocado um esforço suficiente atrás do problema naquela hora e depois do encontro de ontem e também hoje eu dei muito tempo, mas não consegui descobrir. Agradecimentos para sua atenção!

Answer 1

Reivindicação: Em um $n$ de $n$ grade, se houver menos de $n$ quadrados inicialmente infectados, então a infecção não se espalhará para toda a região.

Defina uma borda de um quadrado como uma borda de fronteira se um lado da borda estiver infectado, mas o outro lado não estiver infectado. (A região fora de toda$n$ de $n$ a grade é considerada sempre não infectada.)

Lema-chave: À medida que a infecção se propaga, o número de bordas da fronteira nunca pode aumentar.

Prova do lema-chave: sempre que a infecção se espalha para um novo quadrado, então pelo menos dois de seus vizinhos já estavam infectados, portanto, você perde pelo menos duas bordas da fronteira e ganha no máximo duas. Fim da prova.

Prova da reivindicação: suponha que a infecção se espalhe para toda a região. Naquela época, o número de bordas da fronteira é$4n$(toda a borda externa da placa). Pelo lema-chave, o número de arestas da fronteira inicial deve ser pelo menos$4n$. Portanto, deve ter havido pelo menos$n$quadrados iniciais infectados. Dito de outra forma, se houvesse menos de$n$ quadrados inicialmente infectados, então a infecção não se propagará para toda a região.

(A propósito, existem muitas configurações iniciais de tamanho $n$ que leva à infecção de todo o tabuleiro, não apenas das diagonais.)