How many good distributions of coins are there?

Question

At each vertex in figure 1, there is a student. A total of n = 60k coins are distributed to these students. The coins are redistributed as follows: Each student simultaneously give an equal number of coins to each of their neighbours. For instance, the student at the center vertex gives one fifth of their coins to each of the student's neighbours. Call a distribution of coins good if the coins can be distributed so that every student gives an integer number of coins to each of the student's neighbours and if after all students distribute their coins as described above, all students have the same number of coins they did before the coins were redistributed. How many good distributions of coins are there?

Source: this is based on problem 7 of the 2012 AIME I.

Let a be the number of coins of the student at the center, b the total number of coins of the students at distance one from the center, c the total number of coins of the students at distance 2 from the center, and d the total number of coins of the students at distance 3 from the center. Then one has the following system of equations: $a=b/3, b=a+c/2, c=2/3 b + d/2,d=c/2+d/2.$ The solution to the system is $c=4a=d, b=3a, a = k.$

The obvious distribution of coins where each student at the distances 0,1,2,3 from the center receives 5k,3k,4k,4k coins works. But I'm not sure how to find any other distributions without defining a lot of variables (one for each vertex) and getting a really complex system of equations.

Figure 1:

Answer 1

If $\mathbf x$ is a $16$-dimensional vector representing a distribution of coins, then let $P\mathbf x = \mathbf x$ be the system of equations that tells us that $\mathbf x$ is good.

The matrix $P$ is a stochastic matrix: it satisfies $\mathbf 1^{\mathsf T}P = \mathbf 1^{\mathsf T}$. (In other words, the total number of coins does not change after the operation described in the problem.)

There are a couple of different ways to think about the problem of distribution of coins more abstractly:

1. Via Markov chains. A random walk on the graph in the problem, where from each vertex we choose a uniformly random neighbor to go to, is described by the same system of equations: if the probability distribution is $\mathbf x$ at one time step, it is $P\mathbf x$ at the next time step. The system $P\mathbf x = \mathbf x$ describes a stationary distribution of the Markov chain. With the condition that $\mathbf x$ is nonnegative and its components sum to $1$, when the graph is connected, there is a unique stationary distribution.
2. Using the Perron–Frobenius theorem. (The matrix $P$ is nonnegative and irreducible, which once again comes back to the graph being connected.) The equation $\mathbf 1^{\mathsf T}P = \mathbf 1^{\mathsf T}$ tells us that $\mathbf 1$ is a left eigenvector with eigenvalue $1$ whose components are all positive, so $1$ is the Perron–Frobenius eigenvalue. Therefore there is a right eigenvector as well, satisfying $P\mathbf x = \mathbf x$, its components are also all positive, and it is unique up to scaling.

In either case, we conclude that there is a unique good distribution of coins. It is the one we already found. And the theory of random walks has a final trick to help us along in case we did not find it:

• When we take an unbiased random walk on a graph (i.e. every neighbor is always equally likely) the stationary distribution is obtained by letting every component of $\mathbf x$ be proportional to the degree of the corresponding vertex.

That exactly tells us that the vertices of degree $5$ get $5k$ coins, the vertices of degree $4$ get $4k$ coins, and the vertices of degree $3$ get $3k$ coins.