Problem of the Month (September 2002)

Consider the cellular automaton on the square lattice with the following rules:

1. Each cell's neighborhood is the 8 horizontally, vertically, and diagonally adjacent cells.
2. We start at time 1 with a finite collection of cells in state 1, with all other cells in state 0.
3. At time n, if a cell is in state 0, and the sum of the states of its neighborhood add to n, that cell switches to state n.
4. If at time n, no cell switches to state n, the growth stops.

Since cells stay in state 0 or change to a higher state only once, this is a growth model, and we can illustrate the growth with a picture of the states of the cells after they no longer change. For example, here are two such pictures, each starting from 3 connected cells in state 1:

The largest state ever reached by any cell is called the lifetime of the original pattern. The patterns above both have lifetime 6.

Can you find some small patterns with some large lifetimes? What is the largest lifetime of any pattern starting with at most n cells in state 1? What if we require the n starting cells to be connected? Can you prove that arbitrarily large lifetimes occur? What if we require the starting pattern to be connected? Can you find a pattern with infinite lifetime? Is finding the lifetime of a pattern an NP-complete problem?


ANSWERS

Boris Bukh defined L(n) to be the longest lifetime of a pattern starting from n cells in state 1. He also defined l(n) to be the longest lifetime of a pattern starting from n connected cells in state 1. Through a long argument, he proves the amazing upper bounds L(n) = O(n log2n) and l(n) = O(n log n log log n). He does not know whether l(n) is unbounded.

Berend Jan van der Zwaag and Joseph DeVincentis found an infinite collection of patterns which generate arbitrarily long lifetimes. This shows that L(n) ≥ 3n–3:

Philippe Fondanaiche found a similar construction. Boris Bukh and John Hoffman found a sequence of patterns which show L(n) ≥ 3n–2:

Then Berend Jan van der Zwaag improved this pattern to show L(n) ≥ (7n–5)/2:

Brendan Owen found the small configurations with the longest lifetimes. The connected configurations were the result of a complete search, but the disconnected configurations might be improved upon.

The Configurations Starting from n Cells with the Largest Lifetimes
nRook
Connected
King
Connected
Bishop
Connected
Arbitrary
11111
23325
3611314
4916626
51122639
622318 
722309 
8233510 
9293914 
10294317 
1135 17 
1236 20 
1336   

Clinton Weaver, Claudio Baiocchi, Philippe Fondanaiche, and Joseph DeVincentis also sent some solutions, not all of which were optimal.

Brendan Owen also found the small configurations with the longest lifetimes if the rules were changed to fewer neighbors or a different latice:

Configurations with the Largest Lifetimes with Different Rules
nSquare Lattice
4 neighbors
Hex Lattice
6 neighbors
Triangle Lattice
3 neighbors
Triangle Lattice
12 neighbors
Corner Connected
12 neighbors
111111
213126
325149
4310149
54142415
65152818
76182826
872238 
982438 
10926412 
111129416 
1213 519 
1314 519 
1416 622 
15  622 
16  7  


If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 9/12/02.