Stoppen des Coronavirus-Puzzles [geschlossen]

Question

Eine quadratische Region $2020 \times 2020 \text{ km}^2$ eingeteilt in $2020^2$Zellen. Einige Zellen sind mit Covid-19 kontaminiert . Jede Woche verbreitete sich das Virus auf jene Zellen, die mindestens haben$2$Seite gemeinsam mit kontaminierten Zellen. Finden Sie die maximale Anzahl kontaminierter Zellen, sodass sich die Covid-19- Pandemie unabhängig von ihrem Standort nicht auf die gesamte Region ausbreitet.

Mein Schulfreund gab mir dieses Problem (besser gesagt ein Rätsel) während der Sperrzeit (Juli-August), aber ich habe es vergessen und gestern fragte er mich, ob ich das Problem lösen konnte oder nicht. Und dann war die Antwort offensichtlich nicht, obwohl ich mich damals ausreichend um das Problem gekümmert habe und nach dem Treffen gestern und auch heute viel Zeit gegeben habe, aber nicht in der Lage war, es herauszufinden. Danke für Ihre Aufmerksamkeit!

Answer 1

Behauptung: Auf einem $n$ durch $n$ Gitter, wenn es weniger als gibt $n$ Anfangs infizierte Quadrate, dann breitet sich die Infektion nicht auf die gesamte Region aus.

Definieren Sie eine Kante eines Quadrats als Grenzkante, wenn eine Seite der Kante infiziert ist, die andere Seite jedoch nicht infiziert ist. (Die Region außerhalb des gesamten$n$ durch $n$ Gitter gilt immer als nicht infiziert.)

Schlüssellemma: Während sich die Infektion ausbreitet, kann die Anzahl der Grenzkanten niemals zunehmen.

Beweis des Schlüssellemmas: Immer wenn sich die Infektion auf ein neues Quadrat ausbreitet, waren bereits mindestens zwei seiner Nachbarn infiziert, sodass Sie mindestens zwei Grenzkanten verlieren und höchstens zwei gewinnen. Ende des Beweises.

Anspruchsnachweis: Angenommen, die Infektion breitet sich auf die gesamte Region aus. Zu diesem Zeitpunkt beträgt die Anzahl der Grenzkanten$4n$(die gesamte Außenkante der Platine). Nach dem Schlüssel-Lemma muss die Anzahl der anfänglichen Grenzkanten mindestens betragen$4n$. Daher muss es zumindest gewesen sein$n$Anfangsquadrate infiziert. Anders ausgedrückt, wenn es weniger als gäbe$n$ Anfangs infizierte Quadrate, dann breitet sich die Infektion nicht auf die gesamte Region aus.

(Übrigens gibt es viele anfängliche Größenkonfigurationen $n$ das führt dazu, dass das gesamte Board infiziert wird, nicht nur die Diagonalen.)