Sunday, April 11, 2021

Always see the cup A as two-thirds full, eventually

You have two $16$-ounce cups — cup A and cup B. Both cups initially have $8$ ounces of water in them.

You take half of the water in cup A and pour it into cup B. Then, you take half of the water in cup B and pour it back into cup A. You do this again. And again. And again. And then many, many, many more times — always pouring half the contents of A into B, and then half of B back into A.

When you finally pause for a breather, what fraction of the total water is in cup A?

Let's solve the general case, as it will turn out that the particulars of the initial conditions will not particularly matter in this system of recurrence equations. Let's assume that you start out with $u \in [0,8]$ ounces in cup A and $v \in [0,8]$ ounces in cup B, with $u + v > 0.$ Let's define $V^A_n$ and $V^B_n$ as volumes of water in each cup after $n$ full rotations of pouring half of cup A into cup B and then half of cup B back into cup A. By construction, the recurrence relationship is thus \begin{align*}V_{n+1}^A &= \frac{1}{2} V_n^A + \frac{1}{2} \left( \frac{1}{2} V_n^A + V_n^B \right) = \frac{3}{4} V_n^A + \frac{1}{2} V_n^B \\ V_{n+1}^B &= \frac{1}{2} \left( \frac{1}{2} V_n^A + V_n^B \right) = \frac{1}{4} V_n^A + \frac{1}{2} V_n^B\end{align*}

Equivalently, if we let $V_n = (V_n^A, V_n^B)$ be the vector of volumes after $n$ rotations, then the matrix recurrence equation is $$V_n = \begin{pmatrix} \frac{3}{4} & \frac{1}{2} \\ \frac{1}{4} & \frac{1}{2} \end{pmatrix} V_{n-1},$$ or if we let $A = \begin{pmatrix} \frac{3}{4} & \frac{1}{2} \\ \frac{1}{4} & \frac{1}{2} \end{pmatrix},$ then have simply $$V_n = A^n V_0.$$ Using the eigendecomposition of $A,$ we get $A = Q\Lambda Q^{-1}$ where $Q = \begin{pmatrix} 2 & 1 \\ 1 & -1 \end{pmatrix}$ and $\Lambda = \begin{pmatrix} 1 & 0 \\ 0 & \frac{1}{4} \end{pmatrix}$ (and for good measure, $Q^{-1} = \begin{pmatrix} \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & -\frac{2}{3} \end{pmatrix}$). As a result, we also have $$A^n = Q \Lambda^n Q^{-1} = Q \begin{pmatrix} 1 & 0 \\ 0 & 4^{-n} \end{pmatrix} Q^{-1},$$ so $$V_n = \begin{pmatrix} 2 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 4^{-n} \end{pmatrix} \begin{pmatrix} \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & -\frac{2}{3} \end{pmatrix} V_0 = \begin{pmatrix} 2 \frac{u+v}{3} + 4^{-n} \frac{u-2v}{3} \\ \frac{u+v}{3} - 4^{-n} \frac{u-2v}{3} \end{pmatrix}.$$

Therefore, after $n$ rotations, the ratio of the volume in cup A to the total volume ($u+v > 0$) is $$r_n = \frac{2 \frac{u+v}{3} + 4^{-n} \frac{u-2v}{3}}{u+v} = \frac{2}{3} + \frac{4^{-n}}{3} \frac{u-2v}{u+v}.$$ As $n \to \infty,$ we have that this ratio will always converge to $r_n \to \frac{2}{3}$, regardless of the initial values of $u$ and $v$ (such that $u + v > 0$).

No comments:

Post a Comment