Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The problem is:

Show that it is possible to measure any integral number of litres using only a $3$ litre and a $7$ litre jug.

And then the book says it's true that given $r$ and $s$ litre jugs, $m$ litres of water can be measured for any positive integer $m$. It's seems trivially true but I don't know how to "show" it. Doesn't it hold on the condition that $(r,s)=1$?

share|improve this question
2  
Yes. the condition on $\gcd$ is necessary. Say, if $r$ and $s$ are both even, you will never get an odd number to come out. Proof? Bezout's identity? –  Jyrki Lahtonen Jul 8 '12 at 8:28
    
@JyrkiLahtonen: Umm, so I should use Bezout's identity to show that? –  Gigili Jul 8 '12 at 9:43
    
Bezout's identity shows that you can get 1 liter. The rest is easy. –  Jyrki Lahtonen Jul 8 '12 at 10:16

2 Answers 2

up vote 3 down vote accepted

We put stringent conditions on the equipment we have, and show that we can still do it. We have two jugs, $A$ and $B$, a large barrel full of water, and no other container. (An additional container makes the problem too easy, for then we only need to know how to do $1$ litre.)

Jug $A$ can hold $a$ litres of water, and jug $B$ can hold $b$ litres, where $a$ and $b$ are relatively prime integers, and $a \lt b$. We show that for any non-negative integer $x\le b$, we can end up with $x$ litres of water in jug $B$.

The main problem is to show that for any positive integer $r\lt a$, we can end up with $r$ litres in jug $A$. For $x=qa+r$ for some non-negative quotient $q$ and remainder $r$ where $0\le r\lt a$. If we can achieve $r$ in jug $A$, we can achieve $x$ in $B$ by pouring the contents of $A$ into the emptied jug $B$, and adding $q$ jugfuls from $A$.

We now proceed to the construction of any desired $r$ in jug $A$, by providing an explicit algorithm.

Let $r_0=0$. Suppose that at a certain Stage $k$, we have $r_k$ litres of water in jug $A$. Fill $B$ from the barrel, top up $A$ from $B$, pour the contents of $A$ back into the barrel. If there is water left in $B$, keep filling $A$ from $B$, and emptying $A$ into the barrel whenever $A$ is full.

After a while, the amount that remains in $B$ is not enough to fill $A$. Put it into $A$ anyway. Call the amount we now have in $A$ by the name $r_{k+1}$, the amount at Stage $k+1$.

Then $b=(a-r_k)+an+r_{k+1}$ for some integer $n$. In congruence notation, we have $r_{k+1}\equiv r_k+b \pmod{a}$. Since $r_0=0$, we have $r_1\equiv b\pmod{a}$, $r_2\equiv 2b\pmod a$, and in general $$r_k\equiv kb\pmod{a}.$$

Since $a$ and $b$ are relatively prime, the set $\{0,b,2b,3b,\dots, (a-1)b\}$ is a complete residue system modulo $a$. Thus the sequence $r_0,r_1,\dots, r_{a-1}$ runs, in some order, through the numbers $0,1,2,\dots, a-1$. It follows that for any $r$ with $0 \le r \lt a$, there is a $k$ such that at Stage $k$ we have $r$ litres in jug $A$.

Note that the $k$ for which we have $r_k=r$ at Stage $k$ is obtained by solving the congruence $kb\equiv r\pmod{a}$. That provides the stopping rule for the algorithm.

Suppose that $d=\gcd(a,b)$, and let $x\le b$ be any non-negative integer multiple of $d$. A minor modification of the argument shows that we can end up with $x$ in $B$.

share|improve this answer
    
The problem was for any positive integer $m$. –  copper.hat Jul 8 '12 at 20:02

I'm not exactly sure what you are asking, but if you fill the 7 litre jug and then fill the 3 litre jug from the 7 litre jug twice (emptying in between, of course), you will be left with 1 litre in the 7 litre jug.

This allows you to measure out 1 litre. For n litres, repeat the process n times.

This, of course, comes from the fact that $1 \cdot 7-2 \cdot 3 = 1$.

share|improve this answer
    
That's not what I am asking, I already knew that. It's a high school level maths. –  Gigili Jul 8 '12 at 9:30
    
If $\gcd(r,s)=1$, then the Bezout identity shows the existence of $a,b$ such that $a r + b s = 1$. Suppose $a>0$, then fill up another container with the $r$ jug $a$ times. Then remove the $s$ jug $b$ times. This will leave $1$ litre. Repeat the process $m$ times. Explicit enough for you? –  copper.hat Jul 8 '12 at 9:46
    
And there is no need to get snippy. In my day the Euclidean algorithm was considered high school maths. So what was it you were asking? –  copper.hat Jul 8 '12 at 9:48
    
My question is what I posted above. You comment answers the question much better than your answer. And yes, there is no need to get snippy. –  Gigili Jul 8 '12 at 10:03
    
Thank you for your answer! –  Gigili Jul 8 '12 at 10:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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