GCD Euclid’s algorithm as solution to the 2-buckets water puzzle

euclidean-algorithmgcd-and-lcmpuzzle

I completed an exercise on HackerRank, a site for programming exercises. The problem has been inspired from Die Hard 3 movie. The original problem is like the following.

The problem

You are given two buckets with capacity $5$ (bucket A) and $3$ liters (bucket B); you must obtain exactly $4$ liters of water (there is a fountain somewhere). The procedure is the following:

  1. fill bucket A from the fountain completely: A=5,B=0
  2. fill the bucket B with the water in bucket A: B=3 and A=2
  3. empty bucket B: A =2, B=0
  4. fill bucket B with the water in A: A=0, B=2
  5. refill bucket A from the fountain: A=5, B=2
  6. fill bucket B with the water in A: A=4, B=3

Now changing the capacity values (let me call them c1 and c2) of the $2$ buckets and the desired final value (let me call it d), sometimes this problem has a solution sometimes it doesn't.

The solution

It turns out it has a solution when two conditions are satisfied (at least according to the HackerRank website and some users):

  1. at least one of the buckets has a capacity larger than the final desired quantity: c1>d OR c2>d
  2. calling gcd the greatest common divisor between c1 and c2, it must be that the reminder of the division d/gcd is 0.

I discovered Euclid's algorithm and this implementation in the C programming language and everything worked out. The Euclid's algorithm to find the greatest common divisor, has the following procedure (let me assume c1>c2 and let r be the reminder at each step of the division c1/c2):

while c2>0 do:
    r = c1 % c2
    c1 = c2
    gcd = c2
    c2 = r
return gcd

gcd variable will hold the value representing the greatest common divisor.

My questions

However I am left with two questions, one about the problem and the other about Euclid's algorithm (they might be related):

  1. why does the second condition (the one about the greatest common divisor) guarantee to tell if a solution exists for such a problem? Can anyone make the passage explicit?
  2. Can you make explicit why Euclid's algorithm results in the GCD? It looks like magic to me.

Sorry if my question is quite long but I tried to give every piece of information.

Best Answer

All numbers are integers in the following unless stated otherwise.

Answer to your first question:

Assume that $\gcd(c_1,c_2)= a$ then by Bézout´s identity we have that there exists $m,n\in\mathbb{Z}$ such that

$$ a=n\cdot c_1+ m\cdot c_2, $$

and the fact that $\frac{d}{a}$ leaves $0$ as a remainder can be phrased as

$$ d=k\cdot a,\qquad k\in\mathbb{Z}. $$

Putting these two together means

$$ d= k\cdot n\cdot c_1+k\cdot m\cdot c_2 $$

to make this a bit cleaner let $\tilde{n}=k\cdot n$ and $\tilde{m}=k\cdot m$ so

$$ d=\tilde{n}\cdot c_1+\tilde{m}\cdot c_2, \qquad \tilde{n},\tilde{m}\in\mathbb{Z} $$

So we could get $d$ as a linear combination of $c_1$ and $c_2$, translate this as we could get $d$ by taking a number of times $c_1$ and a number of times $c_2$. Observe that these numbers can be negatives as well so put a couple of $c_1$s in and remove some $c_2$s is also possible.

Now for the second question:

Assume that $a,b\in\mathbb{Z}$. It is not hard to see that then $$ b>0 \ \ \text{and} \ \ \ b\mid a\Rightarrow \gcd(a,b)=b $$

Another ingredient is the following fact, if $b\neq 0$ then

$$ a=b\cdot q+r\Rightarrow \gcd(a,b)=\gcd(b,r) $$

where $b>r$. I chellenge you to try to prove this :)

Having these in mind the Eucledean algorithm is as follows:

$$ a=bq_1+r_1 \qquad 0\le r_1< b $$

$$ b=r_1q_2+r_2 \qquad 0\le r_2< r_1 $$ $$ r_1=bq_3+r_2 \qquad 0\le r_2< r_3 $$

and so on. This will terminate after a while since the remainders are getting smaller and smaller and at some point you will reach $r_{n+1}=0$.

This gives us the following chain of equalities:

$$ \gcd(a,b)=\gcd(b,r_1)=\gcd(r_1,r_2)=\ldots=\gcd(r_{n-1},r_n)=\gcd(r_n,0)=r_n $$

I hope this helped a bit.

Related Question