Too Much Sugar In My Coffee

Algebra Level 5

Chino, Cocoa, Rize, Sharo, Chiya, Megu, and Maya sat around a circular table, in that order, drinking coffee. Chino always finds coffee too sweet, so she shared her coffee uniformly with the other cups, emptying her cup in the process.

Proceeding counterclockwise, each of the other girls, in turn, did the same. After the seventh girl had shared her coffee, the initial content of each cup was restored. The initial amount of coffee in all the cups added up to 3 litres.

The initial amount of coffee in Chino's cup can be represented as $\frac{A}{B}$ litres, where $A$ are $B$ are relatively prime positive integers. Input your answer as $A+B$ .

Reference: Anime: Is The Order A Rabbit?

This question is part of the problem set Mathematics in Anime

The answer is 13.

2 solutions

Zk Lin
Feb 7, 2016

Denote $x_{i}$ as the amount of coffee shared by the $i$ th girl to each of the other cups, starting from Chino, counterclockwise. Similarly, define $y_{i}$ as the initial amount of coffee in the $i$ th girl's cup. Verify the following equations.

$x_{1}=\frac{y_{1}}{6}$

$x_{2}=\frac{x_{1}+y_{2}}{6}$

$x_{3}=\frac{x_{1}+x_{2}+y_{3}}{6}$

$x_{4}=\frac{x_{1}+x_{2}+x_{3}+y_{4}}{6}$

$x_{5}=\frac{x_{1}+x_{2}+x_{3}+x_{4}+y_{5}}{6}$

$x_6=\frac{x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+y_{6}}{6}$

$x_{7}=\frac{x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+y_{7}}{6}$

Note also, that, $x_{1}=\frac{x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}}{6}$ . To explain this, note that after Chino emptied her cup, she received coffee from the other six girls. After the seventh girl shared her coffee, the initial amount of coffee in Chino's cup was restored. We can write this as $y_{1}=x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}$ , from which the equation above follows.

Similarly, you are invited to verify that $x_{i}=\frac{x_{1}+ \cdots+ x_{7} - x_{i}}{6}$ for $i=1,2,3,4,5,6,7$ .

It is easy to see now that all the $x_{i}$ are equal. (Why? Convince yourself that it is really so!) Plugging $x_{1}=x_{2}= \cdots =x_{7}=x$ into our initial system of $7$ equations above yield

$y_{1}=6x$

$y_{2}=5x$

$y_{3}=4x$

$y_{4}=3x$

$y_{5}=2x$

$y_{6}=x$

$y_{7}=0$

Therefore,

$3= y_{1}+y_{2}+y_{3}+y_{4}+y_{5}+y_{6}+y_{7}= 21x$

Hence, $x=\frac{1}{7}$ from which $y_{1}=\frac{6}{7}$ follows.

Adding $6$ and $7$ gives the desired answer $\boxed{13}$ .

Moderator note:

Good explanation for this interesting Russian Olympiad gem.

I would appreciate it if you were to explain more extensively why all of ${ x }_{ i }$ are equal. Although I don't fully understand your solution, it seems very clever, especially the simplification of ${ x }_{ i }$ , how did you conceive it?

Vladimir Smith - 5 years, 4 months ago

From $x_{i}=\frac{x_{1}+ \cdots+ x_{7} - x_{i}}{6}$ , we have the following $6$ equations:

$6x_{1}=x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7} \ \ \ \ \tag{1}$

$6x_{2}=x_{1}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7} \ \ \ \ \tag{2}$

$6x_{3}=x_{1}+x_{2}+x_{4}+x_{5}+x_{6}+x_{7} \ \ \ \ \tag{3}$

$6x_{4}=x_{1}+x_{2}+x_{3}+x_{5}+x_{6}+x_{7} \ \ \ \ \tag{4}$

$6x_{5}=x_{1}+x_{2}+x_{3}+x_{4}+x_{6}+x_{7} \ \ \ \ \tag{5}$

$6x_{6}=x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{7} \ \ \ \ \tag{6}$

$6x_{7}=x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6} \ \ \ \ \tag{7}$

Note that by taking $(1)-(2)$ , we have

$6(x_{1}-x_{2})=x_{2}-x_{1}$

$6(x_{1}-x_{2})=-(x_{1}-x_{2})$

$7(x_{1}-x_{2})=0$ , which implies $x_{1}=x_{2}$ .

Similarly, by taking $(2)-(3)$ , we have

$6(x_{2}-x_{3})=x_{3}-x_{2}$

$6(x_{2}-x_{3})=-(x_{2}-x_{3})$

$7(x_{2}-x_{3})=0$ , which implies $x_{2}=x_{3}$ .

The fact that $x_{3}=x_{4}, x_{4}=x_{5}, x_{5}=x_{6}, x_{6}=x_{7}$ can be derived in this similar manner, by taking the subtraction of two consecutive equations.

As for how I conceive the solution, I first found the solution by trial and error. The hard part is to justify that the solution is unique. To do this, I first made the crucial discovery that the coffee shared by each girl must be the same in order to restore the original content of their cups when the round ended (by defining $x_{i}$ and solving the sets of $6$ equations above). After that, the rest of the problem just falls apart easily.

I first found this problem in a problem solving worksheet, (I then modified it to include characters from an anime). Unfortunately, no solution is given in the worksheet so I have to work one out myself. Intriguingly, the person creating the problem sheet has indicated that an elegant $3$ -line solution to the problem exists. So far, the solution has eluded me. If you are feeling particularly adventurous, you might give it a try.

ZK LIn - 5 years, 4 months ago

Darn, I should have seen that! Thanks for the explanation, and congratulations on creating such a great solution.

Vladimir Smith - 5 years, 4 months ago

Yes, it's right - but not so easy to find! The bottom line is: A funny problem of no realism because: 1. One drinks coffee out of tea boxes. 2.) The content of a box is near 1 litre!

Andreas Wendler - 5 years, 4 months ago

I did not specify the volume of the cups to begin with, so we cannot discount the possibility that they are sufficiently big to contain $\frac{6}{7}$ litres. ;)

Honestly, I have never considered the question of realism while posting this problem. If I were concerned about being realistic, I wouldn't have posted a problem about anime characters pointlessly sharing coffee from cup to cup to "dilute" the sugar content when the practical solution would be to replace it with another serving.

cough -The scene of seven adorable girls acting like complete airheads while sharing their coffee to make sure the contents won't spill is impossibly cute to resist, though.

ZK LIn - 5 years, 4 months ago

Thank you, although it's not fully convincing for me because the question leaving is: Who drinks coffee (?) out of a tea cup containing almost one litre???

Andreas Wendler - 5 years, 4 months ago

Mark Hennings
Feb 10, 2016

The girls will get back to the original position after $7$ sharings would be if each sharing just moved the tea quantities cyclically around the table. Another way of saying this is that the original position will be regained after $7$ sharings if the effect of each sharing was effectively to circulate the cups one position around the table. This will happen if the girls (starting with Chino) have quantities $a,b,c,d,e,f,g$ in their cups, and $\big(0,b+\tfrac16a,c+\tfrac16a,d+\tfrac16a,e+\tfrac16a,f+\tfrac16a,g+\tfrac16a\big) \; = \; \big(g,a,b,c,d,e,f)\;,$ representing the cup position after Chino has shared her tea. Now Cocoa has $a$ in her cup, and when Cocoa has shared, Rize has $a$ , and so on, until Chino ends up with $a$ again after $7$ sharings.

It is easy to see from these equations that this happens when $(a,b,c,d,e,f,g) \; = \; (6x,5x,4x,3x,2x,x,0) \;.$ Thus Chino starts with $a=6x$ , where $(6+5+4+3+2+1)x = 3$ , and hence $a = \tfrac67$ , making the answer $\boxed{13}$ .

Good approach.

However, to show that the solution is unique, you need to justify the reason the contents in each cup indeed rotates cyclically after each sharing. It is insufficient to say that "The girls will get back to the original position after $7$ sharings would be if each sharing just moved the tea quantities cyclically around the table."

Indeed, the content in each cup would be restored if the quantity moves cyclically, but how do we know for sure that if the content in each cup does not rotate cyclically, the girls would not end up with the original amount of content in their cups after $7$ sharings?

ZK LIn - 5 years, 4 months ago

Well, the question did not ask me to prove that there was a unique solution. Applying this symmetry got me there quickly. I wouldn't be surprised the "three-line" proof you refer to uses symmetry along these lines.

However, with a little extra thought, what I have done is enough to prove uniqueness! Consider the matrices $S \; = \; \left(\begin{array}{ccccccc} 0 & 0 & 0 &0 & 0 & 0 & 0 \\ \frac16 & 1 & 0 & 0 & 0 & 0 & 0 \\ \frac16 & 0 & 1 & 0 & 0 & 0 & 0 \\ \frac16 & 0 & 0 & 1 & 0 & 0 & 0 \\ \frac16 & 0 & 0 & 0 & 1 & 0 &0 \\ \frac16 & 0 & 0 & 0 & 0 & 1 &0 \\ \frac16 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right) \qquad \qquad C \; = \; \left( \begin{array}{ccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right)$ Then if $\mathbb{x}$ is a column vector representing the quantities of tea in the girls' cups, then $S\mathbf{x}$ is the quantity of tea in the cups after Chino has shared, while $C\mathbf{x}$ is the quantity of tea in the girls' cups if the cups are passed cyclically in the reverse direction.

The matrix that implements Cocoa's sharing is then $C^{-1}SC$ , the matrix that implements Rize's sharing is $C^{-2}SC^2$ and so on, and so the total sharing process is implemented by the matrix $(C^{-6}SC^6)(C^{-5}SC^5)(C^{-4}SC^4)(C^{-3}SC^3)(C^{-2}SC^2)(C^{-1}SC)S \; = \; (CS)^7$ and the problem reduces to finding an eigenvector of $(CS)^7$ with eigenvalue $1$ (and nonnegative coefficients).

Let $V$ be the vector space of eigenvectors of $(CS)^7$ of eigenvalue 1. If $\mathbf{x} \in V$ then $(CS)^7 (CS)\mathbf{x} \; = \; (CS) (CS)^7 \mathbf{x} \; = \; (CS)\mathbf{x} \;,$ and hence $(CS)\mathbf{x} \in V$ . The matrix $CS$ acts as a linear transformation $T$ on $V$ such that $T^7 = \mathrm{id}$ is the identity transformation. Since $x^7-1$ can be written as a product of distinct linear complex factors, $V$ has a basis consisting of (complex) eigenvalues of $T$ . But $CS \; = \; \left(\begin{array}{ccccccc} \frac16 & 1 & 0 & 0 & 0 & 0 & 0 \\ \frac16 & 0 & 1 & 0 & 0 & 0 & 0 \\ \frac16 & 0 & 0 & 1 & 0 & 0 & 0 \\ \frac16 & 0 & 0 & 0 & 1 & 0 &0 \\ \frac16 & 0 & 0 & 0 & 0 & 1 &0 \\ \frac16 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 &0 & 0 & 0 & 0 \end{array}\right)$ is a simple variant of a companion matrix, and so has characteristic polynomial $f(t) = t^7 - \tfrac16(t + t^2 + t^3 + t^4 + t^5 + t^6) \;.$ Any eigenvalue of $T$ must be a seventh root of unity which is also a zero of $f(t)$ . Since $(t-1)f(t) = \tfrac76t^7(t-1) - \tfrac16t(t^7-1)$ , the only such eigenvalue is $1$ , Thus the only eigenvalue of $T$ is $1$ ,which means that every eigenvalue of $(CS)^7$ with eigenvalue $1$ is also an eigenvector of $CS$ with eigenvalue $1$ .

But solving for eigenvectors of $CS$ with eigenvalue $1$ was my solution technique.

Mark Hennings - 5 years, 4 months ago

Very nice solution indeed. The way you define the sharing operation using $C^{-1}XC$ and the way you prove $(CS)$ and $(CS)^{7}$ share the same eigenvectors for eigenvalue $=1$ simply blows my mind away! Although I couldn't understand the last part (the companion matrix and how it relates to the characteristic polynomial, guess I will just have to take the leap of faith and believe that the only eigenvalue is $1$ ), that is purely due to my lack of knowledge in linear algebra. I have little trouble understanding the rest of your arguments, you did a superb job in explaining the steps.

After marveling at your solution, I must then ask the question: What motivates you to define the sharing operation as $C^{-1}XC$ ? Is it your initial observation that the contents rotate cyclically? To the uninitiated in linear algebra (read:me), this step, albeit clever, seemingly comes out of nowhere.

Finally, not to nitpick but I notice some minor typos (which do not diminish the beauty of this solution).

Thus the only eigenvalue of $T$ is $1$ ,which means that every eigenvalue of $(CS)^{7}$ with eigenvalue $1$ is also an eigenvalue of $(CS)$ with eigenvalue $1$ .

I believe you meant

Thus the only eigenvalue of $T$ is $1$ ,which means that every eigenvector of $(CS)^{7}$ with eigenvalue $1$ is also an eigenvector of $(CS)$ with eigenvalue $1$ .

Seeing this marvelous solution of yours certainly motivates me to study the application of linear algebra in more depth. (Guess I will have a find a good introductory textbook, and start working from there).

ZK LIn - 5 years, 4 months ago

@Zk Lin – Typo fixed. Well spotted!

My starting point was to justify using my symmetry argument as being adequate to find all solutions. Basically, each girl's sharing operation performs the same algebraic operations, but to different sets of components. Thus it must be possible to express the other girls' sharing operations in terms of Chino's; a little thought, based on how Cocoa's and the rest's sharing operations worked, led conjugating with $C$ .

Thought experiment: If all the girls pass their cups back one place, then Chino does all the sharing (she is the only one neat enough to do this without spilling???), and then the cups are passed back to their original owners, the end result is the same as if Cocoa had done the sharing. This is why $C^{-1}SC$ does Cocoa's work. Similar arguments handle Rize and the rest.

The characteristic polynomial of a square matrix $A$ is the polynomial $\mathrm{det}(tI - A)$ ; its roots are the eigenvalues of $A$ . The companion matrix to the polynomial $f(t) = t^n + a_{n-1}t^{n-1} + a_{n-2}t^{n-2} + \cdots + a_1t + a_0$ is the $n \times n$ matrix $A_f \; = \; \left( \begin{array}{ccccccc} 0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ -a_0 & -a_1 & -a_2 & -a_3 & \cdots & -a_{n-2} & -a_{n-1} \end{array} \right)$ with $1$ s on the first superdiagonal, minus the coefficients along the bottom row, and $0$ s everywhere else. It is a standard result of linear algebra that the characteristic polynomial of this matrix is $f(t)$ . You can prove it by induction, evaluating the determinant of $tI - A_f$ by the first column. Having the polynomial coefficients down the first column rather than along the bottom row does not affect this result.

Spotting that $CS$ was, basically, a companion matrix meant that I did not have to do any work evaluating the characteristic polynomial (and avoided calculating a $7\times7$ determinant!).

Mark Hennings - 5 years, 4 months ago

@Mark Hennings – I see. Thanks for the detailed explanations!

ZK LIn - 5 years, 4 months ago

@Zk Lin – This is the typical approach for such Markov Chain events. We set up the matrix, and then (attempt to) find the eigenspace corresponding to the eigenvalue of 1.

Calvin Lin Staff - 5 years, 3 months ago

Too Much Sugar In My Coffee

Reference: Anime: Is The Order A Rabbit?

This question is part of the problem set Mathematics in Anime

The answer is 13.

2 solutions

Moderator note:

0 pending reports