I am reading a computer science puzzles book.

And I get the following question -

"You have a five quart jug, a three quart jug and unlimited supply of water. How would you come up with exactly four quarts of water ?"

The question is pretty simple and I figured the sequence of "water transfers" to solve it.

But there was an interesting side-note that I did not know.

The side-note said that as long as the two jugs size relatively prime, it is possible to find a pour sequence for any value between one and the sum of the jug sizes.

It is true for 5 and 3.

But I want to know if it is really generally true or not ? If it is, it is really cool! What is the theorem called ? Who discovered it ?


Let two wine glasses A and B have capacities $a$ and $b$ ounces, where $a$ and $b$ are relatively prime positive integers, and $a\lt b$. Suppose we also have a large open barrel full of wine. We will show that for any integer $w$, where $0\le w\le b$, we can measure out $w$ ounces of wine. (This means that we can measure out any integer number $y\le a+b$ of wine ounces, as long as we don't mind the stuff being possibly in two glasses. I don't.)

It is enough to show that for any $r$, with $0\le r\lt a$, we can measure out $r$ ounces. For $w=qa+r$ for some $r$ between $0$ and $a-1$. So if we can measure out $r$ ounces, we can put this into B, and then get to $w$ by using glass A $q$ times.

The construction goes as follows. Suppose that at a certain stage we have $x_k$ ounces of wine in cup A. Fill cup B from the barrel, top up cup A from cup B, pour the contents of A into the barrel, or better, drink it. Keep on filling A from cup B, dumping the contents of A into the barrel when A gets full. After a while, the amount left in B will be insufficient to fill A, but pour it in anyway. Call the amount that is now in A by the name $x_{k+1}$. Then $$b=(a-x_k)+an+x_{k+1}$$ for some integer $n$. It follows that $$x_{k+1}\equiv x_k +b\pmod{a}.$$ Start with A empty, that is, with $x_0=0$. Then $x_1\equiv b\pmod{a}$, $x_2\equiv 2b\pmod{a}$, and so on.

But since $a$ and $b$ are relatively prime, the numbers $0,b,2b.3b,\dots, (a-1)b$ form a complete residue system modulo $a$. Thus the sequence $x_0,x_1,x_2,\dots,x_{a-1}$ runs, in some order, through all the numbers from $0$ to $a-1$. This completes the proof.

  • $\begingroup$ I get it now.... Thanks. Any idea who first discovered the fact and proved it ? $\endgroup$ – anu Jan 21 '14 at 7:57
  • $\begingroup$ No idea. This is a proof I wrote out a number of years ago for a number theory course I was teaching. There are undoubtedly neater arguments, and the result has probably been known for a century or more. It is likely that many people have written out proofs. $\endgroup$ – André Nicolas Jan 21 '14 at 8:03
  • $\begingroup$ Okay. Fair enough. Thanks for the concrete proof and logic behind it. $\endgroup$ – anu Jan 21 '14 at 8:06
  • $\begingroup$ You are welcome. I hope the bits of number theory were not a problem. In the same way, one can show that if $d=\gcd(a,b)$ we can measure out precisely the multiples of $d$ that are $\le b$. $\endgroup$ – André Nicolas Jan 21 '14 at 8:08
  • $\begingroup$ Brilliant, but the I don't alone would have been enough for you to deserve a +1. $\endgroup$ – Andreas Caranti Jan 21 '14 at 12:58

Yes, it is true. From Diophantine Equations on Wikipedia

The simplest linear Diophantine equation takes the form ax + by = c, where a, b and c are given integers. The solutions are completely described by the following theorem: This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b. Moreover, if (x, y) is a solution, then the other solutions have the form (x + kv, y - ku), where k is an arbitrary integer, and u and v are the quotients of a and b (respectively) by the greatest common divisor of a and b.

Look at the Wikipedia article for more details of a proof.

To try to connect things, consider the equation: 5x+3y=4 as x could represent the number of filling or emptying of the 5 quart jug while y represents the same thing for the 3 quart jug. If there was a common factor between these, this could be factored out so that any answer would be a multiple of that integer. Given that a solution is (2,-2) to that Diophantine equation, this could imply that one fills the 5 quart jug and empties it over the 3 quart jug a couple of times to get exactly 4 quarts assuming one has another container to hold the 4 quarts.

I'll admit that I've seen this problem from Die Hard 3, so I know of an alternate solution.

Consider the case where there is a common factor between the jug sizes where one has jugs of size 8 and 12. Now, the greatest common divisor of 8 and 12 is 4 and thus any combination of pourings will leave you with a multiple of 4 for an answer as 8x+12y=4(2x+3y) and thus while one can easily solve 2x+3y=1, it is a bit different to solve 4(2x+3y)=1 where x and y are integer values as no solutions exist here.

In contrast, consider that if for a given pair of jug sizes that one can get exactly 1 of the unit then this could be repeated for any Natural number greater than 1 so to get any other value is rather easy if you can get 1.

The first part of my answer covers this in a general case, but for the sake of argument let's take $5x+3y=z$. If $z=1$ then by inspection I can notice that x=-1,y=2 is a solution. There are many solutions as one could take that solution and make the parametrized solution of $x=-1+k,y=2-k$ for k being any integer. Now, if z is some other value, I could just multiply the initial solution to get that value. Thus, if $z=4$ then $x=-4,y=8$ is a solution which works as $5*(-4)+3*8=-20+24=4$.

This last part is fairly trivial to my mind if you remember that one can take an equation and multiply both sides by a non-zero value and maintain equality.

  • $\begingroup$ That doesn't prove there is a sequence of pours that can yield the value. $\endgroup$ – Thomas Andrews Jan 21 '14 at 5:50
  • $\begingroup$ Wow, okay. But I don't even understand how the two things are related...More specifically, I can't see how finding a solution to the equation translates to the pour. And Moreover the equation talks about any integer and not relatively prime numbers ... So I am confused. Can you explain this in a simpler way, so that it is intuitive ? I am genuinely curious about this ... Thank you. $\endgroup$ – anu Jan 21 '14 at 5:52
  • $\begingroup$ Okay. This is also interesting, but the thing I wanted the proof was something of the effect ... if we consider the equation 5x + 3y = z we need to prove that 1 <= z <= (5+3) ... $\endgroup$ – anu Jan 21 '14 at 8:03

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.