2
$\begingroup$

Initially, I have $3$ cups with infinite capacity and some prefilled amount of water(positive integers). I can do only one operation repeatedly by choosing any $2$ out of $3$. The operation is that if you have $2$ cups with volume $a$ and $b$ and $a <= b$, then the operation changes the volume as $b-a$, $2*a$. Basically, it pours the liquid from the more filled cup to the less filled cup by the same amount that it had initially. My goal is to empty any $1$ cup and see if it is possible for all initial cases. Now, if I had $2$ cups, the answer turns out to be that if the sum of the volumes of the cups is of the form $2^N$, then $1$ of the cups will eventually become empty, otherwise, it gets stuck in a loop. I need to generalize this to $3$ cups. Also, you can factor out gcd of the numbers in the beginning as that will remain constant.

P.S:- I was given this problem by a professor at my college. I initially put it on math stack exchange(https://math.stackexchange.com/questions/3490299/puzzle-regarding-emptying-of-cup) but this seemed like a better place to ask.

$\endgroup$
4
  • 1
    $\begingroup$ If you have the prof's permission to post the puzzle on the internet, it's enough if you say so, we don't demand any proof beyond that. (Because saying that you have permission when you actually don't would be much worse than just "common" copyright infringement; no sensible person would knowingly take such a risk.) $\endgroup$
    – Bass
    Nov 5 '20 at 20:44
  • $\begingroup$ @bobble this is just for fun and it was given to us like 2 years ago. $\endgroup$ Nov 6 '20 at 20:07
  • $\begingroup$ @hexomino as mentioned, you should take out the gcd first. So, the numbers after taking out the gcd are 1,3 which when summed forms 4 $\endgroup$ Nov 7 '20 at 12:09
  • $\begingroup$ @RishabhJain Oh, I see what you mean, will delete. $\endgroup$
    – hexomino
    Nov 7 '20 at 12:12
4
$\begingroup$

Let's first take the case of $2$ cups. As you have observed, we can 'take out' the GCD, so it's enough to assume the GCD of the two volumes is $1$ in the beginning. Now here's the key trick:

Every operation either keeps the GCD the same or doubles it.

This is not too hard to prove. Suppose we go from $(a,b)$ to $(2a,b-a)$. Then

$\gcd(a, b-a)$ is the same as $\gcd(a,b)$ because of how the Euclidean algorithm works, and doubling one of the numbers can only double the GCD or not affect it at all.

It's also clear that the total volume of water stays the same. But at the end, the volumes in the two cups must be $0$ and the total, in some order,

so the final GCD is equal to the total! But as we saw, the GCD starts at $1$ and can only double or stay the same, so the eventual GCD must be a power of two. Thus the total volume has to be a power of two.

We are not quite done yet. It remains to show that operation is indeed possible if the total volume is $2^N$. For this, let's use

induction on $N$. The base case $N=0$ is clear: so suppose in general we have a situation where the total is $2^N$, $N>0$. We can always make sure both volumes are even: indeed, if it isn't so already, perform the operation once, and we get even integers in both cups. But remember the very first observation: we can take out GCDs! If we halve both integers (in other words, work with a different unit of volume that's double the original), we end up with an identical situation, except the sum is now $2^{N-1}$, and this is solvable by the induction hypothesis. We are done!

The case of $3$ cups turns out to be quite different; in fact:

It's possible to make one of the cups empty starting from any configuration!

Here's a proof.

Call the quantities $x\le y\le z$ in cups 1,2 and 3. The idea is to reduce $y$ by the largest multiple of $x$ we can, in effect perfroming the Euclidean algorithm. If this works out, then the second cup will have the remainder when $y$ is divides by $x$, so this process reduces the minimum of the three volumes. Do this over and over again, and the minimum is going to hit zero eventually.

To make this happen, let's

write $y=qx+r$. We want to transfer the $qx$ amount into cup 1, which contains $x$. But every move can only double the cup that the water is getting moved into, so $q$ may not always be easy.

This motivates the following trick.

Write $q$ in binary. Say as an example $q=1101_2$. Then $y$ can be written as $x+4x+8x+r$. We start with the scenario $x,x+4x+8x+r,z$ and make the following moves:

  • Move from cup 2 to cup 1. This leaves $2x,4x+8x+r,z$.
  • Move from cup 3 to cup 1. This leaves $4x,4x+8x+r,z-2x$.
  • Move from cup 2 to cup 1. This leaves $8x,8x+r,z-2x$.
  • Move from cup 2 to cup 1. We end up with $16x,r,z-2x$. Yay!

The general process should be clear from this. Essentially,

We write $q$ in binary, and starting from the rightmost bit, move from cup 2 to cup 1 if the bit is $1$, and move from cup 3 to cup 1 if the bit is $0$. The assumption $y\le z$ gurantees that we don't run out of water in cup 3 before the process ends. This lets us get $r$ in the second cup. Next, we can repeat this until the smallest voume hits zero.

$\endgroup$
2
  • $\begingroup$ Thank you very much for your answer. This puzzle has haunted me for a long time. I was able to prove the case for 2 cups myself rigorously using a different method. It would be great if you can also shed some light on your thinking process in getting the answer for 3 cups, basically how you went about the puzzle. Was it knowledge, intuition or practice? $\endgroup$ Nov 10 '20 at 18:02
  • 1
    $\begingroup$ I'd say it's a combination of intuition and having seen similar problems before. I tried to work backward from the final scenario (0,x,?) and realized that situations like (x,x,?), (x,3x,?), (x,7x,?) could be easily resolved by removing powers of two in succession. This motivated the idea of writing $q$ as a sum of powers of two, and the rest eventually fell into place. $\endgroup$
    – Ankoganit
    Nov 11 '20 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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