Zatrzymanie zagadki koronawirusa [zamknięte]
Region kwadratowy $2020 \times 2020 \text{ km}^2$ podzielone na $2020^2$komórki. Niektóre komórki są zanieczyszczone COVID-19 . Co tydzień wirus przenosił się do tych komórek, które mają co najmniej$2$strony z zanieczyszczonymi komórkami. Znajdź maksymalną liczbę skażonych komórek, tak aby bez względu na to, gdzie się znajdują, pandemia COVID-19 nie rozprzestrzeni się na cały region.
Mój kolega ze szkoły dał mi ten problem (lepiej powiedzieć zagadkę) może być w okresie blokady (lipiec-sierpień), ale zapomniałem o tym i wczoraj zapytał mnie, czy udało mi się rozwiązać problem, czy nie? I wtedy odpowiedź oczywiście nie brzmiała, chociaż włożyłem wystarczająco dużo wysiłku w ten problem, wtedy i po wczorajszym spotkaniu, a także dzisiaj, poświęciłem dużo czasu, ale nie mogłem tego rozgryźć. Dziękuję za uwagę!
Odpowiedzi
Roszczenie: na $n$ przez $n$ grid, jeśli jest mniej niż $n$ kwadraty początkowo zainfekowane, wtedy infekcja nie rozprzestrzeni się na cały region.
Zdefiniuj krawędź kwadratu jako krawędź graniczną, jeśli jedna strona krawędzi jest zainfekowana, ale druga strona jest niezainfekowana. (Region poza całością$n$ przez $n$ siatka jest zawsze uważana za niezainfekowaną).
Kluczowy lemat: w miarę rozprzestrzeniania się infekcji liczba granic nigdy nie może wzrosnąć.
Dowód na kluczowy lemat: za każdym razem, gdy infekcja rozprzestrzenia się na nowy kwadrat, co najmniej dwóch sąsiadów zostało już zainfekowanych, dlatego tracisz co najmniej dwie granice i zyskujesz co najwyżej dwie. Koniec dowodu.
Dowód roszczenia: załóżmy, że infekcja rozprzestrzeniła się na cały region. W tym czasie liczba granic wynosi$4n$(cała zewnętrzna krawędź deski). Zgodnie z lematem kluczowym liczba początkowych krawędzi granic musi wynosić co najmniej$4n$. Dlatego przynajmniej musiało być$n$zarażone początkowe kwadraty. Innymi słowy, gdyby było mniej niż$n$ kwadraty początkowo zainfekowane, infekcja nie rozprzestrzeni się na cały region.
(Nawiasem mówiąc, istnieje wiele początkowych konfiguracji rozmiaru $n$ co prowadzi do zakażenia całej planszy, a nie tylko przekątnych).