Олимпиадная задача Горбачева А. Н. для 8-10 классов: жизнь в клетчатом прямоугольнике

  Достаточно рассмотреть случай  m ≤ n.  Пусть для некоторого n в прямоугольнике 1×n существует вечно живая расстановка. Тогда такая расстановка существует и во всех прямоугольниках m×n: берём вечно живую расстановку 1×n и копируем её во все строки прямоугольника m×n. Действительно, у каждой клетки мёртвого столбца соседи сверху и снизу мертвы, поэтому количество её живых соседей равно количеству живых соседних столбцов, а значит, и количеству живых соседей у соответствующей клетки в прямоугольнике 1×n. Поскольку в нём всегда остаётся хотя бы одна живая клетка, то в построенной расстановке m×n всегда остаётся хотя бы один живой столбец.

  При  n = 2  и  n ≥ 4  вечно живые расстановки 1×n существуют: каждая из нижеперечисленных расстановок имеет период 2, то есть каждую вторую минуту возвращается в исходное состояние.

  Кроме того, есть расстановка (также периода 2) в прямоугольнике 3×3:     ЖЖМ          ММЖ     МММ   ↔   ЖМЖ     МЖЖ          ЖММ   Тем самым, во всех прямоугольниках, кроме 1×1 и 1×3, примеры вечно живых расстановок уже построены.   Покажем, что в прямоугольниках 1×1 и 1×3 любая расстановка рано или поздно умрёт. Случай 1×1 очевиден. Для случая 1×3 можно считать (возможно, начиная отсчёт со второго шага), что первая клетка мертва. Тогда остаётся 3 варианта, в которых есть хотя бы одна живая клетка. Эволюция варианта МЖЖ включает в себя и МЖМ:   МЖЖ → ЖММ → МЖМ → ЖМЖ → МММ, а вариант ММЖ симметричен варианту ЖММ, который также входит в рассмотренный выше пример.

При всех парах чисел  (m, n),  кроме пар  (1, 1),  (1, 3)  и  (3, 1).