The L-Game of Life

Question

The L- Game of Life is played in the following way:

On the infinite square grid, we initially make 2016 random cells alive and the rest dead. For every cell, we say that its environment consists of three cells: its upper neighbour, right neighbour, and the cell itself. At every step, the following happens to every cell:

1. If the majority of the cells in the environment of that cell are alive, then that cell becomes/stays alive in the next step.

2. If If the majority of the cells in the environment of that cell are dead, then that cell becomes/stays dead in the next step.

Does the board necessarily become free of life at some point? If yes, then at most how many steps it may take?

Source: All-Union Olympiad, 1973

Answer 1

Consider the diagonals going northwest/southeast. (I'll call these primary diagonals and the ones going the other way secondart diagonals.) Look at the top-right-most primary diagonal that contains any alive squares. None of those squares can survive, since they can have at most one cell alive in their neighborhood. This means that in each step with living cells, a primary diagonal that contains at least one cell will be fully killed off. (1)

Can we generate cells fast enough to keep them alive? To generate new live cells, we need two adjacent live cells on the same primary diagonal. There is a top-left-most cell in the top-right-most primary diagonal that can only be used to generate one new cell - that means not every cell can be used twice, so we will generate at most $n-1$ cells (where $n$ is the number of cells on "death row", so to speak).

We can't space them out, because then the diagonal below the space will die off too. Call a "group" a set of cells that, if left to fully generate without applying the death rule, would be connected horizontally, vertically, and primary diagonally. Splitting the live cells into two groups only makes them die faster, since both groups' topmost primary diagonal would die off. The optimal strategy to keep cells alive would be to have them all in one group.

Let an "oriented triangle of size $n$" be a set of cells (alive or dead) forming a shape like this:

X
XX
XXX
XXXX
XXXXX

There are $n$ cells along the bottom, left, and along the primary diagonal.

Since all the live cells are grouped together, there is an oriented triangle bounding them of size at most $2016$.

In each step, the biggest primary diagonal of the oriented triangle will die off (by (1)).

Therefore, in each step, the size of the oriented triangle containing the group will decrease by at least $1$.

Therefore all the cells will die in at most $2016$ steps. $\blacksquare$

Answer 2

The board

Necessarily becomes free of life by generation $2016$ (generation $0$ being the initial state)

Because

New cells are only bought to life by the presence of living cells both to their right and above, but those "supporting cells" both need living cells to their right or above to support them in turn.

Furthermore

If we had $2$ living cells (#) at generation $0$ the best we could do is

 . . . . .      . . . . .      . . . . .
 . . # . .      . . x . .      . . . . .
 . . . # .      . . # x .      . . x . .
 . . . . .      . . . . .      . . . . .
 . . . . .      . . . . .      . . . . .
     0              1              2

If we had, say, $5$ living cells we could try to use the other $3$ to spawn some to keep this situation happening at the last generation, but note that to spawn those $2$ we'd need a similar diagonal line of $3$ to the right and above.

So the best we can do with $n$ living cells is to have a single diagonal line like so:

 . . # . . . . . . .     . . x . . . . . . .     . . . . . . . . . .
 . . . # . . . . . .     . . # x . . . . . .     . . x . . . . . . .
 . . . . # . . . . .     . . . # x . . . . .     . . # x . . . . . .
 . . . . . # . . . .     . . . . # x . . . .     . . . # x . . . . .
 . . . . . . # . . .     . . . . . # x . . .     . . . . # x . . . .        ...
 . . . . . . . # . .     . . . . . . # x . .     . . . . . # x . . .
 . . . . . . . . # .     . . . . . . . # x .     . . . . . . # x . .
 . . . . . . . . . #     . . . . . . . . # x     . . . . . . . # x .
 . . . . . . . . . .     . . . . . . . . . .     . . . . . . . . . .
       0 (n)                   1 (n-1)                 2 (n-2)      

leaving a lifeless board at generation $n$

Answer 3

Yes, the board becomes free of life in at most 2016 steps.

Let's imagine the smallest rectangle on the grid that contains all live cells.
No square outside of this rectangle can ever become alive.
After one step, the top right corner of the rectangle will be dead, after 2 steps the 2 cells next to it will be dead too.
After n steps all cells that are closer than n cells from the top right corner are dead (the square becomes necessarily dead in diagonal lines).

Now instead of creating just one rectangle, we can create multiple smaller rectangles instead so that they cover all live cells and live cells sharing an edge are in the same rectangle (cells only sharing a corner can be in different ones).
That way the maximum size of an individual rectangle can be a x b, only if a + b <= 2016. Such a rectangle will be dead in at most 2016 steps.
That gives us an upper bound of 2016 steps.

A straight line of 2016 live cells will take exactly 2016 steps to die out so we have a lower bound of 2016 steps as well.

Answer 4

There have been many beautiful and enlightening answers to this question. For the sake of completeness, I (the OP) will include the solution I came across (note that it is not my solution).

We claim that $2016$ cells will die in at most $2016$ steps; or in general, $n$ cells will die in at most $n$ steps. We will prove this by (strong) induction.

The case $n=1$ is obvious, so assume that $k$ cells will be killed in at most $k$ steps for any $k<n$. Now consider $n$ alive cells. Consider the minimal rectangle covering these cells. The part of the rectangle without its bottom row contains at most $n-1$ alive cells (otherwise it wouldn't have been the minimal rectangle), and they are not affected by the bottom row. So they'll die off in $n-1$ steps. Similarly the part of the rectangle without the leftmost column will be dead in at most $n-1$ steps. So after $n-1$ steps, the only cell which may be alive is the one in the bottom-left corner, which will die at the next step; taking at most $n$ steps altogether. $\mathrm{QED}$.

Just a bit of history: This solution was found during the test (in 1973) by A. Gomilko, a tenth-grader at that time.