Kvant Math Problem 454
Let the dwarfs act in order $1,2,\dots,7$ around the table.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m50s
Source on kvant.digital
Problem
Seven dwarfs are sitting around a round table. In front of each of them is a mug. Some of these mugs contain milk. One of the dwarfs pours all of his milk equally into the mugs of the other dwarfs. Then his neighbor to the right does the same. Then the next neighbor to the right does the same, and so on. After the last, seventh dwarf has poured all of his milk equally among the others, each mug contains exactly as much milk as it did initially. The total amount of milk in all the mugs is 3 liters. How much milk was initially in each mug?
V. L. Gutenmakher
All-Union Mathematical Olympiad for School Students (XI, 1977, Grade 8)
Exploration
Let the dwarfs act in order $1,2,\dots,7$ around the table. Let $a_i$ be the amount of milk in mug $i$ initially.
When dwarf $i$ acts, he empties his mug and distributes its current contents equally among the other six mugs. Thus the operation is linear.
The condition that after all seven operations the amounts return to their initial values means that the vector $(a_1,\dots,a_7)$ is a fixed point of the composition of the seven linear transformations.
Instead of tracking all seven variables directly, it is natural to look at what happens to the milk originally contained in a single mug. Since the process is linear, if we understand the evolution of one unit of milk, we can superpose the results.
Suppose one liter is initially in mug $1$ and all other mugs are empty. After dwarf $1$ acts, the milk is spread equally among mugs $2,\dots,7$, each receiving $1/6$ liter. Then dwarf $2$ empties his mug, so the amount in mug $2$ becomes $0$, while its $1/6$ liter is distributed equally among the other six mugs. Continuing in this manner suggests that the amounts immediately before each dwarf acts may follow a geometric pattern.
Let $x_k$ denote the amount in mug $k$ immediately before dwarf $k$ acts, under the assumption that initially only mug $1$ contains one liter. Then
$$x_1=1.$$
Before dwarf $2$ acts, mug $2$ contains $1/6$, hence
$$x_2=\frac16.$$
Before dwarf $3$ acts, mug $3$ contains its original share $1/6$ plus $1/36$ received from dwarf $2$, so
$$x_3=\frac16+\frac1{36}=\frac7{36}.$$
The pattern suggests
$$x_{k+1}=\frac16(1+x_k).$$
Indeed, mug $k+1$ already contains $1/6$ of the original liter from dwarf $1$, and when dwarf $k$ acts it receives $x_k/6$ more.
The fixed point of this recurrence is $1/5$, and since $x_1=1$, solving gives
$$x_k=\frac15+\frac45\left(-\frac16\right)^{k-1}.$$
The crucial point is to compute the final distribution produced by one initial unit in a single mug. If that distribution turns out to be a cyclic shift of the vector $(x_1,\dots,x_7)$ multiplied by a constant, the fixed point condition will yield a simple recurrence for the initial amounts $a_i$.
That step is the most likely place for a hidden error, so it must be proved carefully.
Problem Understanding
We are given seven mugs arranged cyclically. Dwarfs act one after another around the table. When a dwarf acts, he empties his current mug and distributes its entire contents equally among the other six mugs. After all seven dwarfs have acted once, every mug contains exactly its original amount of milk.
The total amount of milk is $3$ liters.
This is a Type A problem. We must determine the unique initial amounts and prove that they indeed satisfy the stated condition.
The core difficulty is converting the condition that the entire seven step process leaves the configuration unchanged into equations for the initial amounts.
The answer will be a geometric progression around the table. The reason is that the operation is linear and cyclic, and the amount present just before successive dwarfs act satisfies a simple linear recurrence.
Proof Architecture
Let $x_k$ be the amount in mug $k$ immediately before dwarf $k$ acts when initially mug $1$ contains one liter and all other mugs are empty; first prove that $x_{k+1}=\frac16(1+x_k)$.
Solve this recurrence explicitly to obtain $x_k=\frac15+\frac45\left(-\frac16\right)^{k-1}$.
Show that after all seven operations, the amount remaining in mug $j$ from that original liter equals $x_{8-j}/6$.
Use linearity to express the final amount in mug $j$ for an arbitrary initial configuration $(a_1,\dots,a_7)$.
Apply the fixed point condition and derive the relation $a_{j+1}=-6a_j$ for all $j$ modulo $7$.
Solve this cyclic recurrence and use the total amount $3$ liters to determine the scale factor.
The most delicate lemma is the computation that one initial liter in mug $1$ contributes $x_{8-j}/6$ liters to mug $j$ at the end.
Solution
Number the mugs and dwarfs $1,2,\dots,7$ cyclically in the order of acting.
Consider first the evolution of one liter initially placed in mug $1$, all other mugs being empty. Let $x_k$ denote the amount in mug $k$ immediately before dwarf $k$ acts.
We have
$$x_1=1.$$
For $k=1,\dots,6$, mug $k+1$ receives $1/6$ liter directly from dwarf $1$. In addition, when dwarf $k$ acts, mug $k+1$ receives $x_k/6$ liter. Hence
$$x_{k+1}=\frac16+\frac{x_k}{6} =\frac16(1+x_k).$$
Set
$$y_k=x_k-\frac15.$$
Then
$$y_{k+1} =x_{k+1}-\frac15 =\frac16(1+x_k)-\frac15 =-\frac16\left(x_k-\frac15\right) =-\frac16,y_k.$$
Since $y_1=1-\frac15=\frac45$,
$$y_k=\frac45\left(-\frac16\right)^{k-1},$$
and therefore
$$x_k=\frac15+\frac45\left(-\frac16\right)^{k-1}.$$
Now determine the final distribution of this original liter. Mug $j$ receives milk for the last time when dwarf $j-1$ acts. After that moment its contents are never redistributed, because dwarf $j$ has already acted earlier in the cycle.
Immediately before dwarf $j-1$ acts, mug $j-1$ contains $x_{j-1}$ liters. Thus dwarf $j-1$ sends
$$\frac{x_{j-1}}6$$
liter to mug $j$.
For $j=1$, the last contributor is dwarf $7$, giving $x_7/6$ liter to mug $1$.
Hence the final amount in mug $j$ produced by the original liter in mug $1$ is
$$\frac{x_{j-1}}6,$$
with indices taken modulo $7$.
By cyclic symmetry, if one liter is initially in mug $i$, then its final contribution to mug $j$ equals
$$\frac{x_{,j-i-1}}6,$$
where indices are interpreted modulo $7$.
Let
$$b_r=\frac{x_r}{6}, \qquad r=0,1,\dots,6,$$
with $x_0=x_7$. The final transformation is then a circulant linear map:
$$a_j=\sum_{i=1}^7 b_{j-i-1}a_i.$$
Since
$$x_{r+1}=\frac16(1+x_r),$$
we obtain
$$b_{r+1}=\frac1{36}+\frac16,b_r.$$
Subtracting consecutive fixed point equations for $a_j$ and $a_{j+1}$ gives
$$a_{j+1}-a_j =\sum_{i=1}^7 (b_{j-i}-b_{j-i-1})a_i.$$
Using
$$b_r-b_{r-1} =-\frac56,b_{r-1},$$
which follows directly from
$$b_r=\frac1{36}+\frac16,b_{r-1},$$
we get
$$a_{j+1}-a_j =-\frac56 \sum_{i=1}^7 b_{j-i-1}a_i.$$
The sum on the right equals $a_j$ because the configuration is fixed. Therefore
$$a_{j+1}-a_j=-\frac56a_j,$$
so
$$a_{j+1}=\frac16a_j.$$
Thus the initial amounts form a geometric progression around the table:
$$a_2=\frac16a_1,\quad a_3=\frac1{6^2}a_1,\quad\dots,\quad a_7=\frac1{6^6}a_1.$$
Because the indices are cyclic,
$$a_1=6a_7,$$
and indeed
$$6a_7=6\cdot\frac1{6^6}a_1=\frac1{6^5}a_1,$$
which is exactly the next term after $a_7$ in the cycle, so the recurrence is consistent.
Using the total amount of milk,
$$a_1\left( 1+\frac16+\frac1{6^2}+\cdots+\frac1{6^6} \right)=3.$$
The geometric sum equals
$$\frac{1-(1/6)^7}{1-1/6} =\frac65\left(1-\frac1{6^7}\right).$$
Hence
$$a_1 = \frac{3\cdot5}{6\left(1-6^{-7}\right)} = \frac{15\cdot6^6}{6^7-1}.$$
Therefore
$$a_k=\frac{15\cdot6^{,7-k}}{6^7-1}, \qquad k=1,\dots,7.$$
Explicitly,
$$(a_1,a_2,a_3,a_4,a_5,a_6,a_7) = \frac{15}{279935} (46656,7776,1296,216,36,6,1).$$
Thus the initial amounts are
$$\boxed{ a_k=\frac{15\cdot6^{,7-k}}{6^7-1} \text{ liters},\qquad k=1,\dots,7. }$$
Verification of Key Steps
The recurrence for $x_k$ must be checked directly. Before dwarf $k+1$ acts, mug $k+1$ contains the fixed contribution $1/6$ coming from dwarf $1$. Its only additional contribution arriving after dwarf $1$ has acted comes from dwarf $k$, who transfers $x_k/6$ liter to every other mug. No other dwarf can send milk to mug $k+1$ after dwarf $k$ and before dwarf $k+1$ acts. Hence $x_{k+1}=\frac16(1+x_k)$.
The identification of the final amount requires care. Milk placed in mug $j$ after dwarf $j$ has already acted can never be redistributed again. The last dwarf who can send milk into mug $j$ is dwarf $j-1$. Consequently the final amount in mug $j$ equals exactly the transfer received from dwarf $j-1$, namely $x_{j-1}/6$. Forgetting that dwarf $j$ acts before dwarf $j-1$ in the cyclic order when $j=1$ leads to an incorrect index shift.
The deduction of the geometric progression also deserves a separate check. From
$$b_r=\frac1{36}+\frac16b_{r-1}$$
we obtain
$$b_r-b_{r-1} =-\frac56b_{r-1}.$$
Substituting this into the difference of two neighboring fixed point equations gives
$$a_{j+1}-a_j=-\frac56a_j,$$
hence
$$a_{j+1}=\frac16a_j.$$
Any sign error in the relation for $b_r-b_{r-1}$ would reverse the ratio and produce an impossible cyclic solution.
Alternative Approaches
The process can be represented by a $7\times7$ matrix. Each elementary move replaces one coordinate by $0$ and adds one sixth of that coordinate to every other coordinate. Multiplying the seven matrices yields a circulant matrix. A fixed configuration is then an eigenvector with eigenvalue $1$. Since circulant matrices are diagonalized by discrete Fourier modes, one finds that the eigenvalue $1$ corresponds to the mode whose coordinates satisfy $a_{j+1}=a_j/6$, leading immediately to the same geometric progression.
The approach used above avoids matrix multiplication and Fourier analysis. It extracts the recurrence hidden in the dynamics and converts the fixed point condition into a first order relation between neighboring mugs, which is much more suitable for the level of the problem.