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