Jugs Puzzle - the answer
Given two jugs A and B with capacities a and b we can obtain
any multiple of hcf(a,b) up to max(a,b)
(hfc is the "highest common factor", it is 1 when a and b
do not share any factors)
Proposition 1:
- At any stage at least one of the jugs is either full or empty:
- We can see that this is true by noting that any of the six operations
(fill A fill B empty A, empty B, transfer A to B (two cases), transfer
B to A (two cases) results in at most one partially filled jugs.
There are only two loops to go around the one starts with filling
jug A, the other starts with filling jug B.
The only way to proceed is to maintain at least one partially filled
jug. (having no partially filled jugs is not "interesting" as it is
only a few steps from the start condition)
wlog: assume we fill A first and define "forwards" as a transfer from A to B.
Assuming we have x pints in B and 0 in A (0,x) the following is the
only sensible way to proceed (any other option either back-tracks
or leaves us with both jugs empty or full)
Start (0,x)
Fill A (a,x)
Transfer A to B (a-b+x,b) {if a+x>b)
or (0,a+x) {otherwise}
Repeat while B is full (a-nb+x,b) {for some suitable n}
empty jug B and transfer A to B
(0,a-nb+x) = (0,a+x mod b)
Which brings us back to a situation similar to the start from which
"forwards" is the only sensible way to go.
Going through the above sequence again gives (0,2a+x mod b) then
(0,3a+x mod b)...
Starting with two empty jugs there are two sequences:
(0,0), (0,a mod b), (0,2a mod b), (0,3a mod b), ...(0,na mod b)...
(0,0), (b mod a,0), (2b mod a,0), (3b mod a,0), ...(nb mod a,0)...
Will deliver any multiple of the hcf of a and b upto b.
Some basic number theory informs us that if a and b are co-prime
we can get any number (up to b) from na mod b
The puzzle is much less interesting than it first appears - aren't they all?
The "couple of twists" do not significantly change the problem.