Gorbachev A.N.

In a rectangular grid of size $m \times n$, each cell can be either alive or dead. Every minute, all living cells die simultaneously, and those dead cells that had an odd number of living neighbors (by side) come to life.

Indicate all pairs ($m, n$) for which there exists an initial arrangement of living and dead cells such that life in the rectangle will continue indefinitely (that is, at every moment in time, at least one cell will be alive)?
It is sufficient to consider the case $m \leq n$. Suppose for some $n$ there exists an eternal living arrangement in a $1 \times n$ rectangle. Then such an arrangement exists in all $m \times n$ rectangles: take the eternal living arrangement $1 \times n$ and copy it into all rows of the $m \times n$ rectangle. Indeed, for each cell in a dead column, the neighbors above and below are also dead, so the number of its live neighbors is equal to the number of live neighboring columns, and thus to the number of live neighbors of the corresponding cell in the $1 \times n$ rectangle. Since at least one live cell always remains in it, at least one live column always remains in the constructed $m \times n$ arrangement.

For $n=2$ and $n \geq 4$, eternal living arrangements $1 \times n$ exist: each of the following arrangements has a period of 2, meaning it returns to its initial state every second minute.

| $n=2$ | LiveDead $\leftrightarrow$ DeadLive |
| :--- | :--- |
| even $n \geq 4$ | LiveDeadDeadLiveLiveDeadDeadLive... $\leftrightarrow$ DeadLiveLiveDeadDeadLiveLiveDead... |
| odd $n \geq 4$ | LiveDeadDeadDeadLiveLiveDeadDeadLive... $\leftrightarrow$ DeadLiveDeadLiveDeadDeadLiveLiveDead... |

Moreover, there is an arrangement (also with a period of 2) in a $3 \times 3$ rectangle:

LiveLiveDead DeadDeadLive

DeadDeadDead $\leftrightarrow$ LiveDeadLive

DeadLiveLive LiveDeadDead

Thus, examples of eternal living arrangements have already been constructed in all rectangles except $1 \times 1$ and $1 \times 3$.

We will show that in rectangles $1 \times 1$ and $1 \times 3$, any arrangement will eventually die. The case $1 \times 1$ is obvious. For the case $1 \times 3$, we can assume (possibly starting the count from the second step) that the first cell is dead. Then there are 3 variants where there is at least one live cell. The evolution of the variant DeadLiveLive includes the variant DeadLiveDead: DeadLiveLive $\rightarrow$ LiveDeadDead $\rightarrow$ DeadLiveDead $\rightarrow$ LiveDeadLive $\rightarrow$ DeadDeadDead, and the variant DeadDeadLive is symmetric to the variant LiveDeadDead, which is also included in the example considered above.

## Answer

For all pairs of numbers $(m, n)$, except for the pairs $(1,1),(1,3)$ and $(3,1)$.

Send a comment