i. Each cell's neighborhood is the 8 horizontally, vertically, and diagonally adjacent cells.

ii. We start at time 1 with a finite collection of cells in state 1, with all other cells in state 0.

iii. 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.

iv. 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?

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.

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:

Square Lattice | Hex Lattice | Triangle Lattice | Triangle Lattice | Corner Connected | |
---|---|---|---|---|---|

n | 4 neighbors | 6 neighbors | 3 neighbors | 12 neighbors | 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.