3

I am thinking through a word problem, which proceeds as follows:

Mom distributed $L$ liters of juice among her $N$ sons. The first son distributed the contents of his pail evenly to the pails of the other $N-1$ sons. The second did the same, and so on. After the $N$th son distributed the contents his pail evenly to the other $N-1$ sons, it was found that each son had exactly as much juice in his pail as at the start. What was the initial distribution of the juice?

I was considering approaching this through "brute force" by labeling each of the initial allocated amounts as $L_1, L_2, \dotsc ,L_N$ where $L_1 + \dotsb + L_N = L$, although am wondering how to best proceed from there. What are some ideas or intuition on how to approach this problem efficiently?

Mike Pierce
  • 18,938
Margaret
  • 33

2 Answers2

2

The easiest way to find a solution would be if the process is stationary in the sense that each operation is the same except that the sons are cyclically shifted by $1$ in each step. Then instead of using $N$ different matrices to model it, we can use a single one, which combines the distribution and the cyclical shift. Let's set up this matrix and see if it has a stationary distribution – if so, this will be a solution to the problem.

The matrix that describes the distribution is

$$ \pmatrix{0&&\cdots&&&0\\\frac1{N-1}&1\\\frac1{N-1}&&1\\\frac1{N-1}&&&1\\\vdots&&&&\ddots}\;, $$

so the matrix for distribution and cyclical shift is

$$ \pmatrix{\frac1{N-1}&1\\\frac1{N-1}&&1\\\frac1{N-1}&&&1\\\vdots&&&&\ddots\\0&&\cdots&&&0}\;. $$

The system of equations for a stationary distribution of this matrix yields a constant increment between the entries, so the stationary distribution is

$$ \pmatrix{(N-1)\alpha\\(N-2)\alpha\\\vdots\\\alpha\\0}\;. $$

For this to add up to $L$, we need

$$\binom N2\alpha=L\;,$$

and thus

$$ \alpha=\frac L{\binom N2}\;. $$

To see that this solution is unique, note that without the last, permanently zero component this is the matrix of an irreducible finite Markov chain, and such a Markov chain has a unique stationary distribution.

joriki
  • 238,052
0

The solution I came up with is: $$ \frac{(N-1)L}{ \frac{N(N-1)}{2}}, \frac{(N-2)L}{\frac{N(N-1)}{2}}, \dots, \frac{L}{\frac{N(N-1)}{2}},0. $$ Reasoning:

After first son distributes his share to the other $N-1$ sons, the distribution looks like this: $$ 0, \frac{(N-1)L}{\frac{N(N-1)}{2}}, \frac{(N-2)L}{\frac{N(N-1)}{2}},\dots, \frac{2L}{\frac{N(N-1)}{2}}, \frac{L}{\frac{N(N-1)}{2}}. $$ Now, the second son gives everybody else $\frac{L}{\frac{N(N-1)}{2}}$ juice, and the distribution looks like this: $$ \frac{L}{\frac{N(N-1)}{2}}, 0, \frac{(N-1)L}{\frac{N(N-1)}{2}},\dots, \frac{3L}{\frac{N(N-1)}{2}}, \frac{2L}{\frac{N(N-1)}{2}}. $$ You can see that continuing with this manner, at the end we get the original distribution, which is what we need.

Wojciech Karwacki
  • 893