Número mínimo de pasos en el problema de la medida del agua.

Question

He estado luchando con este problema por un tiempo y se ha ido a través de preguntas acerca de la "Jarra de Agua de Problema/Rompecabezas".

Una persona quiere tener $2$ separada $1$ L medidas de agua al mismo tiempo. Sin embargo, las únicas medidas que ella tiene son para $6, 10$ e $15$ L. Mostrar cómo esto puede ser posible con el mínimo número de pasos sin marcar las medidas o el uso de cualquier recipiente que no sea la original de gran vaso de agua. La única pasos permitidos son el llenado o el vaciado de una medida o de la transferencia de agua de una medida a otra.

He leído una pregunta aquí, que es bastante similar (también la participación mínima de las operaciones), pero sólo se utiliza $2$ medidas/jarras en lugar de $3$. Yo no entendía cómo podía adaptarlo a mi problema. Sería una gran ayuda si alguien pudiera explicar en términos más simples...

Answer 1

Puedo demostrar la existencia de una solución, pero soy incapaz de decirle que es una solución óptima:

Iniciar con el llenado de la $6$L y $10$L jarras. Volcado de la $10$L jarra en la $15$L vaso y vierta el $6$L jarra en la $15$L jarra hasta que se completa.

Hasta ahora hemos hecho $4$ se mueve, y tenemos $1$L en la $6$L jarra y un total $15$L jarra.

Ahora volcado a la $15$L jarra y se llene nuevamente la $10$L jarra. (Se mueve a $5$ e $6$). Vierta la $10$L jarra en la $15$L jarra, luego de la transferencia de la $1$L de agua en el $6$L jarra a la ahora vacía $10$L jarra. Llene nuevamente la $6$L jarra.

Después de $9$ total mueve tenemos $1$L de agua en el $10$L jarra, $10$L de agua en el $15$L jarra, y un total $6$L jarra. El $10$th movimiento va a ser para verter el $6$L jarra en la $15$L jarra de relleno, dejando $1$L de agua que queda en el $6$L jarra.

Ahora tenemos dos conjuntos de $1$L de agua.

---

No estoy diciendo que mi solución es o no es el óptimo, pero no prueban la existencia de una solución.

Answer 2

Soluciones en $9$ pasos (sin prueba de optimalidad):

denotar jarras como $a$($6$L), $b$($10$L), $c$($15$L); entonces:

\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}

---

De hecho hay hasta $12$ válido mueve en cada etapa:
$\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$;

así que no hay más de $12^{8}\approx 430\:000\:000$ cadenas de $8$-paso mueve (no demasiado como para la comprobación del equipo).

Answer 3

Es más ilustrativo que "pura" a prueba de...

Cada posible estado puede ser escrito como triple $(a,b,c)$, donde $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}$. Así, podemos marcar los puntos con coordenadas enteras, que pertenecen a la paralelepípedo rectangular $\color{red}{[0,6]}\times\color{green}{[0,10]}\times\color{blue}{[0,15]}$.

Cada estado debe tener al menos un vacío o lleno el tarro. Así que (afortunadamente) cada estado puede ser marcado como punto en la superficie del rectángulo anterior.

De esta manera, el estado inicial se puede mostrar como en la imagen de abajo:
$\color{gray}{gray}$ punto $-$ estado inicial: $(0,0,0)$;
$\color{blue}{blue}$ puntos $-$ posibles estados: $(1,1,0), (1,1,15)$, $(6,1,1), (0,1,1)$, $(1,10,1), (1,0,1)$:

Podemos obtener otros $3$ unidos por un solo paso:
$\color{orange}{orange}$ puntos $-$ nuevos estados: $(6,0,0)$, $(0,10,0)$, $(0,0,15)$:

$2$ pasos:
$black$ puntos $-$ antiguo de los estados unidos;
$\color{gray}{gray}$ puntos $-$ puntos obtenidos por el paso anterior;
$\color{orange}{orange}$ puntos $-$ nuevos puntos;
(algunos movimientos de $\color{gray}{gray}$ a $\color{orange}{orange}$ están marcados por líneas adicionales):

$3$ pasos:

y así sucesivamente:
$4$ pasos:

$5$ pasos:

$6$ pasos:

$7$ pasos:

$8$ pasos:
(todavía todos los $6$ objetivo de los estados (puntos) no están cubiertos por $\color{orange}{orange}$):

$9$ pasos:
sí: $2$ objetivo de los estados (puntos) ha sido alcanzado: $(1,10,1)$ e $(1,1,15)$
(que está descrito en mi anterior respuesta)