4
$\begingroup$

I've been struggling with this problem for a while and gone through questions about the "Water Jug Problem/Puzzle".

A person wants to have $2$ separate $1$ L measures of water at the same time. However the only measures she has are for $6, 10$ and $15$ L. Show how this could be done with the minimum number of steps without marking the measures or using any container other than the original large beaker of water. The only steps allowed are filling or emptying a measure or transferring water from one measure to another.

I've read a question here which is pretty similar (also involving minimum operations) to this but only used $2$ measures/jugs instead of $3$. I didn't understand how I could adapt it into my problem. It would be a great help if someone could explain in simpler terms...

$\endgroup$
4
$\begingroup$

I can show the existence of a solution, but I am unable to tell you that it is an optimal solution:

Start with filling the $6$L and $10$L jugs. Dump the $10$L jug into the $15$L jug and pour the $6$L jug into the $15$L jug until it's full.

Thus far we have made $4$ moves, and we have $1$L in the $6$L jug and a full $15$L jug.

Now dump out the $15$L jug and fill back up the $10$L jug. (Moves $5$ and $6$). Pour the $10$L jug into the $15$L jug, then transfer the $1$L of water in the $6$L jug to the now empty $10$L jug. Fill back up the $6$L jug.

After $9$ total moves we have $1$L of water in the $10$L jug, $10$L of water in the $15$L jug, and a full $6$L jug. The $10$th move will be to pour the $6$L jug into the $15$L jug to fill it up, leaving $1$L of water left in the $6$L jug.

We now have two sets of $1$L of water.


I am not saying that my solution is or is not optimal, but it does prove the existence of a solution.

$\endgroup$
4
$\begingroup$

Solutions in $9$ steps (without proof of optimality yet):

denote jugs as $a$($6$L), $b$($10$L), $c$($15$L); then:

\begin{array}{|c|c|c|c|c|} \hline \# & move & a & b & c \\ \hline 1) & \bullet \rightarrow a & 6 & - & - \\ 2) & \bullet \rightarrow c & 6 & - & 15 \\ 3) & c \rightarrow b & 6 & 10 & 5 \\ 4) & b \rightarrow \bullet & 6 & - & 5 \\ 5) & c \rightarrow b & 6 & 5 & - \\ 6) & a \rightarrow c & - & 5 & 6 \\ 7) & \bullet \rightarrow a & 6 & 5 & 6 \\ 8) & a \rightarrow b & 1 & 10 & 6 \\ 9) & b \rightarrow c & 1 & 1 & 15 \\ \hline \end{array}

\begin{array}{|c|c|c|c|c|} \hline \# & move & a & b & c \\ \hline 1) & \bullet \rightarrow a & 6 & - & - \\ 2) & \bullet\rightarrow b & 6 & 10 & - \\ 3) & b \rightarrow c & 6 & - & 10 \\ 4) & a \rightarrow b & - & 6 & 10 \\ 5) & \bullet \rightarrow a & 6 & 6 & 10 \\ 6) & a \rightarrow c & 1 & 6 & 15 \\ 7) & c \rightarrow b & 1 & 10 & 11 \\ 8) & b \rightarrow \bullet & 1 & 0 & 11 \\ 9) & c \rightarrow b & 1 & 10 & 1 \\ \hline \end{array}


Actually there are up to $12$ valid moves at each stage:
$\bullet \rightarrow a$, $\;\bullet \rightarrow b$, $\;\bullet \rightarrow c$;
$a \rightarrow b$, $\;a \rightarrow c$, $\;a \rightarrow \bullet$;
$b \rightarrow a$, $\;b \rightarrow c$, $\;b \rightarrow \bullet$;
$c \rightarrow a$, $\;c \rightarrow b$, $\;c \rightarrow \bullet$;

so there are not more than $12^{8}\approx 430\:000\:000$ chains of $8$-step moves (not too much as for computer check).

$\endgroup$
  • 3
    $\begingroup$ This program confirms that your solution is the shortest. $\endgroup$ – Mike Earnest Feb 20 at 17:04
  • 2
    $\begingroup$ @Mike Earnest: thank you very much for open source and clever & concise code. $\endgroup$ – Oleg567 Feb 20 at 17:13
  • $\begingroup$ Is there a way to show that there can't be less steps other than a program? $\endgroup$ – RachelG Feb 20 at 19:58
  • 2
    $\begingroup$ @RachelG: yes, there is: each possible state can be written as triple $(a,b,c)$, where $a,b,c \in\mathbb{Z}, 0\le a \le 6, 0\le b \le 10, 0\le c \le 15$. So, we can mark those as poins with integer coordinates, which belong to the rectangular cuboid $[0,6]\times[0,10]\times[0,15]$. Each state should have at least one empty or full jar. So now each state can be marked as point on surface of the cuboid above (and can be painted on paper sheet more-or-less easily). I'll try to explain more detailed a bit later ... $\endgroup$ – Oleg567 Feb 21 at 16:07
  • $\begingroup$ So if you consider the minimum number of states for each jug, it would be 3x3=9 which is the minimum number of steps? I was wondering if you could explain this, more in further detail... I really appreciate all the reasonings you've come forward with so far! Thank you $\endgroup$ – RachelG Feb 22 at 22:36
2
$\begingroup$

It's more illustration than "pure" proof...

Each possible state can be written as triple $(a,b,c)$, where $a,b,c\in\mathbb{Z}$, $\color{red}{0\le a\le 6}$, $\color{green}{0\le b \le 10}$, $\color{blue}{0\le c \le 15}$. So, we can mark those as points with integer coordinates, which belong to the rectangular cuboid $\color{red}{[0,6]}\times\color{green}{[0,10]}\times\color{blue}{[0,15]}$.

Each state should have at least one empty or full jar. So (fortunately) each state can be marked as point on surface of the cuboid above.

This way, initial state can be displayed as in the image below:
$\color{gray}{gray}$ dot $-$ starting state: $(0,0,0)$;
$\color{blue}{blue}$ dots $-$ possible target states: $(1,1,0), (1,1,15)$, $(6,1,1), (0,1,1)$, $(1,10,1), (1,0,1)$: state 0

We can get other $3$ states by one step:
$\color{orange}{orange}$ dots $-$ new states: $(6,0,0)$, $(0,10,0)$, $(0,0,15)$: state 1

$2$ steps:
$black$ dots $-$ old states;
$\color{gray}{gray}$ dots $-$ dots obtained by previous step;
$\color{orange}{orange}$ dots $-$ new dots;
(some moves from $\color{gray}{gray}$ to $\color{orange}{orange}$ are marked by additional lines): state 2

$3$ steps: state 3

and so on:
$4$ steps: state 4

$5$ steps: state 5

$6$ steps: state 6

$7$ steps: state 7

$8$ steps:
(still all $6$ target states (dots) are not covered by $\color{orange}{orange}$ ones): state 8

$9$ steps:
yes: $2$ target states (dots) have been reached: $(1,10,1)$ and $(1,1,15)$
(they're described in my previous answer) state 9

$\endgroup$

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.