SandPiles toppling that start to cycle.

61 Views Asked by At

There are grains of sand are have been dropped on a 3x3 grid, and when some capacity is reached, the grains start spilling off. For a a vertex v, the degree |v| denotes the number of edges adjacent to v. Each vertex v can hold exactly |v|−1 grains on it. If there are more grains on it, then the grains start spilling off to its neighbors but do not go out of the grid, meaning that the number grains that spill off is equal to the edges connected to its neighbors until fewer than |v| grains of sand lie on v. Those grains that topple to the other vertices may cause overloads on its neighbors, causing spills from there.

For example, the central vertex can hold upto 3 grains, if you put 4 grains, it will send one grain to each of cell that shares an edge with it. Or, If the corner cell/vertex contains more than 1 grain, it will send the grains to the two cells.

This means that there is a possibility that the grains might oscillate between cells and they will eventually start rotating/cycling between arrangements. My question is if they do cycle through n arrangments, what can be the possible values of n ? By trial and error the value i have found i think the value to be 2. I am not sure if it true though.

Also, can we prove the existance of a number L such that every arrangement will reach an arrangement where it will not send any grains or will reach a cyclic arrangement in less than or equal to L steps. Again by trail and error I think the answer is 23, but I am not sure.

1

There are 1 best solutions below

1
On

Partial answer (rewritten and expanded).

To make it easier to talk about, I'm going to define some terms. Since this is a cellular automatum, I'm going to uses "cells" instead of nodes.

  • A cell is critical when it has at least as many grains as its degree. The amount of grains above the nearest multiple of its degree is its excess. A cell with $0$ excess is balanced (i.e., the number of grains is a multiple of the degree, so upon dispersement, nothing is left).
  • A state is an assignment of a number of grains to each cell. If a state has no critical cells, it is stable. When all critical cells in a state $P$ disperse their grains, the new state is called the child of $P$, and is denoted by $P'$. The descent of $P$ is the sequence $P, P', P'', \ldots$. The elements of the descent are the descendents of $P$.
  • $P$ is cyclic if it is its own descendent (this includes stable states), otherwise $acyclic$. For arbitrary $P$, the acyclic part of its descent is its lead (whose count is the lead lengh, and cyclic part is the cycle. The cycle length is the fewest number of steps between repeats of a cyclic descendent.
  • Given two states $P$ and $Q$ and integers $n$ and $m$, $nP + mQ$ denotes the "potential state" whose grains in each cell are the indicated combination of the grains for $P$ and $Q$. If all cells in $nP + mQ$ have a non-negative number of grains, then the state is valid.
  • A state is balanced if every cell in it is balanced. It is completely balanced if its entire descent is balanced. It is perfect if it is completely balanced and cyclic.

Since the number $N$ of grains does not change, there are only a finite number of states possible for each $N$, namely $N+8 \choose 8$ (this is a correction from my original post, where I accidently used the wrong form of stars and bars). The descent of any state $P$ therefore cannot be longer than this without repeating a state. That state, and every state following it are cyclic. Hence every state has a cycle, and acyclic states have a lead.

A useful result is:

If $P$ is any state, and $Q$ is balanced, then when $P + mQ$ is valid, so is $P'+mQ'$, and $$(P+mQ)' = P'+mQ'$$ which can be verified by writing out the cells. As long as the descendents of $Q$ remain balanced, the descendents of $P + mQ$ will continue to have the same form. If $Q$ is completely balanced, then the entire descent of $P+mQ$ is the same linear combinations of the descents of $P$ and $Q$. If $Q$ is perfect, then the lead length of $P$ and $P+mQ$ are the same, and the cycle length of $P + mQ$ will be the least common multiple of the cycle lengths of $P$ and $Q$.

The critical state $$C := \begin{bmatrix}2&3&2\\3&4&3\\2&3&2\end{bmatrix}$$ is balanced and stable, and therefore perfect with cycle length $1$. Therefore it can be subtracted from any state all of whose cells are greater than its own, without changing lead or cycle lengths. Therefore there is no reason to examine states without at least one non-critical cell. The 2-cycle $$\begin{bmatrix}0&3&0\\3&0&3\\0&3&0\end{bmatrix}\longleftrightarrow\begin{bmatrix}2&0&2\\0&4&0\\2&0&2\end{bmatrix}$$ is also perfect, and if added to another cycle will result in a cycle of even length. The symmetric states $$\begin{bmatrix}6&0&0\\0&0&0\\0&0&6\end{bmatrix}, \begin{bmatrix}6&0&6\\0&0&0\\6&0&6\end{bmatrix},\begin{bmatrix}0&6&0\\0&0&0\\0&6&0\end{bmatrix},\begin{bmatrix}0&0&0\\0&12&0\\0&0&0\end{bmatrix}$$ and their rotations are completely balanced, and descend into the previous perfect cycle with a lead length of $1$. They too when added to another cycle will result in an even length cycle. In particular, note that any odd-length cycle must therefore have $11$ or fewer grains in the center cell for all states in the cycle. Similarly any state with opposing edge or corner cells with $6$ or more grains in each must have an even cycle.

The states $$\begin{bmatrix}4(3^n)&0&0\\0&0&0\\0&0&0\end{bmatrix}, \begin{bmatrix}0&4(3^n)&0\\0&0&0\\0&0&0\end{bmatrix}$$and their rotations are balanced, but not completely balanced. How long their descendents remain balanced depends on the size of $n$. But they will not cycle until the balance is broken, so you can get arbitrarily large lead lengths by increasing $n$. Both states with $14$ grains instead of $4(3^n)$ will eventually pick up perfect 2-cycle component. At $13$ grains in a single corner descends into a steady state, but $13$ grains on an edge picks up a $6$-cycle after a lead of $5$ - the first cycle length I've found that wasn't a power of $2$: $$\underset\longleftarrow{\begin{bmatrix}2&0&2\\2&1&2\\1&2&1\end{bmatrix} \to \begin{bmatrix}0&2&0\\3&1&3\\1&2&1\end{bmatrix} \to \begin{bmatrix}1&2&1\\0&3&0\\2&2&2\end{bmatrix} \to \begin{bmatrix}1&2&1\\1&3&1\\0&4&0\end{bmatrix} \to \begin{bmatrix}1&2&1\\1&4&1\\1&1&1\end{bmatrix} \to \begin{bmatrix}1&3&1\\2&0&2\\1&2&1\end{bmatrix}}$$

Any odd length cycle would therefore have to have corners with $13$ or fewer grains, and edges and centers with $12$ or fewer grains. For any cycle of length greater than $2$, there must be an example with all corners and edges having fewer than $36$ grains each, and fewer than $12$ grains in the center.

These could all be searched relatively easily, which would tell you what cycle lengths are possible, and in particular, what the maximum cycle length is.