31
$\begingroup$

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: Handwritten table, transcribed below

   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.
$\endgroup$
  • $\begingroup$ @DanielFischer, yes thnx. $\endgroup$ – Haha Nov 27 '13 at 12:47
  • $\begingroup$ Surely integrality is the main issue here. I would suggest using a dynamic programming algorithm, which is not polynomial. $\endgroup$ – Listing Nov 27 '13 at 12:56
  • $\begingroup$ @Listing, what do you mean with integrability? And in which subproblems should i break the main problem? $\endgroup$ – Haha Nov 27 '13 at 13:01
  • $\begingroup$ @Dimitris: He says InteGRALity, not integraBILity -- that is, the observation is just that the numbers are integers. $\endgroup$ – Henning Makholm Nov 27 '13 at 13:03
  • 1
    $\begingroup$ 10 kilos a day means the brothers have a lousy cow. They should send it to the butcher and share the meat instead. $\endgroup$ – Per Manne Nov 27 '13 at 21:02
26
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks for your answer. I know little for algorithms but i understood this fully.thanks:) $\endgroup$ – Haha Nov 27 '13 at 13:06
  • $\begingroup$ But is there any faster way from my solution? $\endgroup$ – Haha Nov 27 '13 at 13:08
  • 1
    $\begingroup$ @Kevin, if you can do that, then your first comment should have read "You can do it in 2". Milk the cow into the 5k bottle. Then fill the 10k till her udders start squirting air :-) $\endgroup$ – Boluc Papuccuoglu Nov 27 '13 at 16:26
  • 1
    $\begingroup$ @BolucPapuccuoglu there is no 5K bucket $\endgroup$ – Kevin Nov 27 '13 at 16:31
  • 1
    $\begingroup$ @Kevin, yes my bad. D'oh! $\endgroup$ – Boluc Papuccuoglu Nov 27 '13 at 16:33
22
$\begingroup$

enter image description here

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

$\endgroup$
  • 9
    $\begingroup$ poor 0,7,3 :( $\endgroup$ – Cruncher Nov 27 '13 at 16:10
16
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ +1, Much nicer way to visualize the graph and allowed moves than doing it numerically like I did. $\endgroup$ – Henning Makholm Nov 27 '13 at 13:45
  • $\begingroup$ @HenningMakholm Thanks, and if you have time, you may wish to try drawing on an $AB$- or $AC$-plane instead. $\endgroup$ – peterwhy Nov 27 '13 at 13:58
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice answer. thank you for your time:) $\endgroup$ – Haha Nov 27 '13 at 22:31
  • $\begingroup$ @PerManne, after reading your solution and rereading my solution above, I suddenly realise what I was doing on my graph above was like moving straight on a torus, and the number of wrapping through border is closely related to the number of moves. Do you have any thought about this? $\endgroup$ – peterwhy Dec 1 '13 at 9:33
1
$\begingroup$

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. ;)

$\endgroup$
  • $\begingroup$ -1 for duplicating Henning Makholm's answer. $\endgroup$ – Fred Kline Nov 27 '13 at 13:41
  • 1
    $\begingroup$ I didn't realise there was already an answer! so rude.. $\endgroup$ – user111834 Nov 27 '13 at 23:50
0
$\begingroup$

That's it, i drew the tree and it was quite simple:

There are 2 non-repeating paths to the (5, 5, 0),
the first, dividing (10,0,0)-(3,7,0)-(3,4,3)-(6,4,0)... in 10 steps
and the second one, dividing (10,0,0)-(7,0,3)-(7,3,0)-(4,3,3)... in 11 steps
$\endgroup$
  • 5
    $\begingroup$ If you want to add information to your earlier answer, you should edit it instead of writing a new answer. $\endgroup$ – Henning Makholm Nov 27 '13 at 13:54
  • $\begingroup$ There's a different non-repeating path, starting (10,0,0) - (7,0,3) - (0,7,3) - (3,7,0) - (3,4,3) - (6,4,0) ... and so forth. And yet another one, starting (10,0,0) - (3,7,0) - (3,4,3) - (0,7,3,) - (7,0,3) - (7,3,0) - (4,3,3) ... $\endgroup$ – Henning Makholm Nov 27 '13 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.