Infekcja

Zostań na chwilę demonem zła. Chcesz zainfekować szachownicę o $|n2$ polach $|(n⩾ 2)$ , które będziemy nazywać komórkami. W każdym kolejnym kroku zdrowa komórka zostaje zainfekowana, gdy graniczy co najmniej dwoma bokami z zainfekowanymi sąsiadami. Ten proces nazywamy 2-infekcją. Zainfekowana komórka pozostaje chora na zawsze.

Jaki jest najmniejszy zbiór inicjujący 2-infekcję całej szachownicy? Musimy precyzyjnie odpowiedzieć na dwa pytania:

1.: Jaka minimalna liczba zainfekowanych komórek wystarczy, by 2-zainfekować całą szachownicę?
2.: Jak rozmieścić na szachownicy minimalny zbiór inicjujący 2-infekcję, by zainfekować wszystkie komórki?

Odpowiedź na pierwsze pytanie jest prosta. Przyjmijmy, że zainfekowane komórki są czarne. Zauważmy, że zainfekowany zbiór na rysunku 1 ma obwód 12. Po zainfekowaniu środkowych kwadratów (zacieniowanych na zielono, Rys. 2), obwód zainfekowanego zbioru jest równy $10 < 12.$ Z kolei na rysunku 3 zainfekowany zbiór ma obwód 8, który nie zmienia się po rozszerzeniu infekcji (Rys. 4).

Przykłady te sugerują, że rozprzestrzenianie 2-infekcji nie zwiększa obwodu zainfekowanej figury! Zatem jeśli mamy szachownicę o $2 n$ komórkach $|(n⩾ 2)$ i obwodzie $4n,$ to $(n − 1)$ zainfekowanych komórek nigdy nie wystarczy do 2-zainfekowania całej szachownicy (bo wtedy obwód zainfekowanego zbioru nie przekracza $4(n − 1) < 4n$ ).

To, że $n$ zainfekowanych komórek wystarczy do 2-zainfekowania szachownicy o $|n2$ komórkach, sprawdzamy empirycznie, rozmieszczając $n$ zainfekowanych komórek na przekątnej (Rys. 5). Inne "skuteczne" rozmieszczenie $|n = 4$ zainfekowanych komórek na szachownicy o $2 |4 = 16$ polach przedstawia rysunek 6 W obu tych konfiguracjach zainfekowana komórka występuje w każdym wierszu i w każdej kolumnie. Warunek ten jeszcze nie gwarantuje 2-zainfekowania całej szachownicy (Rys. 7). Oznacza to, że w procesie rozprzestrzeniania się 2-infekcji istotne jest rozmieszczenie komórek rozpoczynających 2-infekcję (różne od rozmieszczenia wzdłuż przekątnych). Koncentracja zainfekowanych komórek, jak i nadmierne ich rozproszenie nie gwarantują sukcesu. Im większa szachownica, tym oczywiście więcej możliwości "bezpiecznego" rozlokowania $n$ zainfekowanych komórek (Rys. 8, 9). Przy jednoczesnym spełnieniu warunku, że infekcja pojawia się w każdej kolumnie i w każdym wierszu, dają one możliwość zainfekowania wybranych obszarów, nie infekując całej szachownicy.

Problem komplikuje się, gdy rozważamy prostokątną tablicę $|n× m(n,$ jednostkowych kwadratów (komórek). Rozumując jak wyżej, łatwo stwierdzamy, że do 2-zainfekowania takiej tablicy potrzebujemy co najmniej $n+m ⌈-2-⌉$ zainfekowanych komórek (symbol $|⌈x ⌉$ oznacza najmniejszą liczbę całkowitą nie mniejszą od $x$ ). Jednak rozmieszczenie zbioru $⌈n+m⌉ 2$ zainfekowanych komórek, który 2-zainfekuje całą tablicę, nie jest tak oczywiste. Dla tablicy o wymiarach $5 × 10$ rozmieszczenie 8 zainfekowanych komórek, jak na rysunku 10, pozwoli 2-zainfekować całą tablicę.

Przykład ten pokazuje, jak 2-zainfekować tablicę $n × m$ : jeśli $n | ⩽m,$ to najpierw infekujemy kwadrat $|n× n,$ a pozostałe $|⌈m2-⌉$ infekcji umieszczamy w co drugiej (i ewentualnie ostatniej) kolumnie pozostałego prostokąta $|n× (m$

Zobaczmy, jak może przebiegać rozwój infekcji, gdy w każdym kroku zdrowa komórka (kwadrat jednostkowy) zostaje zainfekowana, jeśli graniczy co najmniej trzema bokami z zainfekowanymi sąsiadami. Taki proces infekcji nazywamy 3-infekcją.

Przyjmijmy, że proces 3-infekcji szachownicy o $n2$ komórkach $|(n⩾ 3)$ rozpoczyna $|k < n2$ komórek, które jedna po drugiej zarażają wszystkie $|t = n2 −k$ komórek. Do zainfekowania komórki dochodzi, gdy wystąpi sytuacja z rysunku 11 Ogólnie, gdy zdrowa komórka zostaje zainfekowana, to w 3-infekcji obwód zainfekowanego obszaru maleje co najmniej o 2.

Zatem skoro początkowo zainfekowany obszar ma obwód co najwyżej $4k,$ to po procesie zainfekowania wszystkich $|t$ komórek obwód zainfekowanego zbioru spełnia nierówność

2 4k− 2t = 4k − 2(n −k) ⩾ 4n,

skąd

n2 +-2n k⩾ ⌈ 3 ⌉.

Gdy $n ⩾ 3$ jest liczbą parzystą, to możemy wskazać dokładniejsze (większe) ograniczenie dolne liczby zainfekowanych komórek, które przy właściwym rozmieszczeniu gwarantują 3-zainfekowanie szachownicy o $|n2$ komórkach. Zauważmy, że w tym przypadku 4 komórki w rogach szachownicy muszą być zainfekowane, bo te komórki mają tylko dwóch sąsiadów graniczących bokami. Z podobnych względów do krawędzi szachownicy nie mogą przylegać dwie sąsiadujące zdrowe komórki (nigdy nie zostałyby one zarażone). W tej sytuacji, ze względu na parzystość $n,$ co najmniej 4 zainfekowane komórki przylegają do zainfekowanych rogów szachownicy. Wobec tego początkowy obwód zainfekowanych pól wynosi co najwyżej $|4k− 8.$ Zatem w tym przypadku mamy nowe oszacowanie

(4k− 8) −2t = 4k− 8 − 2(n2− k) ⩾ 4n,

skąd

(n+ 1)2 k⩾ ⌈ -------⌉ + 1. 3

Wzory te pokazują, że dla dużych zbiorów skuteczną 2-infekcję wywołuje relatywnie mały zbiór, ale skuteczną 3-infekcję może wywołać tylko duży zbiór, stanowiący co najmniej trzecią część wszystkich komórek. Odporność na infekcje jest istotna! Oto przykłady pokazujące, że

5 zainfekowanych komórek 3-infekuje szachownicę o 9 komórkach (Rys. 12),
10 zainfekowanych komórek 3-infekuje szachownicę o 16 komórkach (Rys. 13),
12 zainfekowanych komórek 3-infekuje szachownicę o 25 komórkach (Rys. 14),
18 zainfekowanych komórek 3-infekuje szachownicę o 36 komórkach (Rys. 15).

Na większej szachownicy problem rozmieszczenia minimalnej liczby komórek, które 3-infekują całą szachownicę, staje się trudniejszy.

Łatwo sprawdzić, że przedstawione na powyższych przykładach konfiguracje realizują wyprowadzone przez nas wcześniej ograniczenie dolne na liczbę początkowo zainfekowanych komórek. Niestety nie wiemy, czy to ograniczenie jest zawsze optymalne?

Dyskusja nad tego typu problemami może być kontynuowana dla innych podziałów płaszczyzny wielokątami bądź może być rozciągnięta na wielowymiarowe prostopadłościany, np. na zbiory jednostkowych sześcianów wypełniających sześcian $|n3,$ gdzie $n ⩾ 3.$

Jeśli komórka w postaci jednostkowego sześcianu zostaje zainfekowana, gdy graniczy co najmniej dwiema ścianami z zainfekowanymi sąsiadami, to do zainfekowania całego sześcianu $33$ wystarczą 4 zarażone komórki, 6 chorych komórek może zainfekować cały sześcian $3 4 .$ Ogólnie, jeśli $n ⩾ 3,$ to $|n+ ⌊n-⌋ 2$ chorych komórek może zainfekować cały sześcian $n3$ ( $⌊x ⌋$ oznacza największą liczbę całkowitą nie większą od $|x$ ). Oczywiście, gdy trafnie rozmieścimy zainfekowane komórki...