|
|
 |
Условие
В клетчатом прямоугольнике m×n каждая клетка может быть либо живой, либо мёртвой. Каждую минуту одновременно все живые клетки умирают, а те мёртвые, у которых было нечётное число живых соседей (по стороне), оживают.
Укажите все пары (m, n), для которых найдётся такая начальная расстановка живых и мёртвых клеток, что жизнь в прямоугольнике будет существовать вечно (то есть в каждый момент времени хотя бы одна клетка будет живой)?
Решение
Достаточно рассмотреть случай m ≤ n. Пусть для некоторого n в прямоугольнике 1×n существует вечно живая
расстановка. Тогда такая расстановка существует и во всех прямоугольниках
m×n: берём вечно живую расстановку 1×n и копируем её во все строки прямоугольника m×n. Действительно, у каждой клетки мёртвого столбца соседи сверху и снизу мертвы, поэтому количество её живых соседей равно количеству живых соседних столбцов, а значит, и количеству живых соседей у соответствующей клетки в прямоугольнике 1×n. Поскольку в нём всегда остаётся хотя бы одна живая клетка, то в построенной расстановке m×n всегда остаётся хотя бы один живой столбец.
При n = 2 и n ≥ 4 вечно живые расстановки 1×n существуют: каждая из нижеперечисленных расстановок имеет период 2, то есть каждую вторую минуту возвращается в исходное состояние.
ЖЖМ ММЖ
МММ ↔ ЖМЖ
МЖЖ ЖММ
Тем самым, во всех прямоугольниках, кроме 1×1 и 1×3, примеры вечно живых расстановок уже построены. Покажем, что в прямоугольниках 1×1 и 1×3 любая расстановка рано или поздно умрёт. Случай 1×1 очевиден. Для случая 1×3 можно считать (возможно, начиная отсчёт со второго шага), что первая клетка мертва. Тогда остаётся 3 варианта, в которых есть хотя бы одна живая клетка. Эволюция варианта МЖЖ включает в себя и МЖМ: МЖЖ → ЖММ → МЖМ → ЖМЖ → МММ, а вариант ММЖ симметричен варианту ЖММ, который также входит в рассмотренный выше пример.
Ответ
При всех парах чисел (m, n), кроме пар (1, 1), (1, 3) и (3, 1).
