Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a well-known problem involving a water barrel and a wine barrel, described here. The trick to solving the puzzle is that one need not make the calculations for each stage of the liquid movement. But if one does...

The units here are the quantity of liquid moved each time, e.g. cupfuls. At the end of each "take out/put back" movement, the amount of wine in one barrel is the same as the amount of water in the other, so we can consider just the two volumes of liquid without caring about what they are made from.

At the beginning the two volumes are $0$ and $n$, say.

After the first movement the volumes are $$\frac{n}{n+1}\text{ and }\frac{n^2}{n+1}.$$ After the second the volumes are $$\frac{n(2n)}{(n+1)^2}\text{ and }\frac{n(n^2+1)}{(n+1)^2}.$$ After the third the volumes are $$\frac{n(3n^2+1)}{(n+1)^3}\text{ and }\frac{n(n^3+3n)}{(n+1)^3}.$$ There is a pattern here suggesting that after $t$ goes the volumes are
$$\frac{n}{(n+1)^t}\sum_{k=0}^{t/2-1}{\binom{t}{t-2k}n^{2k}}$$ and $$\frac{n}{(n+1)^t}\sum_{k=0}^{t/2}{\binom{t}{t-2k-1}n^{2k+1}}.$$ As more liquid is moved the two volumes will each start to approach $\dfrac{n}{2}$.
To my question: how do we show that the two volumes above both tend to $\dfrac{n}{2}$ as $t\rightarrow\infty$?

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

The upper limits on the summations should be $\lfloor t/2 \rfloor$ and $\lceil t/2 \rceil$, and you can simplify the binomial coefficients to get $$\frac{n}{(n+1)^t}\sum_{k=0}^{\lfloor t/2 \rfloor}\binom{t}{2k}n^{2k}\text{ and }\frac{n}{(n+1)^t}\sum_{k=0}^{\lceil t/2 \rceil}\binom{t}{2k+1}n^{2k+1}.$$

Now $$(n+1)^t = \sum_{k=0}^t \binom{t}{k}n^k\text{ and }(n-1)^t = \sum_{k=0}^t\binom{t}{k}(-1)^{t-k}n^k,$$ so $$\begin{align*} \frac12\left((n+1)^t+(n-1)^t\right) &= \frac12\sum_{k=0}^t\binom{t}{k}\left((1+(-1)^{t-k}\right)n^k\\ &= \begin{cases} \sum_{k=0}^{\lfloor t/2\rfloor}\binom{t}{2k}n^{2k},&\text{if }t\text{ is even}\\ \sum_{k=0}^{\lceil t/2\rceil}\binom{t}{2k+1}n^{2k+1},&\text{if }t\text{ is odd}, \end{cases} \end{align*}$$ and $$\begin{align*} \frac12\left((n+1)^t-(n-1)^t\right) &= \frac12\sum_{k=0}^t\binom{t}{k}\left((1-(-1)^{t-k}\right)n^k\\ &= \begin{cases} \sum_{k=0}^{\lfloor t/2\rfloor}\binom{t}{2k}n^{2k},&\text{if }t\text{ is odd}\\ \sum_{k=0}^{\lceil t/2\rceil}\binom{t}{2k+1}n^{2k+1},&\text{if }t\text{ is even}. \end{cases} \end{align*}$$

It follows that $$\sum_{k=0}^{\lfloor t/2\rfloor}\binom{t}{2k}n^{2k} = \begin{cases} \frac12\left((n+1)^t+(n-1)^t\right),&\text{if }t\text{ is even}\\ \frac12\left((n+1)^t-(n-1)^t\right),&\text{if }t\text{ is odd} \end{cases}$$

and $$\sum_{k=0}^{\lceil t/2\rceil}\binom{t}{2k+1}n^{2k+1} = \begin{cases} \frac12\left((n+1)^t+(n-1)^t\right),&\text{if }t\text{ is odd}\\ \frac12\left((n+1)^t-(n-1)^t\right),&\text{if }t\text{ is even}. \end{cases}$$

(This is a useful trick to bear in mind when you have alternate binomial coefficients.)

Thus, for every $t$ the numbers $$\frac{n}{(n+1)^t}\sum_{k=0}^{\lfloor t/2 \rfloor}\binom{t}{2k}n^{2k}\text{ and }\frac{n}{(n+1)^t}\sum_{k=0}^{\lceil t/2 \rceil}\binom{t}{2k+1}n^{2k+1}$$ are $$\frac{n}{2(n+1)^t}\left((n+1)^t+(n-1)^t\right)\text{ and }\frac{n}{2(n+1)^t}\left((n+1)^t-(n-1)^t\right)$$ in one order or the other. These are $$\frac{n}{2}\pm\left(\frac{n-1}{n+1}\right)^t = \frac{n}{2}\pm\left(1-\frac2{n+1}\right)^t,$$ which clearly approach $\dfrac{n}2$ as $n\to \infty$.

share|improve this answer
add comment

If you have $\frac{n}{2}+w$ water in the water tank before a transfer, after a transfer each direction you have $\frac{n}{2}+w\frac{n-1}{n+1}$, so $w$ is driven to zero.

share|improve this answer
add comment

The sums you write can be evaluated in closed forms: $$ \frac{1}{(n+1)^t} \sum_{k=0}^{t/2} \binom{t}{t-2k} n^{2k+1} = \frac{1}{(n+1)^t} \sum_{k=0}^{t/2} \binom{t}{2k} n^{2k+1} = \frac{n}{2} \left( 1 + \frac{(1-n)^t}{(n+1)^t} \right) $$ from which the property you seek to establish is apparent.

Now to establish the formula $$ \sum_{k=0}^{t/2} \binom{t}{2k} n^{2k+1} = \sum_{k=0}^{t} \frac{1}{2}\left(1 + (-1)^k \right)\binom{t}{k} n^{k+1} = \frac{n}{2}\left( (n+1)^t + (1-n)^t \right) $$

share|improve this answer
    
Ross, Brian and Sasha, Thanks very much. –  Peter Phipps Sep 30 '11 at 18:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.