Побеги амебы больших размеров
В качестве расширения к вопросу @WhatsUp здесь , правила которого включены ниже, со следующими отличиями:
В одном из квадратов живет амеба (отмечена кружком на следующих рисунках).
В некоторых квадратах есть амебы (на следующем рисунке отмечены зеленым / желтым цветом).
В сетке есть область, которая называется «тюрьма» (на следующих рисунках окрашена в серый цвет).
Здесь «тюрьма» состоит из всех желтых и зеленых квадратов.
Если желтоватый крайний нижний квадрат не занят, смогут ли амебы сбежать? Насколько это сложно?
В ночь перед их побегом желтая камера заполнена новым заключенным-амебой (все желтые и зеленые считаются заполненными), что они могут делать теперь?
Справка
Есть бесконечная сетка квадратов.
В одном из квадратов живет амеба (отмечена кружком на следующих рисунках).
Амебы не могут двигаться, но они могут выполнять свое уникальное действие: амеба может разделиться на две амебы, которые идентичны исходной, и каждая будет занимать квадрат, который (ортогонально) примыкает к исходному квадрату.
Поскольку в каждом квадрате может разместиться только одна амеба, разделение может произойти только тогда, когда у амебы есть как минимум два пустых соседних квадрата (если их больше двух, то она может свободно выбирать, на какие квадраты разделить). Также две амебы не должны разделяться одновременно, чтобы не возникло конфликта.
В сетке есть область, которая называется «тюрьма» (на следующих рисунках окрашена в серый цвет). Цель состоит в том, чтобы позволить амебам сбежать из тюрьмы, то есть достичь статуса, при котором амебы не находятся в тюрьме.
Ответы
Ответ на Q2. Как отмечает @Milo Brandt в комментарии к указанному Q, существует следующий полуинвариант:
Поместите целые координаты в сетку, где (0,0) будет центром креста. Весовой квадрат (п, м) на$2^{-\lvert n \rvert - \lvert m \rvert}$. Тогда легко проверить, что
1. вес всей (бесконечной) доски равен 9 (см. Рисунок)
и
2. вес квадратов, занятых амебой, никогда не уменьшается.
Поскольку вес всего креста $4\frac 1 2$ равный весу своего (бесконечного) дополнения, амеба не может убежать за конечное число ходов.