title: Solving the water jug problem
body: <p>While reading through some <a href="http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-042JFall-2005/E7AB2626-FB19-480E-95F5-A9C23C2BD885/0/ln6.pdf" rel="noreferrer">lecture notes</a> on preliminary number theory, I came across the solution to 
  water jug problem (<strong>with two jugs)</strong> which is summed as thus:</p>
  
  <p>Using the property of the G.C.D of two numbers that GCD(a,b) is the smallest possible linear combination of a and b, and hence a certain quantity Q is only measurable by the 2 jugs, iff Q is a n*GCD(a,b), since Q=sA + tB, where:</p>
  
  <pre><code>n = a positive integer
  A = capacity of jug A
  B=  capacity of jug B
  </code></pre>
  
  <p>And, then the method to the solution is discussed</p>
  
  <p>Another model of the solution is to model the various <em>states</em> as a state-space search problem as often resorted to  in Artificial Intelligence.</p>
  
  <p>My question is: What other known methods exist which models the solution, and how? Google didn't throw up much.</p>