# Euclidean Algorithm Problem

Given two cups holding 16oz. and 25oz. and enough water, how can you measure out exactly 3 oz. of water?

It is easy to get $3=8\times16-5\times25$. But after thinking for a long time, I still fail to measure out 3 oz. of water without spilling... I really don't know how to use the two cups effectively.

-
I'm curious, how did you get $3=8\times16-5\times25$ from the Euclidean Algorithm? I tried the EA and got $1=11\times16-7\times25$. Thanks. – Jeff Jan 30 '12 at 3:06
He either subtracted $25\times 16$ from the solution, to make it optimal, or more probable he solved the problem by solving the equation $3=25x=9x \mod 16$. Note that it is very easy to guess the solution here, since $3$ is invertible and $3\times 5 =-1 \mod 16$. – N. S. Jan 30 '12 at 16:03

Look at the general problem. Cup A has capacity $a$ ounces, cup B has capacity $b$ ounces, where $a$ and $b$ are integers, $a<b$, and $\gcd(a,b)=1$. We also have an open tank full of water. (Mustn't throw water away, that's unsustainable.) We can assume that $a>1$, else the problem is trivial.

We want to show that for any integer number $n$ of ounces, where $n\le b$, we can end up with exactly $n$ ounces in cup B.

It is enough to show that for any integer $r$, with $1\le r\le a-1$, we can end up with $r$ ounces in cup A. Let $n=qa+r$, where $0\le r\le a-1$. If we can end up with $r$ ounces in cup A, dump that into B, and then $q$ cupfuls from A, and we end up with $n$ ounces in cup B.

Let $r_0=0$. Suppose that at the end of a certain stage $k$, we have $r_k$ ounces in cup A. The $k+1$-th stage goes as follows. Fill B from the tank, top up A from cup B, dump the contents of A into the tank, fill A from cup B, dump the contents of A into the tank, fill cup A from cup B, and so on. After a while, when we pour the contents of B into A, there is no more water in B. Call the amount of water then in A by the name $r_{k+1}$. Then $b=(a-r_k)+am+r_{k+1}$ for some integer $m$, and therefore $r_{k+1}\equiv r_k +b \pmod{a}$.

Since $r_0=0$, at the end of the first stage we have $r_1\equiv b \pmod{a}$, at the end of the second stage we have $r_2\equiv 2b \pmod{a}$, and so on, until at the end of the $a-1$-th stage $r_{a-1}\equiv (a-1)b \pmod{a}$.

Since $a$ and $b$ are relatively prime, the numbers $b, 2b, 3b,\dots, (a-1)b$ are pairwise incongruent modulo $a$, and none of them is congruent to $0$ modulo $a$. Thus as $k$ travels from $1$ to $a-1$, the $r_k$ travel, in some order, through all the integers from $1$ to $a-1$. Thus all these numbers are achievable in A. This completes the proof.

-

The process you undergo to measure out the desired amount (3 oz.) is done by filling the smaller container (16 oz.), dumping as much as possible into the larger container, and repeating until the larger container is full. When the larger container is full, dump it out and repeat. After the smaller container has been filled 8 times and the larger container has been emptied 5 times, you will be left with 3 oz. in the smaller container. Consider the following sequence of steps (x, y), where x represents the amount in the 16 oz. container, and y represents the amount in the 25 oz. container.

$$(0,0) \rightarrow (16,0) \rightarrow (0, 16) \rightarrow (16, 16) \rightarrow (7, 25)$$

At this point we dump the larger container.

$$(7, 0) \rightarrow (0, 7) \rightarrow (16,7) \rightarrow (0, 23) \rightarrow (16, 23) \rightarrow (14, 25)$$

Again we dump the larger container.

$$(14,0) \rightarrow (0, 14) \rightarrow (16, 14) \rightarrow (5, 25)$$

Dump the larger container.

$$(5, 0) \rightarrow (0,5) \rightarrow (16, 5) \rightarrow (0, 21) \rightarrow (16,21) \rightarrow (12, 25)$$

You know the drill by now.

$$(12,0) \rightarrow (0,12) \rightarrow (16, 12) \rightarrow (3, 25)$$

Dump the larger container, and you are left with $$(3,0)$$.

-

Call the cups 16 and 25 (for obvious reasons). Fill 25, then from this, fill the other one. This leaves you 9 oz in 25. Discarding the water from 16, pour the 9oz into it. Now refill 25, and from this, fill 16 the rest of the way, leaving you with 18 in 25. Empty 16 again, and fill it from the 18 in 25, leaving you with 2 in 25. Move these 2 to 16, refill 25, and then finish filling 16 to leave you with 11 in 25. Move these 11 to 16, then fill 25 and from it, refill 16 all the way, leaving you with 19 in 25. Now empty 16 and fill it from these 19, leaving you with 3 ounces of water in 25.

-