Разделы 
Дополнительно
Задача по математике - 3364
2019-06-03 
В клетчатом прямоугольнике $m \times n$ каждая клетка может быть либо живой, либо мертвой. Каждую минуту одновременно все живые клетки умирают, а те мертвые, у которых было нечетное число живых соседей (по стороне), оживают. Укажите все пары ($m, n$), для которых найдется такая начальная расстановка живых и мертвых клеток, что жизнь в прямоугольнике будет существовать вечно (т. е. в каждый момент времени хотя бы одна клетка будет живой).
Решение:
Рассмотрим сначала случай прямоугольника $1 \times n$. При $n = 2$ и $n \geq 4$ вечно живые расстановки в прямоугольнике $1 \times n$ существуют: каждая из расстановок на рис. имеет период 2, т. е. каждую вторую минуту возвращается в исходное состояние. Четыре случая на рисунке соответствуют различным остаткам от деления числа $n$ на 4. Выделенная часть
является повторяющейся, т. е., чтобы получить картинку для большего $n$, достаточно увеличить количество таких частей (символ 
соответствует живой клетке, символ 
- мертвой).
Заметим, что при $n = 4k + 1$ имеется одна «вечно мертвая» клетка, а при остальных n каждая клетка последовательно оживает и умирает.
Пусть для некоторого $n$ в прямоугольнике $1 \times n$ существует вечно живая расстановка. Тогда такая расстановка существует и во всех прямоугольниках $m \times n$.
Строится она так: берем вечно живую расстановку в прямоугольнике $1 \times n$ и копируем ее во все строки прямоугольника $m \times n$. Тогда в нем столбцы будут эволюционировать так же, как клетки в соответствующем столбце прямоугольника $1 \times n$. Действительно, все клетки живого столбца умирают, как и соответствующая клетка прямоугольника $1 \times n$. У каждой клетки мертвого столбца соседи сверху и снизу мертвы, поэтому количество ее живых соседей равно количеству живых соседних столбцов, а значит, и количеству живых соседей у соответствующей клетки в «полоске» $1 \times n$. Значит, мертвый столбец оживает в том и только том случае, когда оживает соответствующая клетка в полоске.
Поскольку в полоске всегда остается хотя бы одна живая клетка, то в построенной расстановке для прямоугольника $m \times n$ тоже всегда остается хотя бы один живой столбец.
Мы можем считать, что $m \leq n$ (иначе повернем прямоугольник на $90^{\circ}$). Если $n \geq 4$ или $n = 2$, то, по доказанному, вечно живая расстановка найдется. Остается рассмотреть прямоугольники $1 \times 1, 1 \times 3$ и $3 \times 3$.
В прямоугольнике $3 \times 3$ также есть вечно жи¬вая расстановка (тоже периода 2), см. рис.
Осталось доказать, что в прямоугольниках $1 \times 1$ и $1 \times 3$ любая расстановка рано или поздно умрет. Случай $1 \times 1$ очевиден. Для случая $1 \times 3$ можно считать (возможно, начиная отсчет со второго шага), что первая клетка мертва. Тогда остается 3 варианта, в которых есть хотя бы одна живая клетка:
. Проверку этих вариантов мы оставляем читателю.
Ответ: Все пары чисел ($m, n$), кроме пар $(1, 1), (1, 3)$ и $(3, 1)$.
В клетчатом прямоугольнике $m \times n$ каждая клетка может быть либо живой, либо мертвой. Каждую минуту одновременно все живые клетки умирают, а те мертвые, у которых было нечетное число живых соседей (по стороне), оживают. Укажите все пары ($m, n$), для которых найдется такая начальная расстановка живых и мертвых клеток, что жизнь в прямоугольнике будет существовать вечно (т. е. в каждый момент времени хотя бы одна клетка будет живой).
Решение:
Рассмотрим сначала случай прямоугольника $1 \times n$. При $n = 2$ и $n \geq 4$ вечно живые расстановки в прямоугольнике $1 \times n$ существуют: каждая из расстановок на рис. имеет период 2, т. е. каждую вторую минуту возвращается в исходное состояние. Четыре случая на рисунке соответствуют различным остаткам от деления числа $n$ на 4. Выделенная часть
является повторяющейся, т. е., чтобы получить картинку для большего $n$, достаточно увеличить количество таких частей (символ соответствует живой клетке, символ - мертвой).
Заметим, что при $n = 4k + 1$ имеется одна «вечно мертвая» клетка, а при остальных n каждая клетка последовательно оживает и умирает.
Пусть для некоторого $n$ в прямоугольнике $1 \times n$ существует вечно живая расстановка. Тогда такая расстановка существует и во всех прямоугольниках $m \times n$.
Строится она так: берем вечно живую расстановку в прямоугольнике $1 \times n$ и копируем ее во все строки прямоугольника $m \times n$. Тогда в нем столбцы будут эволюционировать так же, как клетки в соответствующем столбце прямоугольника $1 \times n$. Действительно, все клетки живого столбца умирают, как и соответствующая клетка прямоугольника $1 \times n$. У каждой клетки мертвого столбца соседи сверху и снизу мертвы, поэтому количество ее живых соседей равно количеству живых соседних столбцов, а значит, и количеству живых соседей у соответствующей клетки в «полоске» $1 \times n$. Значит, мертвый столбец оживает в том и только том случае, когда оживает соответствующая клетка в полоске.
Поскольку в полоске всегда остается хотя бы одна живая клетка, то в построенной расстановке для прямоугольника $m \times n$ тоже всегда остается хотя бы один живой столбец.
Мы можем считать, что $m \leq n$ (иначе повернем прямоугольник на $90^{\circ}$). Если $n \geq 4$ или $n = 2$, то, по доказанному, вечно живая расстановка найдется. Остается рассмотреть прямоугольники $1 \times 1, 1 \times 3$ и $3 \times 3$.
В прямоугольнике $3 \times 3$ также есть вечно жи¬вая расстановка (тоже периода 2), см. рис.
Осталось доказать, что в прямоугольниках $1 \times 1$ и $1 \times 3$ любая расстановка рано или поздно умрет. Случай $1 \times 1$ очевиден. Для случая $1 \times 3$ можно считать (возможно, начиная отсчет со второго шага), что первая клетка мертва. Тогда остается 3 варианта, в которых есть хотя бы одна живая клетка:
. Проверку этих вариантов мы оставляем читателю.
Ответ: Все пары чисел ($m, n$), кроме пар $(1, 1), (1, 3)$ и $(3, 1)$.
