Sharing jugs of wine

✍ Scribed by Colin J.H. McDiarmid; Jorge Ramirez Alfonsin

• Book ID: 103060482
• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 512 KB
• Volume: 125
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)90169-4

✦ Synopsis

Two people have a full B-gallon jug of wine and two empty jugs of capacity M and S, respectively, where B= M +S. Any jug may be poured into any other jug until either the first one is empty or the second is full. What is the quickest way for them to divide the wine equally? We solve this problem and show that a natural related problem may be solved in polynomial time. Theorem 1.1. It is possible to share equally zy and only if B is divisible by 2r, where r=gcd(M, S). If this is the case, then the least number of pourings is (l/r)B-1, and the