## Communicating recipients

Posted by Zorglub on January 16, 2015 – 2:22 pm

Three recipents R(0), R(1) and R(2) each contain an integer volume v_{0}(0) ≥ v_{0}(1) ≥ v_{0}(2) ≥ 1. Each recipient is large enough to contain the combined volumes. You are allowed to transfer some liquid from one recipient to another, only if the receiving one doubles its volume. Show that there is always a way to empty out one recipient in finitely many steps.

Example: If the initial volumes are 17, 8, 5 the sequence of volumes could be

R(0) R(1) R(2)

17 8 5

17 3 10

17 6 7

17 12 1

16 12 2

14 12 4

14 8 8

14 16 0 => R(2) is finally empty.

January 17th, 2015 at 6:11 am

Nice problem. It’s hurting my brain. I suspect that Bezout’s identity might be involved.

January 17th, 2015 at 1:49 pm

I stumbled on this problem on the web, and it turned out to be much more interesting and difficult than I thought at first glance.

Chris, I did not use Bezout’s identity. I don’t see how it could be used.

January 19th, 2015 at 3:23 pm

Hi Zorglub. It was only a suspicion. The fact that it can take several transfers seems to me to be a big hint that some clear thinking is needed.

January 21st, 2015 at 10:36 am

Here is a hint:

Find a way to pour R(0) and R(1) into R(2) in such a way that R(1) ends up with a volume strictly less than v0(2).

Then, reorder the recipients and apply this method recursively…

January 22nd, 2015 at 1:36 am

Please don’t give the solution yet. I will have a go. I’ve just had too many other things to do.