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[0,8] ounces in cup A and v[0,8] ounces in cup B, with u+v>0. Let's define VAn and VBn 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 VAn+1=12VAn+12(12VAn+VBn)=34VAn+12VBnVBn+1=12(12VAn+VBn)=14VAn+12VBn

Equivalently, if we let Vn=(VAn,VBn) be the vector of volumes after n rotations, then the matrix recurrence equation is Vn=(34121412)Vn1,

or if we let A=(34121412), then have simply Vn=AnV0.
Using the eigendecomposition of A, we get A=QΛQ1 where Q=(2111) and Λ=(10014) (and for good measure, Q1=(13131323)). As a result, we also have An=QΛnQ1=Q(1004n)Q1,
so Vn=(2111)(1004n)(13131323)V0=(2u+v3+4nu2v3u+v34nu2v3).

Therefore, after n rotations, the ratio of the volume in cup A to the total volume (u+v>0) is rn=2u+v3+4nu2v3u+v=23+4n3u2vu+v.

As n, we have that this ratio will always converge to rn23, regardless of the initial values of u and v (such that u+v>0).

No comments:

Post a Comment