Dragons and Kasha
This is how my ex-husband Joseph Bernstein used to start his courses in representation theory.
Suppose there is a four-armed dragon on every face of a cube. Each dragon has a bowl of kasha in front of him. Dragons are very greedy, so instead of eating their own kasha they try to steal kasha from their neighbors. Every minute every dragon extends four arms to the neighboring cube’s faces and tries to get the kasha from the bowls there. As four arms are fighting for every bowl of kasha, each arm manages to steal one-fourth of what is in the bowl. Thus each dragon steals one-fourth of of the kasha of each of his neighbors, while all of his own kasha is stolen too. Given the initial amounts of kasha in every bowl, what is the asymptotic behavior of the amounts of kasha?
You might ask how this relates to representation theory. First, it relates to linear algebra. We can consider the amounts of kasha as a six-dimensional vector space and the stealing process as a linear operator. As mathematicians, we can easily assume that a negative amount of kasha is allowed.
Now to representation theory. The group of rotations of the cube naturally acts on the 6-dimensional vector space of kashas. And the stealing operator is an intertwining operator of this representation. Now for a spoiler alert: I’m about to finish the solution, so stop here if you want to try it on your own.
The intertwining operator acts as a scalar on irreducible representations of the group. Thus we should decompose our representation into irreducible ones. The group has five irreducible representations with dimensions 1, 1, 2, 3, and 3.
We can decompose the kasha into the following three representations:
- One-dimensional. Every dragon has the same amounts of kasha. The stealing operator acts as identity.
- Three-dimensional. Dragons on opposite sides have the opposite amount of kasha. The stealing operator acts as zero.
- Two-dimensional. Dragons on opposite sides have the same amount of kasha and the total amount of kasha is zero. The stealing operator acts as −1/2.
We see that asymptotically every dragon will have the same amount of kasha.
Now it is your turn to use this method to solve a similar problem, where there are n dragons sitting on the sides of an n-gon. Each dragon has two arms, and steals half of the kasha from his neighbors. Hey, wait a minute! Why dragons? There are people around the table stealing each other’s kasha. But the question is still the same: What is the asymptotic behavior of the amounts of kasha?
Share:
Philip Petrov:
I’ve found a general formula for the case with the case when “three people have quantities of apples a, b and c and each one steal half of the apples of the others”. I end up with Jacobsthal numbers sequence with exception on n=1. Here it is (in Bulgarian language): https://www.cphpvb.net/fun/7987-stealing-from-the-neighboor/
1 March 2012, 7:03 amPhilip Petrov:
One correction to my previous comment – there is no exception in the n=1 case. The numerator of the coefficient in front of the “a”, “b” and “c” numbers in the specific pile is Jacobsthal number or production of Jacobsthal number; and the divisor is just 2^n
2 March 2012, 11:40 amJoe DeVincentis:
If n is odd, the asymptotic behavior is that everybody ends up with the same amount of kasha.
If n is even, there is a parity constraint that prevents this: the sum of the kasha at even-numbered seats in one iteration is the same as the sum of the kasha in odd-numbered seats the next iteration. However, within each of the two groups, they asymptotically approach having the same amount. Overall, each person approaches alternating between two values, the same two values for each person, but the even-numbered people are out of phase with the odd-numbered people.
I don’t understand the math behind the proof of the original puzzle, but here (for both cases), you can consider the result if all the kasha starts in one bowl. Then the pattern is initially that every other person has an empty bowl, and the others have C(s,i)/2^s of the total kasha, until s is large enough that the kasha starts to overlap, and then the numerator starts being sums of binomial coefficients where i assumes a set of values which are the same modulo the number of people in the loop (where, for the even case, there are two loops containing half the people each, and for the odd case there is a single loop). The result starting from any other state is the superimposition of multiple instances of this, rotated and multiplied by the starting values. Once everybody in the loop has some kasha, you can ignore the minimum amount of kasha, and treat it as if that amount is constant, and the remainder is circulating. This leads to the asymptotic approach to even distribution of the kasha (within each loop).
31 May 2012, 9:44 pm