2
$\begingroup$

Fix a positive integer $k$.

Given an infinite grid of squares, each of them is assigned a nonnegative integer value. Furthermore, only finitely many of these values are nonzero. Call this state Generation $0$. In Generation $n+1$, a cell is given the value:

  • $0$ if the sum of its four neighbors in Generation $n$ was not divisible by $k$;
  • $\frac{1}{k}*\text{(The sum of its four neighbors in Generation n)}$ otherwise.

The question is this: Does there exist an initial configuration such that the grid does not eventually become all zeroes?

For $k\ge 4$, the answer is easily no; one can prove this using the sum of all the grid's numbers as a monovariant. For $k\le 2$, the answer is easily yes; for $k=2$ consider two diagonally adjacent "$1$"s. But what about $k=3$??

A similar question can be posed for a hexagonal grid (considering six instead of four neighbors). Here, it is yes for $k\ge 6$ and no for $k\le 3$. But what about $k=4, 5$??

Sidenote: These questions arose when I was fooling around with numbers on graph paper the other day, and I have no idea whether they are solved or open, known or new. Heuristically, it seems that every square configuration should die out for $k=3$, as the sum of all entries will, on average, multiply by $\frac{4}{9}$ after each generation. But there might also exist some extraordinary initial configuration which results in infinite expansion.

Example: The picture below shows a sample when $k=3$ on a square grid (only nonzero entries shown). The grid would die out after Generation 2.
k=3

Edit: fixed a typo; now things should be clear.

$\endgroup$
3
  • 1
    $\begingroup$ You have not said what the fixed integer $k$ has to do with the automaton. $\endgroup$
    – Will Jagy
    Commented Nov 25, 2013 at 23:47
  • $\begingroup$ I have fixed the typo, things should make sense now. $\endgroup$
    – Apple
    Commented Nov 26, 2013 at 1:17
  • $\begingroup$ You are using $4$ neighbours, not $8$, it seems? $\endgroup$ Commented Nov 26, 2013 at 6:54

1 Answer 1

1
$\begingroup$

For $k=4$, a checkerboard pattern of 1's does not die out.

For $k=3$, the honeycomb pattern does not die out.

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .