Uciekają duże ameby

Dec 01 2020

Jako rozszerzenie pytania @WhatsUp tutaj , którego zasady są podane poniżej, z następującymi różnicami:

Na jednym z kwadratów żyje ameba (zaznaczona jako kółko na poniższych zdjęciach).

Na niektórych polach znajdują się ameby (zaznaczone na poniższym obrazku jako zielono-żółte).

Na siatce znajduje się region zwany „więzieniem” (pomalowany na szaro na poniższych zdjęciach).

Tutaj „więzienie” składa się ze wszystkich żółtych i zielonych kwadratów.

  1. Jeśli żółtawy, najniższy kwadrat jest pusty, czy ameby mogą uciec? Jak to jest trudne?

  2. W noc poprzedzającą rozpoczęcie ucieczki żółta cela zostaje wypełniona nowym więźniem ameby (wszystkie żółte i zielone są uważane za wypełnione), co mogą teraz zrobić?

Odniesienie

Istnieje nieskończona siatka kwadratów.

Na jednym z kwadratów żyje ameba (zaznaczona jako kółko na poniższych zdjęciach).

Ameby nie mogą się poruszać, ale mogą wykonywać swoją unikalną akcję: ameba może podzielić się na dwie ameby, które są identyczne z oryginalną, a każda z nich zajmie pole sąsiadujące (prostopadle) z pierwotnym kwadratem.

Ponieważ każdy kwadrat może pomieścić tylko jedną amebę, podział może nastąpić tylko wtedy, gdy ameba ma co najmniej dwa puste sąsiednie kwadraty (jeśli jest ich więcej niż dwa, może dowolnie wybierać, na które kwadraty się podzielić). Ponadto dwie ameby nie powinny rozdzielać się jednocześnie, aby nie doszło do konfliktu.

Na siatce znajduje się region zwany „więzieniem” (pomalowany na szaro na poniższych zdjęciach). Celem jest wypuszczenie ameb z więzienia, czyli osiągnięcie stanu, w którym żadna ameba nie przebywa w więzieniu.

Odpowiedzi

8 PaulPanzer Dec 01 2020 at 09:59

Odpowiedź na pytanie 2. Jak @Milo Brandt wskazuje w komentarzu do przywoływanego Q, istnieje następujący pół niezmiennik:

Umieść współrzędne całkowite na siatce, gdzie (0,0) jest środkiem krzyża. Waga kwadrat (n, m) wg$2^{-\lvert n \rvert - \lvert m \rvert}$. Wtedy można to łatwo zweryfikować

1. waga całej (nieskończonej) planszy wynosi 9 (por. Rysunek),
a
2. waga kwadratów zajmowanych przez amebę nigdy nie spada.

Jak waga całego krzyża $4\frac 1 2$ co równa się wadze jej (nieskończonego) dopełnienia, ameba nie może uciec w nieskończenie wielu ruchach.