Arrêter l'énigme du coronavirus [fermé]
Une région carrée $2020 \times 2020 \text{ km}^2$ divisée en $2020^2$cellules. Certaines cellules sont contaminées par le covid-19 . Chaque semaine, le virus s'est propagé aux cellules qui ont au moins$2$côté commun avec les cellules contaminées. Trouvez le nombre maximum de cellules contaminées de telle sorte que peu importe où elles se trouvent, la pandémie de covid-19 ne se propage pas à toute la région.
Mon ami d'école m'a donné ce problème (mieux dire un casse-tête) peut-être pendant la période de verrouillage (juillet-août) mais je l'ai oublié et hier il m'a demandé si j'avais pu résoudre le problème ou non? Et puis la réponse était évidemment non, même si j'ai mis un effort suffisant derrière le problème cette fois-là et après la compétition d'hier et aussi aujourd'hui, j'ai donné beaucoup de temps mais je n'ai pas réussi à le comprendre. Merci de votre attention!
Réponses
Réclamation: sur un $n$ par $n$ grille, s'il y a moins de $n$ carrés initialement infectés, alors l'infection ne se propage pas à toute la région.
Définissez une arête d'un carré comme étant une arête de frontière si un côté de l'arête est infecté mais que l'autre côté n'est pas infecté. (La région en dehors de l'ensemble$n$ par $n$ la grille est considérée comme toujours non infectée.)
Lemme clé: Au fur et à mesure que l'infection se propage, le nombre de bords de frontière ne peut jamais augmenter.
Preuve du lemme clé: chaque fois que l'infection se propage à un nouveau carré, au moins deux de ses voisins étaient déjà infectés, par conséquent vous perdez au moins deux bords de frontière et en gagnez au plus deux. Fin de preuve.
Preuve de réclamation: Supposons que l'infection se propage à toute la région. A ce moment-là, le nombre d'arêtes frontières est$4n$(tout le bord extérieur de la planche). D'après le lemme clé, le nombre d'arêtes de frontière initiales doit être au moins$4n$. Par conséquent, il doit y avoir eu au moins$n$carrés initiaux infectés. En d'autres termes, s'il y avait moins de$n$ carrés initialement infectés, alors l'infection ne se propage pas dans toute la région.
(À propos, il existe de nombreuses configurations initiales de taille $n$ qui mènent à l'infection de la planche entière, pas seulement des diagonales.)