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 log²n) 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

n	Rook Connected	King Connected	Bishop Connected	Arbitrary
1	1	1	1	1
2	3	3	2	5
3	6	11	3	14
4	9	16	6	26
5	11	22	6	39
6	22	31	8
7	22	30	9
8	23	35	10
9	29	39	14
10	29	43	17
11	35		17
12	36		20
13	36

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

n	Square Lattice 4 neighbors	Hex Lattice 6 neighbors	Triangle Lattice 3 neighbors	Triangle Lattice 12 neighbors	Corner Connected 12 neighbors
1	1	1	1	1	1
2	1	3	1	2	6
3	2	5	1	4	9
4	3	10	1	4	9
5	4	14	2	4	15
6	5	15	2	8	18
7	6	18	2	8	26
8	7	22	3	8
9	8	24	3	8
10	9	26	4	12
11	11	29	4	16
12	13		5	19
13	14		5	19
14	16		6	22
15			6	22
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.

n	Rook Connected	King Connected	Bishop Connected	Arbitrary
1	1	1	1	1
2	3	3	2	5
3	6	11	3	14
4	9	16	6	26
5	11	22	6	39
6	22	31	8
7	22	30	9
8	23	35	10
9	29	39	14
10	29	43	17
11	35		17
12	36		20
13	36

n	Square Lattice 4 neighbors	Hex Lattice 6 neighbors	Triangle Lattice 3 neighbors	Triangle Lattice 12 neighbors	Corner Connected 12 neighbors
1	1	1	1	1	1
2	1	3	1	2	6
3	2	5	1	4	9
4	3	10	1	4	9
5	4	14	2	4	15
6	5	15	2	8	18
7	6	18	2	8	26
8	7	22	3	8
9	8	24	3	8
10	9	26	4	12
11	11	29	4	16
12	13		5	19
13	14		5	19
14	16		6	22
15			6	22
16			7

n	Rook Connected	King Connected	Bishop Connected	Arbitrary
1	1	1	1	1
2	3	3	2	5
3	6	11	3	14
4	9	16	6	26
5	11	22	6	39
6	22	31	8
7	22	30	9
8	23	35	10
9	29	39	14
10	29	43	17
11	35		17
12	36		20
13	36

n	Square Lattice 4 neighbors	Hex Lattice 6 neighbors	Triangle Lattice 3 neighbors	Triangle Lattice 12 neighbors	Corner Connected 12 neighbors
1	1	1	1	1	1
2	1	3	1	2	6
3	2	5	1	4	9
4	3	10	1	4	9
5	4	14	2	4	15
6	5	15	2	8	18
7	6	18	2	8	26
8	7	22	3	8
9	8	24	3	8
10	9	26	4	12
11	11	29	4	16
12	13		5	19
13	14		5	19
14	16		6	22
15			6	22
16			7

n	Rook Connected	King Connected	Bishop Connected	Arbitrary
1	1	1	1	1
2	3	3	2	5
3	6	11	3	14
4	9	16	6	26
5	11	22	6	39
6	22	31	8
7	22	30	9
8	23	35	10
9	29	39	14
10	29	43	17
11	35		17
12	36		20
13	36

n	Square Lattice 4 neighbors	Hex Lattice 6 neighbors	Triangle Lattice 3 neighbors	Triangle Lattice 12 neighbors	Corner Connected 12 neighbors
1	1	1	1	1	1
2	1	3	1	2	6
3	2	5	1	4	9
4	3	10	1	4	9
5	4	14	2	4	15
6	5	15	2	8	18
7	6	18	2	8	26
8	7	22	3	8
9	8	24	3	8
10	9	26	4	12
11	11	29	4	16
12	13		5	19
13	14		5	19
14	16		6	22
15			6	22
16			7