\documentclass{article}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{graphicx}
\input seteps
\begin{document}
\title{Truck drivers, straws, and sharing a glass of water}
\author{Kevin Iga and Kendra Killpatrick\\
Pepperdine University}
\maketitle
The problem for this paper arose recently as the second author and her
husband were moving from Colorado to Southern California. In the midst
of loading their boxes onto the moving truck, their moving truck
driver, John, discovered that the author was a math professor and said
he had a math problem that had long been bothering him. He then
presented the following scenario:
\begin{quotation}
I was at a truckstop and talking with a friend of mine, Bill. His
glass was close to empty, and mine was pretty full. Let's say I took a
straw in my glass, and put my finger on the top to trap the water in
the straw, and picked it up and moved it over to Bill's glass, and then
let go so the water goes into Bill's glass. Then I put the straw in
Bill's glass, and used my finger to trap the water, in the straw,
moving it back over to my glass. If I did that over and over again,
what would happen? Would we ever end up with the same amount in both
glasses?
\end{quotation}
In other words, John transfers some water from his glass to Bill's
using his straw in the following way: John stands his straw vertically
in the glass so that the straw hits the bottom. He then covers the
straw with his finger, and pulls the straw out of the water. It will
then have a certain amount of water in the straw---in fact, at the
height of the water in John's glass. He then moves the straw over
Bill's glass and lifts his finger, thereby releasing the water into
Bill's glass. See figure~\ref{strawmove}
\begin{figure}
\vspace{.5in}
\includegraphics{strawmove.eps}
\caption{Transferring water with a "straw move"}
\label{strawmove}
\end{figure}
John then puts the straw in Bill's glass and uses the same technique to
transfer water back to his glass. He does this over and over again.
Will he ever reach the state where both glasses are even?
\section{The setup}
Instead of measuring the amount of water in each glass (they are
related anyway, since the total amount of water is not changing), we
can measure the amount in John's glass. Furthermore, we can use a
system of units that makes the total amount of water equal to one.
Another way to look at this is that we are measuring the percentage of
the total amount of water that is in John's glass.
Let $x$ represent the percent of the total amount of water that is in John's glass. Then $1-x$ will represent the percent of water in Bill's glass. We will assume that the two glasses are cylindrical and of the same size (actually we just need them to have the same constant cross sectional area and that they are each sufficiently big to hold the
amounts of water in question).
The main consequence of this assumption is that when we put a straw into the glass, the amount taken up by the straw is proportional to the amount of water in the glass. The ratio of the amount of water in the straw to the amount of water in the glass is simply the ratio of the cross sectional area of the straw to the cross sectional area of the
glass.
Let $p$ represent this ratio, so that if John's glass has $x$ amount of water in it, and we put the straw in John's glass, then the straw will pick up $px$ amount of water and transfer it to Bill's glass.
Thus, if we pay attention to how much water is in John's glass (we can
figure out how much is in Bill's glass by subtracting from one as
mentioned above), we see that if John starts with $x$ amount of water
in his glass, after a single straw transfer of water to Bill's glass,
John will have $x - px = (1-p)x$ amount of water in it. We define
\[f(x)=(1-p)x\]
and note that this describes what happens to the amount of water in John's glass after a move of water from John's glass to Bill's glass.
Similarly, if John's glass starts with $x$ amount of water, and we transfer water from Bill's glass to John's glass, we are transferring
$p(1-x)$ amount of water, so John's glass will now have $x + p(1 - x) =
(1-p)x + p$ amount of water in it. We likewise define
\[g(x)=(1-p)x+p\]
to describe how the amount of water in John's glass changes when water
is transferred from Bill's glass to John's glass.
\section{Scenario 1: Alternating moves}
In this scenario, we move water from John's glass to Bill's glass, then
back again, and so on. The amount of water in John's glass, if it
starts with $x_0$, is given by the following table:
\vspace{10pt}
\begin{center}
\begin{tabular}{cc}
time & amount of water in John's glass\\\hline
0& $x_0$\\
1& $f(x_0)$\\
2& $g(f(x_0))$\\
3& $f(g(f(x_0)))$\\
4& $g(f(g(f(x_0))))$\\
$\vdots$ & $\vdots$\\
\end{tabular}
\end{center}
\vspace{10pt}
Because we are alternating between $f$ and $g$, it will be convenient
to define
\[h(x)=g(f(x))\]
which the reader can verify is
\[h(x)=(1-p)^2 x +p.\]
This function now describes the effect of moving water from John's
glass to Bill's glass, then back again. Thus after an even number of
moves, the amount of water in John's glass is
\[h(h(\dots h(h(x))\dots))\]
while the result of an odd number of moves is that John's glass has
\[f(h(h(\dots h(h(x))\dots))).\]
Let's first focus on what happens after an even number of moves. This
is thus a matter of examining the sequence
\[x_0, h(x_0), h^2(x_0), \dots.\]
First, note that $h(x)$ is a linear function of the variable $x$, and
the equation $h(x)=x$ can be solved as follows:
\begin{eqnarray*}
h(x)&=&x\\
(1-p)^2 x+p&=&x\\
p&=&x-(1-2p+p^2)x\\
p&=&(2p-p^2)x\\
x&=&\frac{1}{2-p}
\end{eqnarray*}
This means that the result of transferring water from John's glass to
Bill's glass and back will result in a return to the exact same state
precisely when $x=1/(2-p)$. Now since $p$ is between $0$ and $1$, we
see that $2-p$ is between $1$ and $2$, and so $1/(2-p)$ is between
$1/2$ and $1$. The graph of $h(x)$ in the unit square is as shown in
Figure~\ref{Strawpaper01}. Also shown in the figure is the line $y=x$, and it
intersects the graph of $h(x)$ at $(1/(2-p),1/(2-p))$. Note that the slope of $h(x)$ is $(1-p)^2$, which is between $0$
and $1$. Based on $h(0)=p$ and $h(1)=(1-p)^2+p=1-p+p^2=1-p(1-p)$, we
see that $h(x)$ on $[0,1]$ takes values between $0$ and $1$.
\begin{figure}[!h]
\begin{center}
\includegraphics{Strawpaper01.eps}
\caption{The amount of water in John's glass ($h(x)$) after moving water
from John's glass to Bill's and back again}
\label{Strawpaper01}
\end{center}
\end{figure}
\subsection{Graphical iteration}
A very convincing way to study what happens when we move water back and
forth is to use the graph in Figure \ref{Strawpaper01} and graphically determine what happens after one move of water with the straw, hereafter called a ''straw move''. We will study separately the case where we make an even number of straw moves and the case where we make an odd number of straw moves.
\vspace{.1in}
\underline{Even moves:}
To graphically determine the amount of water in John's glass after an even number of straw moves, start at the point $x$ on the
$x$-axis and obtain the point $(x, h(x))$ by drawing a vertical line up
to the function $h(x)$. This point has $y$-coordinate equal to $h(x)$,
which becomes the new value of $x$.
If we wish to do another iteration of water movement, we need to turn
this new $y$ value into an input, or $x$, value. To do this, first
find the corresponding point $(h(x), h(x))$ on the $y=x$ line by
drawing a horizontal line from the value $h(x)$ on the $y$-axis to the
graph of the function $y=x$. To obtain an $x$ value from this point,
simply draw a vertical line from the function $y=x$ down to the
$x$-axis. This will give us the equivalent value of the amount of
water in John's glass after one complete iteration, but along the
$x$-axis so we can use it as an input value.
To shorten this process,
we can begin at any point $x$ on the $x$-axis, find the corresponding
value of $h(x)$ by drawing a vertical line to the function $h(x)$, and
then turning this into an $x$ value by drawing a horizontal line to the
function $y=x$ and drawing a vertical line back down to the $x$-axis.
The value we find on the $x$-axis is $h(x)$. We now have performed one
iteration. This is done in Figure~\ref{Strawpaper02}.
\begin{figure}[!h]
\begin{center}
\includegraphics{Strawpaper02.eps}
\caption{Determing the amount of water in John's glass after one
complete iteration.}
\label{Strawpaper02}
\end{center}
\end{figure}
Continuing to iterate the water movement from John's glass to Bill's
glass and back, we obtain the graph in Figure \ref{Strawpaper03}, which shows
that the amount of water in John's glass approaches a limiting value,
which is the intersection point $x=1/(2-p)$, which as we mentioned
earlier, is bigger than $\frac{1}{2}$.
In this way, we can see the behavior of iterating $h$. Assuming $x$
starts out larger than $1/(2-p)$, after each iteration of $h$, $x$ will
be smaller and smaller, approaching $1/(2-p)$ from above. A similar
triangles argument shows that this convergence happens exponentially
fast. Now since this sequence is decreasing to $1/(2-p)$, which is
larger than $1/2$, we never reach $x=1/2$.
\begin{figure}[!h]
\begin{center}
\includegraphics{Strawpaper03.eps}
\caption{The amount of water in John's glass approaches a limiting
value as multiple iterations of water movement are performed.}
\label{Strawpaper03}
\end{center}
\end{figure}
\vspace{.1in}
\underline{Odd moves:}
Now we will use a similar graphical argument to understand what is happening after an odd number of moves. To do
this, we simply study the sequence of points obtained by the even
sequence $x_0, h(x_0), h(h(x_0)), \dots$, and apply $f(x)=(1-p)x$ to
each, as was mentioned before. The result will be the sequence of
amounts in John's glass after an odd number of moves. For this, we
need to study the function $f(x)$.
We note that since $1-p$ is between $0$ and $1$, we have that the
sequence of $x$ values after an odd number of moves, $f(x_0),
f(h(x_0)), f(h(h(x_0))), \dots$ is, term by term, less than the
sequence of $x$ values after an even number of moves. This is obvious
when you realize that this is the result of moving water from John's
glass to Bill's glass. But also, the sequence of $x$ values
corresponding to an even number of moves is a decreasing sequence
converging to $1/(2-p)$ from above. Since $f(x)$ is continuous and
monotonically increasing, this means that the sequence of $x$ values
after an odd number of moves is also a decreasing sequence, converging
to $f(1/(2-p))=(1-p)/(2-p)=1-1/(2-p)$.
Note that since $1/(2-p)$ is between $1/2$ and $1$, we see that
$1-1/(2-p)$ is between $0$ and $1/2$. This means that the odd sequence
decreases from $f(x_0)$ to $1-1/(2-p)$. It is possible that along the
way, we hit $1/2$ exactly, but generally the sequence may pass $1/2$
without hitting it exactly.
In summary, in the process of moving water from John's glass to
Bill's and back again, over and over, John's glass decreases, then
increases, then decreases, then increases, and so on, in such a way as
to decrease generally, with odd iterations decreasing to
$1-1/(2-p)<1/2$ and even iterations decreasing to $1/(2-p)>1/2$. The
odd iterations (i.e., the ones right after we transfer water from
John's glass to Bill's) are the only ones that might achieve $x=1/2$.
At the very least, it passes it on its descent to $1-1/(2-p)<1/2$.
\begin{figure}[h!]
\begin{center}
\vspace{.5in}
\includegraphics{Strawpaper04.eps}
\caption{The amount of water in John's glass as a function of time}
\label{Strawpaper04}
\end{center}
\end{figure}
John had asked if we would ever reach $x=1/2$. Why $1/2$? Perhaps John supposed that this procedure of transferring water back and forth would tend to stabilize the amounts in the glasses and so would bring the amount of water in each glass closer and closer to $1/2$, which is not true in general. In actual fact, the limiting situation is one in which the glasses oscillate between two states. The first state is one in which John's glass has $1/(2-p)$, and then after transferring water to Bill's glass the second state will be the one in which John now has $1-1/(2-p)$. Transferring water back to John's glass will bring John's glass back to $1/(2-p)$. In actuality, we approach both of these limits from above, and although the approach is exponential, it never quite reaches the limiting value. This is what people in dynamical systems call a ''limit cycle'' because it approaches not a limit but a cycle of (in this case two) situations (see Figure \ref{Strawpaper05}).
\begin{figure}[!h]
\begin{center}
\includegraphics{Strawpaper05.eps}
\caption{A graph of the ''limit cycle''.}
\label{Strawpaper05}
\end{center}
\end{figure}
\subsection{Finding if it reaches $1/2$}
But since John asked about $1/2$, not $1/(2-p)$, we might actually have
$x=1/2$, or not, on the way to the limiting situation. How can we know
if this happens? Intuitively, we might guess this is a very rare
situation, since iterating $h$ over and over gets a decreasing sequence
of points in $[0,1]$, but any given number in the interval, like $1/2$,
would probably not be hit.
One way to analyze this question is to work backward. We know that if
John's glass ever has $x=1/2$, it must be after an odd number of moves.
We therefore solve backward
\[f(x)=(1-p)x=1/2\]
to obtain
\[x=\frac{1}{2(1-p)}.\]
It is possible that this is the initial value of $x=x_0$. If so, we
will reach $x=1/2$ after one straw move. If $x<\frac{1}{2(1-p)}$, then
we will never reach $x=1/2$, since we have already passed it. On the
other hand, if $x>\frac{1}{2(1-p)}$, we will need to consider if we get
to $x=1/2$ after three moves, or five moves, and so on. To find this
out, we solve for $x$ in the following equation:
\[h(x)=\frac{1}{2(1-p)}.\]
Since
\[h(x)=(1-p)^2x+p,\]
the solution can be found as follows:
\begin{eqnarray*}
(1-p)^2x+p&=&\frac{1}{2(1-p)}\\
(1-p)^2x&=&\frac{1}{2(1-p)}-p\\
x&=&\frac{1}{2(1-p)^3}-\frac{p}{(1-p)^2}.
\end{eqnarray*}
More generally, we can define a sequence with
$a_1=1/2$, and
\begin{eqnarray*}
h(a_n)&=&a_{n-1}\\
(1-p)^2a_n+p&=&a_{n-1}\\
a_n&=&\frac{a_{n-1}-p}{(1-p)^2}
\end{eqnarray*}
Note that going backward in this iteration is not the same thing as a
straw move going in the other direction; we are indeed transferring
water back, but the amount we transfer going forward when moving water from John's glass to Bill's glass is determined by the amount
of water in John's glass currently; while the analogous motion when
solving the iteration backward is based on how much water will be in
Bill's glass at the end of the iteration.
To graphically determine what possible initial amounts of water $x$ and $1-x$ could
lead to attaining half of the water in each glass, one could simply
perform the procedure above in reverse. Start at the point $(0, 1/2)$ on the $y$-axis. Move horizontally to the graph of $y=f(x)$ and then vertically down to the $x$-axis to obtain the point $x_1 = \frac{1}{2(1-p)}$ (this represents the first
possible initial state from which it is possible to obtain half of the
water in each glass). Now move vertically from $x_1$ to the point
$y=x=\frac{1}{2(1-p)}$ on the line $y=x$ and move horizontally to the graph of $h(x)$. Note
that $1/(2(1-p))>1/(2-p)$, so this starting point is above the point of
intersection between the graph of $h(x)$ and $y=x$. Note also that the
graph of $h(x)$ takes values between $h(0)=p$ and $h(1)=1-p+p^2$. If
$x$ is smaller than $p$ or bigger than $1-p+p^2$, then this is
impossible and one will never obtain the state with half of the water
in each glass. Assuming that $x$ is between those values, though, then
it is possible to move horizontally to the graph of $h(x)$. From the
graph of $h(x)$, move vertically up to the $x$-axis. This value of $x$
represents another possible initial amount of water from which it is
possible to obtain half of the water in each glass. We then iterate this procedure. Depending on the value of $p$, it will
take a certain amount of time before we are in the situation that $x<0$
or $x>1$. When this happens, we stop, because there are no solutions
possible (see Figure \ref{Strawpaper06}). Geometrically, it seems likely that there is therefore for
any value of $p$, only finitely many initial values of $x$ that will
arise in this way. It is possible, in fact, to use a similar triangles
argument to see that this procedure results in an exponentially growing
sequence away from $1/(2-p)$, inasmuch as the ''forward'' sequence was
an exponentially decreasing sequence to $1/(2-p)$. Therefore, after a
finite number of steps, we end up outside the required interval.
As $p$ gets closer to zero, the number of possible initial volumes
increases and as $p$ gets closer to $\frac{1}{2}$ the number of initial
values decreases. If $p > \frac{1}{2}$, there are no possible initial
volumes because then $1/(2(1-p)) > 1$.
\vspace{.2in}
\begin{figure}[!h]
\begin{center}
\includegraphics{Strawpaper06.eps}
\caption{Possible initial water amounts that
will result in an even split of water.}
\label{Strawpaper06}
\end{center}
\end{figure}
\vspace{.2in}
\section{Scenario 2: If John's glass begins with less than $1/(2-p)$}
Where did we use the assumption that John's glass was fuller than
Bill's? When we analyzed the sequence of $x, h(x), h(h(x)), \dots$ and
saw that graphically, it decreased to $1/(2-p)$. This assumed we
started with $x_0 > 1/(2-p)$. If $x<1/(2-p)$, we can do the same
analysis to see that $x$ will increase to the limit of $1/(2-p)$.
One way to think about this is to reverse the roles of Bill's and
John's glasses. Of course, we are still starting by pouring water from
John's glass to Bill's, but from then on, the situation is the same,
with Bill's and John's glasses exchanged.
More specifically, if John's glass starts with $x_0$, we do one move so
that John's glass now has $f(x_0)=(1-p)x_0$, then look at what Bill's
glass has. Bill will have $1-(1-p)x_0$. If $x_0<1/(2-p)$, then Bill's
glass, will have $1-(1-p)x_0>1-(1-p)/(2-p)=1/(2-p)$, and we are in the
situation from the previous scenario.
We might ask which starting positions of this type could lead to
$x=1/2$. Luckily, $x=1/2$ is exactly the same under exchanging John's
and Bill's glasses, so we can study this case by looking at the finite
sequence of starting positions for John's glass, and stipulating that
it is Bill that starts with that quantity of water instead of John.
Then we will have a starting position with Bill's glass being fuller
than John's, and resulting in $x=1/2$ after a finite number of steps.
Finally, what if the starting position is $x_0=1/(2-p)$? Then a straw
move from John's glass to Bill's brings us to $1-1/(2-p)$, while the
next straw move from Bill's glass to John's returns us back to
$x=1/(2-p)$.
\subsection{Come on, now. Really.}
In the previous section we made a distinction between $x=1/2$ and
$x=1/(2-p)$. How far apart are
these, really, and would anyone really notice? Or to make the
objection a bit more serious, we have clearly neglected a few
considerations. Water is made up of molecules, and so we cannot have a
continuum of values for $x$. And furthermore, water has surface
tension, which we did not analyze. Although these are small effects,
so is the precision with which we are describing this limiting process.
In light of this, should we really answer John and Bill's question the
way we have?
In an attempt to determine the real-life answer to the problem, we took a standard straw and a somewhat standard water glass and found the value of $p$ to be approximately $.015$. For this value of $p$, $1/(2-p) = .5038$ (rounding to four decimal places) which is so close to $1/2$ that it is likely not distinguishable to the human eye. Thus the fact that the limiting situation is the oscillation between $1/(2-p) = .5038$ and $1-1/(2-p) = .4962$ may appear to the naked eye as having reached an equilibrium state where both glasses have $1/2$ of the water.
\subsection{A more elegant example}
As the authors are theoretical, not applied, mathematicians, we found
it was more fun not to talk about straws in real life but rather cases
that were mathematically beautiful. In the special case that $x_0=1$
and $1-x_0=0$ and $p=\frac{1}{2}$ (This is a rather large straw!) we
obtain an interesting pattern by alternating the movement of water
between the two glasses. If we express the volume of water in binary
form, we obtain the following:
\[
\begin{array}{ccc}
&{\text {John's Glass}}&{\text {Bill's Glass}}\\
{\text {Starting position}}&1.000000\dots&0.000000\dots\\
{\text {Iteration 1}}&0.100000\dots&0.100000\dots\\
{\text {Iteration 2}}&0.110000\dots&0.010000\dots\\
{\text {Iteration 3}}&0.011000\dots&0.101000\dots\\
{\text {Iteration 4}}&0.101100\dots&0.010100\dots\\
{\text {Iteration 5}}&0.010110\dots&0.101010\dots
\end{array}
\]
We see that if $k$ is odd, then on the $k$th iteration we have
$0.1010\cdots01100\cdots$ in Glass $A$, where the last $1$ is in
position $k$, and $0.010101\cdots01000\cdots$ in Glass $B$, where the
last $1$ is in position $k$. If $k$ is even, then on the $k$th
iteration we have $0.01010\cdots01100\cdots$ in Glass $A$, where the
last $1$ is in position $k$, and $0.10101\cdots01000\cdots$ in Glass
$B$, where again the last $1$ is in position $k$.
Note that we do reach $1/2=0.1000$ after one iteration. In fact
$x_0=1$ and $x_0=0$ are the only starting positions that will lead to
$x=1/2$.
The interested reader may be interested in investigating similar
results for ternary and higher $n$-ary expansions with initial water
amounts in John's glass of $\frac{1}{3}$, or, in general, $\frac{1}{n}$.
\section{Further reading}
Students who wish to read a further exposition of problems involving
the method of cobwebs, which we found useful in our paper, are referred
to the books {\underline{A First Course in Chaotic Dynamical Systems}}
by R. Devaney (Chapters 4 and 5) and {\underline{Understanding
Nonlinear Dynamics}} by D. Kaplan and L. Glass. Students may also be
interested in reading the article ''Clarifying Compositions with
Cobwebs" by N. Neger and M. Frame which appears in the College
Mathematics Journal, Vol. 34, No. 3 (May 2003).
Unfortunately, the author was not able to present her mover, John, with
this solution amidst the hectic mess of packing, moving and unpacking,
but hopes that somewhere, somehow he will be able to read it as he sits
at another Truck Stop facing another water glass dilemma.
\newpage
\begin{figure}[h!]
\begin{center}
\includegraphics{Strawpaper07.eps}
\end{center}
\end{figure}
\end{document}