Jugs of Water Puzzle: Minimum Number of Operations

Yes, the algorithm is always optimal. The reason is that once you've decided which jug to fill first, there's nothing you can do that makes sense at any point other than what the algorithm says.

Suppose we have just poured from A to B. Then, because we stopped pouring, it must be the case that either A is empty or B is full. (Or both are true, in which case we have achieved nothing we couldn't do just by filling up B from the beginning).

• If A is empty, then pouring back from B to A immediately will just put us in the state we just came from. Either emptying or filling B will erase all of our hard work, so the only sane thing to do is to fill A from the tap, and then continue pouring from A to B.

• If B is full, then pouring back from B to A immediately would still be pointless (at least from the point of view of getting a shortest solution) because we could have done that instead of pouring from A to B in the first place. Either emptying or filling A would lose our work so far, so the only thing to do is to empty out B, and then continue pouring from A to B.

Thus, in an optimal sequence every pour goes in the same direction: either always from A to B or from B to A. You can compute how long it will take to reach $c$ in each case by using the extended Euclidean algorithm (as Joffan describes) rather than actually doing the simulation one pour at a time, though.

Essentially this is an exercise in modular arithmetic.

Each cycle of jug activity either adds or subtracts a certain amount from the larger jug, depending on which way around the cycle you are heading (which jug is being refilled and which discarded).

In order to find the number of operations, barring some details, you need to find the multiplicative inverse of $b \bmod a$ (I'm assuming that $a$ is the largest of the three numbers). The extended Euclidean algorithm will give you this, and also the feasibility of the triplet.

Suppose we have $(a,b,c) = (57,41, 20)$. Then the extended Euclidean algorithm gives:

\begin{array}{c|c} n & s & t & q \\ \hline 57 & 1 & 0 & \\ 41 & 0 & 1 & 1 \\ 16 & 1 & -1 & 2 \\ 9 & -2 & 3 & 1 \\ 7 & 3 & -4 & 1 \\ 2 & -5 & 7 & 3 \\ 1 & 18 & -25 & 2 \\ \end{array}

where each line gives an identity $n=57s+41t$, ending with Bezout's identity $18\cdot 57-25\cdot 41=1$

Edit insert: this is where we can check feasibility. If the Extended euclidean algorithm here ends with a GCD of $1$, there is no issue, but if $a$ and $b$ have a common factor then the problem is only solvable if $c$ is also divisible by that factor.

This means that $-25\cdot 41\equiv 1 \bmod 57$, so we have $-25$ as the mulitplicative inverse of $41\bmod 57$ and $41k\equiv 20\bmod 57$ can be solved with $k\equiv -25\cdot 20\equiv -50\cdot 10\equiv 7\cdot 10\equiv 70\equiv 13\bmod 57$.

So $-13\equiv 44\bmod 57$ is larger; therefore we want to go the additive way, refilling the small jug and pouring into the big jug, and that refill should happen $13$ times (if we start with both jugs empty): $\newcommand{pour}{\underset{\text{pour}}{\to}}$ $\newcommand{refill}{\underset{\text{refill}}{\to}}$ $\newcommand{empty}{\underset{\text{empty}}{\to}}$

$\begin{align}(0,0)&\refill(0,41)\pour(41,0)\refill(41,41)\pour(57,25)\empty(0,25)\\ &\pour(25,0)\refill(25,41)\pour(57,9)\empty(0,9)\pour(9,0)\\ &\refill(9,41)\pour(50,0)\refill(50,41)\pour(57,34)\empty(0,34)\\ &\pour(34,0)\refill(34,41)\pour(57,18)\empty(0,18)\pour(18,0)\\ &\refill(18,41)\pour(57,2)\empty(0,2)\pour(2,0)\refill(2,41)\\ &\pour(43,0)\refill(43,41)\pour(57,27)\empty(0,27)\pour(27,0)\\ &\refill(27,41)\pour(57,11)\empty(0,11)\pour(11,0)\refill(11,41)\\ &\pour(52,0)\refill(52,41)\pour(57,36)\empty(0,36)\pour(36,0)\\ &\refill(36,41)\pour(57,20)\\ \end{align}$

For every refill, of course we also get an initial pour, and then we may also get extra empty + pour operations if we go past a multiple of 57 poured. so $\lfloor(13\times 41)/57\rfloor = 9$ so we should have $13\times 2 + 9\times 2 = 44$ operations (which would end with correct amount in the big jug). Here we stopped short of the last two operations because we had the correct amount in the small jug already (which can be predicted since $20<41$), giving $42$ operations.