2
$\begingroup$

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$?

  • 0
    Bezout's identity shows that you can get 1 liter. The rest is easy.2012-07-08

2 Answers 2

3

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$.

  • 0
    The problem was for any positive integer $m$.2012-07-08
4

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$.

  • 0
    Thank you for your answer!2012-07-08