Subscribe via feed.

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 v0(0) ≥ v0(1) ≥ v0(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.


This post is under “Tom” and has 5 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

5 Responds so far- Add one»

  1. 1. Chris Said:

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

  2. 2. Zorglub Said:

    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.

  3. 3. Chris Said:

    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.

  4. 4. Zorglub Said:

    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…

  5. 5. Chris Said:

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

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0