The milk sharing problem

I found a book with math quizzes. It was my father's when he was young. I encountered a problem with the following quiz. I solved it, but I wonder, is there a faster way to do it? If so, how can I compute the time (polynomial time) that is needed to solve it? Can we build an algorithm?

The problem is this one:

Two brothers have a cow that produces 10 kilos of milk per day. Because they are fair, they share the milk and each one gets 5 kilos.

They only have available three bottles.

$A$ that fits 10 kilos.

$B$ that fits 7 kilos.

$C$ that fits 3 kilos.

How do they share it?

What I did is these steps:

   Bottle Sizes
      A   B   C
     10   7   3

Moves    Bottles        What we do:
 1st    10   0   0      Fill the bottle A.
 2nd     7   0   3      Fill the bottle C.
 3rd     7   3   0      Empty the index of C in B.
 4th     4   3   3      Refill C.
 5th     4   6   0      Empty C in B.
 6th     1   6   3      Refill C from A.
 7th     1   7   2      Refill B from C.
 8th     8   0   2      Empty the index of B in A.
 9th     8   2   0      Empty the index of C in B.
10th     5   2   3      Refill C from A.
11th     5   5   0      Empty C in B.

This particular problem is small enough to check for the shortest solution with brute force.

Every state of the system is fully described by how much milk there is in bottles B and C, which makes $8\times 4=32$ possible states. In each state there are at most 6 possible moves: pick two bottles and pour from one to another until either the source is empty or the destination is full. So the problem maps to a pencil-and-paper sized instance of Graph Shortest Path.

(With a bit more thought we can see that states where all three bottles are partially full cannot be reached by any legal move. There are 12 such states, so in reality at most 20 of the states can be reachable -- and in any reachable state there's really at most 4 meaningful moves, because pouring from/to the bottle you just emptied/filled is a no-op).

This doesn't create a polynomial-time algorithm for the general problem, though. At most we get a pseudo-polynomial one if the number of bottles is kept fixed.

A pen-and-paper breadth first search finds that the unique shortest solution is this with 9 pours: $$ (10)00 \to 370\to343\to640\to613\to910\to901\to271\to253\to550 $$ and all 20 states are in fact reachable.

This is all configurations accessible from the first. Backward operations are not shown. As you see, there is a shorter path.

This is one way to visualise a solution, which is actually similar to the method given by Henning Makholm. Let variables $A$, $B$ and $C$ be the weights of milk in each bottle of the same name. We have three inequalities and one equation:

$$0\le A \le 10\\ 0\le B\le7\\ 0\le C\le3\\ A+B+C = 10$$

Now I choose two variables, say $B$ and $C$, and eliminate the remaining variable.

$$0\le B+C \le 10\\ 0\le B\le7\\ 0\le C\le3$$

Define one starting point, in this case $(A,B,C)=(10,0,0)$, and one ending point, $(A,B,C) = (5,5,0)$. We can plot this region and the two points onto a $BC$-plane.

We can think of pouring milk between bottles as either moving horizontally (keeping $C$ constant) until boundary, moving vertically (keeping $B$ constant), or moving diagonally NW or SE (keeping $A$ constant). All movement should move until hitting boundary, as there is no way to stop precisely without emptying one bottle or fully filling one bottle.

By creating path in this way, this may be an easier visual alternative if solved by hand. Finally answers can be read from the $B$ and $C$ values of each intermediate node, for example, in $(A,B,C)=(10-B-C, B, C)$ format:

$$(10,0,0)\to(3,7,0)\to(3,4,3)\to(6,4,0)\to\cdots$$

and with some practise, the bottles involved can be read from edge direction.

In general, such region can be of shape hexagon, pentagon, parallelogram, trapezium, rectangle, triangle, etc.

These problems are routinely solved by using the Euclidean algorithm. The greatest common divisor of $7$ and $3$ is $1$, and this number can be written as an integral combination of $7$ and $3$ (Bezout's identity). In fact, here we can immediately write $$1\cdot 7-2\cdot 3=1$$ Multiply through by $5$, and we get $$5\cdot 7-10\cdot 3=5$$ This gives one possible solution: Fill the medium ($7$ kg) bucket five times, and use the smallest bucket to remove $3$ kg ten times. This is not very efficient, but we can produce new solutions by adding and subtracting the identity $$3\cdot 7 - 7\cdot 3=0$$ as many times as we wish. Subtracting it once, we get $$2\cdot 7-3\cdot 3=5$$ This shows a much more efficient solution, where we fill the medium bucket twice, and use the smallest bucket to remove $3$ kg three times. We can subtract the identity $3\cdot 7-7\cdot 3=0$ once more, resulting in $$(-1)\cdot 7 + 4\cdot 3=5$$ This gives a solution where we fill the smallest bucket four times, and use the medium bucket to remove $7$ kg.

There are infinitely many more ways of writing $5$ as an integral combination of $7$ and $3$, but these two are the ones with coefficients closest to zero, so they are the only candidates for solving the problem.

Since we have a lack of large containers, there remains the practical problem of implementing these solutions without spilling any milk. This has to be done by pouring back and forth between the buckets that we have. This can always be done, and at any stage of the process there is only one way to proceed in accordance with the solution that we wish to implement. Looking at the solution given by the OP in the problem statement, we see that we have filled the $7$ kg bucket twice, and we have poured $3$ kg from the medium to the smallest bucket four times, which makes this the implementation of the solution $2\cdot 7-3\cdot 3=5$. Looking at the lower solution by @Xoff, we see the implementation of the solution $(-1)\cdot 7+4\cdot 3=5$, where we have poured $3$ kg into the medium bucket four times, and removed $7$ kg once. Comparing these two alternatives, as in several of the answers above, we get that the solution given by the OP is in fact the optimal one.

I've found a better way, in 10 steps. I tried to improve it but it seems to me that it's the option with less steps. Here it goes:

A B C (10, 0, 0)-(3, 7, 0)-(3, 4, 3)-(6, 4, 0)-(6, 1, 3)-(9, 1, 0)-(9, 0, 1)-(2, 7, 1)-(2, 5, 3)-(5, 5, 0)

In any case, i'm going to draw a tree (this may sound a bit childish) in order to prove it. ;)