Minimum number of steps in water measure problem

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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)$:

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

$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):

$3$ steps:

and so on:
$4$ steps:

$5$ steps:

$6$ steps:

$7$ steps:

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

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