The Two Water Jugs Problem
The premise of the puzzle is simple. You have a well, and two water jugs of different sizes. The idea is to get a specific amount of water in one of (or both of) the jugs. In doing so, you are allowed to:
You are not allowed to do anything else, such as fill up a jug to a specific level - it is assumed that there are no ways of telling how full the jug is if it is partially full.
It is possible to tell whether or not a particular jugs problem is doable or not. Say that the capacity of one jug is p, the capacity of the other is q and that the target amount of water is r. A jug problem is possible if p and q are relatively prime, and if r is no bigger than (p+q) and/or if r is a multiple of gcd(p,q). Consequently, if you have a 9 litre jug and a 5 litre jug, it is possible to reach any amount of water between 0 and 14 litres inclusive. However, if you have a 6 litre jug and a 4 litre jug, you can only get 0, 2, 4, 6, 8 and 10 litres.
It isn't too hard to work out solutions for even bigger combinations. It's possible (read: I have done this myself) to use computational problem solvers to solve these in a few seconds; it took my machine a mere 0.88 seconds to work out how to get 5 litres, using a 19 litre and a 1,091 litre jug, in 348 steps.
Thanks go to neil for pointing out that a jug problem is still possible if p and q are not relatively prime, as long as r is a multiple of their greatest common divisor.
The contents of this writeup are in the public domain.