a problem from 1977 all Soviet Union Mathematical Olympiad

Seven dwarfs are sitting at a round table. Each has a cup, and some cups contain milk. Each dwarf in turn pours all his milk into the other six cups, dividing it equally among them. After the seventh dwarf has done this, they find that each cup again contains its initial quantity of milk. How much milk does each cup contain, if there were 42 ounces of milk altogether?

The problem can be found here Futility Closet

Solution 1:

Let there be a total of $a$ ounces of milk. Let the $k^{th}$ dwarf have $x_k^{(0)}$ ounces of milk initially.

Let do it for smaller cases to guess the pattern. It is evident that the last dwarf has $0$ milk initially.

For $n=2$: Then $x_1^{(0)} = a$ and $x_2^{(0)} = 0$.

For $n=3$: Then $$x_1^{(1)} =0; \,\,\,\,x_2^{(1)} =x_2^{(0)} + \dfrac{x_1^{(0)}}2; \,\,\,\,x_3^{(1)} =\dfrac{x_1^{(0)}}2$$ Then $$x_1^{(2)} =\dfrac{x_2^{(0)} + \dfrac{x_1^{(0)}}2}2; \,\,\,\,x_2^{(2)} =0; \,\,\,\,x_3^{(2)} =\dfrac{x_1^{(0)}}2 + \dfrac{x_2^{(0)} + \dfrac{x_1^{(0)}}2}2$$ Then $$x_1^{(3)} =\dfrac{x_2^{(0)} + \dfrac{x_1^{(0)}}2}2 + \dfrac{\dfrac{x_1^{(0)}}2 + \dfrac{x_2^{(0)} + \dfrac{x_1^{(0)}}2}2}2; \,\,\,\,x_2^{(2)} =\dfrac{\dfrac{x_1^{(0)}}2 + \dfrac{x_2^{(0)} + \dfrac{x_1^{(0)}}2}2}2; \,\,\,\,x_3^{(2)} = 0$$ Hence, $$x_1^{(0)} = \left(\dfrac12 + \dfrac18\right)x_1^{(0)} + \left(\dfrac12 + \dfrac14\right)x_2^{(0)}$$ $$x_2^{(0)} = \left(\dfrac14 + \dfrac18\right)x_1^{(0)} + \left(\dfrac14\right)x_2^{(0)}$$ This gives us $x_1^{(0)} = 2x_2^{(0)} \implies x_1^{(0)} = \dfrac{2a}3$ and $x_2^{(0)} = \dfrac{a}3$.

This leads us to a possible guess if there are $n$ dwarfs i.e. $$x_k^{(0)} = (n-k)y$$ such that $$\sum_{k=1}^n x_k^{(0)} = a \implies y = \dfrac{2a}{n(n-1)}$$ i.e. for $7$ dwarfs, we have \begin{align} x_1^{(0)} & = 6y\\ x_2^{(0)} & = 5y\\ x_3^{(0)} & = 4y\\ x_4^{(0)} & = 3y\\ x_5^{(0)} & = 2y\\ x_6^{(0)} & = y\\ x_7^{(0)} & = 0 \end{align} where $y=2$. (Because $y+2y+3y+4y+5y+6y = 42 \implies 21y = 42 \implies y=2$). At transfer $k$, the $k^{th}$ dwarf has $6y$ ounce of milk and transfer to each other dwarf $y$ ounce of milk.

In general, if there are $n$ dwarfs and the total milk is $a$ ounces, and if the $k^{th}$ dwarf has $x_k^{(0)}$ of milk to begin with then $$x_k^{(0)} = \dfrac{2(n-k)}{n(n-1)}a$$

Solution 2:

Let $n+1$ be the number of dwarfs, we can put $n=6$ later. We can imagine a training round of $n+1$ moves was done (which brings back the initial configuration) so that every dwarf will have distributed at least once, and we can then (for this moment) number the dwarfs $0,1,\ldots,n$, according to the number of moves since they were most recently distributor. We can describe the distribution by a sequence $(x_0,x_1,\ldots,x_n)$ (with $x_0=0$) of quantities held according to their number. After one move, we renumber the dwarfs according to the same rule, and find a new value for $(x_0,x_1,\ldots,x_n)$, again with $x_0=0$. (If you find renumbering dwarfs confusing, you can imagine their numbers fixed, dwarf number $n$ doing the distributing every time, and everyone then passing their cup to the next numbered dwarf modulo $n+1$; the point is we just record the correspondence of numbers to quantity, dwarfs and cups being auxiliary.) Leaving aside $x_0$ which is always $0$, the transformation of $(x_1,\ldots,x_n)$ is linear, and given by the matrix (acting on column vectors): $$ A = \begin{pmatrix}0&0&\ldots&0&1/n\\ 1&0&\ldots&0&1/n\\0&1&\ldots&0&1/n\\\vdots&\ddots&\ddots&0&1/n\\ 0&\ddots&0&1&1/n \end{pmatrix}. $$ We need to find an eigenvector of $A^{n+1}$ for the eigenvalue $1$.

The eigenvalues $\lambda$ of $A$ that give rise to such an eigenvalue of $A^{n+1}$ are those with $\lambda^{n+1}=1$. Now $A$ is the companion matrix of the polynomial $P=X^n-\frac1n(X^{n-1}+\cdots+X+1)$, which is therefore the minimal and characteristic polynomial of $A$. Clearly $A$ has an eigenvalue $\lambda=1$ (in fact $A$ is a column-stochastic matrix), which is easily checked to be a simple root of $P$. But any other $n+1$-st root of unity is a root of $X^n+X^{n-1}+\cdots+X+1$, and since this polynomial is relatively prime to $P$ by inspection, $A$ has no such roots as eigenvalue; the eigenvalue $1$ of $A^{n+1}$ will be simple, with the same eigenvectors as those for $\lambda=1$ of $A$. We can therefore simply compute those eigenvectors, which is easy; they are the scalar multiples of $$ \begin{pmatrix}1\\2\\3\\\vdots\\n\end{pmatrix}. $$ Finally we choose the multiple with the required sum of entries. For $n=6$ and sum of entries $42$ the multiple is by $2$, so we find the solution $x_i=2i$ for $i=0,1,\ldots,6$ in this case.

If you don't like the idea of excluding the empty cup from considerations, you can include it, which extends $A$ to an $(n+1)\times(n+1)$ matrix with initial row zero which is still a column-stochastic companion matrix; the polynomial $P$ will be multiplied by $X$, but the arguments will be otherwise identical. The renumbering scheme has turned the process into a very simple Markov chain. Note also that the scheme removes any dependency on the order in which the dwarfs empty their cups, which is irrelevant provided that each dwarf empties exactly once, and that the training round follows the same order as the following "real" round of moves.