11
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I think it's right and quite nicely explained, but it sounds a bit non-rigorous (though I don't know exactly why). +1 for now; I'll wait for some more time and then add a check. Hope you don't mind. :-) $\endgroup$ – Ankoganit Jul 21 '16 at 9:28
  • 1
    $\begingroup$ @Ankoganit: Yeah, a few parts in here are non-rigorous - I'd be happy to clean any of them up if you have any specific objections. $\endgroup$ – Deusovi Jul 21 '16 at 9:29
  • $\begingroup$ What does "■" mean? $\endgroup$ – EKons Jul 21 '16 at 17:33
  • 1
    $\begingroup$ @ΈρικΚωνσταντόπουλος: en.wikipedia.org/wiki/Tombstone_(typography) (Also, what's wrong with Unicode?) $\endgroup$ – Deusovi Jul 21 '16 at 18:49
  • 3
    $\begingroup$ @ΈρικΚωνσταντόπουλος: It's fairly common. I see nothing wrong with having it in an answer. $\endgroup$ – Deusovi Jul 21 '16 at 18:53
5
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ You can also have a straight line to achieve the same thing $\endgroup$ – justhalf Jul 22 '16 at 5:42
  • 1
    $\begingroup$ @justhalf maybe I should have stated that too, but I jumped straight to "can we do better by spawning?". $\endgroup$ – Jonathan Allan Jul 22 '16 at 8:53
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice explanation. Only your usage of the term lower bound is flawed. A lower bound would be the minimum number of steps in which a board could be dead (which is 1 step if you put the living cells far enough apart). What you've done in your last sentence is stating a possible solution that exactly fits your correctly proven upper bound and is therefore an optimal solution. $\endgroup$ – The Dark Truth Jul 21 '16 at 8:48
  • 1
    $\begingroup$ Thanks. It was meant as a lower bound for the answer to the question (lower bound for the highest amount of necessary steps). Not as a lower bound for total amount of steps of any starting position. $\endgroup$ – Meiffert Jul 21 '16 at 8:52
  • 1
    $\begingroup$ What about 2016 cells along a diagonal that goes from NW to SE? Its rectangle has a+b bigger than 2016. $\endgroup$ – Deusovi Jul 21 '16 at 8:57
  • 1
    $\begingroup$ I don't understand. How do you prove that $2016$ steps cover the whole rectangle? It just covers $2016$ diagonals. $\endgroup$ – Ankoganit Jul 21 '16 at 8:59
  • 2
    $\begingroup$ @Deusovi Thanks for the input, there is indeed a hole in my proof, I'm confident that it could be fixed, but your proof uses similar idea, so I went ahead and upvoted it instead. :) $\endgroup$ – Meiffert Jul 21 '16 at 9:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh yeah, I could've used induction. That would've made it significantly easier. $\endgroup$ – Deusovi Jul 22 '16 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.