El problema del reparto de leche

Question

Me encontré con un libro de matemáticas de las pruebas. Era de mi padre cuando era joven. Me encontré con un problema con el siguiente cuestionario. He resuelto, pero me pregunto, ¿hay una manera más rápida de hacerlo? Si es así, ¿cómo puedo calcular el tiempo (tiempo polinomio) que se necesita para resolverlo? Se puede construir un algoritmo?

El problema es este:

Dos hermanos tienen una vaca que produce 10 kilos de leche por día. Porque son justas, que comparten la leche y cada uno recibe 5 kilos.

Sólo tienen disponibles tres botellas.

$A$ que se adapte a 10 kilos.

$B$ que se adapte a 7 kilos.

$C$ que se adapte a 3 kilos.

Cómo hacer que compartir?

Lo que yo hice estos pasos:

   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.

Answer 1

Este problema en particular es lo suficientemente pequeño como para comprobar la menor solución con la fuerza bruta.

Cada estado del sistema está completamente descrito por la cantidad de leche que hay en las botellas B y C, lo que hace que $8\veces 4=32$ estados posibles. En cada estado hay en la mayoría de los 6 posibles movimientos: elija dos botellas y se vierte de una a otra hasta que la fuente está vacía o el destino. Por lo que el problema de los mapas de un lápiz-y-papel de tamaño ejemplo de Gráfico de Ruta de acceso más corta.

(Con un poco más de pensamiento, podemos ver que los estados donde todos tres botellas son parcialmente llena no puede ser alcanzado por cualquier jugada legal. Esos estados son 12, por lo que en la realidad, en la mayoría de los 20 de los estados puede ser accesible-y en cualquier estado alcanzable no hay, realmente, en la mayoría de 4 avance significativo, porque brota de/a la botella que acaba de vaciado/llenado, es un no-op).

Esto no crea un polinomio de tiempo de algoritmo para el problema general, aunque. En la mayoría de los obtenemos una pseudo-polinomial uno si el número de botellas que se mantiene fija.

---

Un lápiz-y-papel amplitud primera búsqueda encuentra que la única solución más corta es esta con 9 vierte: $$ (10)00 \370\to343\to640\to613\to910\to901\to271\to253\to550 $$ y todos 20 los estados son en realidad alcanzable.

Answer 2

Esto es para todas las configuraciones accesibles desde la primera. Atrás operaciones no se muestra. Como se puede ver, hay una ruta más corta.

Answer 3

Esta es una manera de visualizar una solución, que en realidad es similar a la del método dado por Henning Makholm. Deje que las variables $A$, $B$ y $C$ ser los pesos de la leche en cada botella del mismo nombre. Tenemos tres de las desigualdades y una ecuación:

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

Ahora puedo elegir dos variables, digamos $B$ y $C$, y eliminar el resto de variables.

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

Definir un punto de partida, en este caso $(a,B,C)=(10,0,0)$, y un punto de finalización, $(a,B,C) = (5,5,0)$. Podemos representar esta región y los dos puntos en un $BC$-plano.

Podemos pensar verter la leche entre las botellas como mover horizontalmente (mantenimiento $C$ constantes) hasta el límite, se desplazan en sentido vertical (de mantenimiento de $B$ constantes), o moviéndose en diagonal NW o SE (mantenimiento de $Un$ constantes). Todo movimiento debe moverse hasta golpear límite, ya que no hay forma de parar, precisamente, sin vaciar una botella o totalmente de llenado de una botella.

Mediante la creación de la ruta de esta manera, esto puede ser más fácil de visual alternativo en caso resuelto por la mano. Finalmente, las respuestas pueden ser leídos a partir de la $B$ y $C$ los valores de cada nodo intermedio, por ejemplo, en $(a,B,C)=(10-B-C, B, C)$ formato:

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

y con algo de práctica, las botellas de los involucrados puede ser leído desde el borde de la dirección.

En general, la región puede ser de forma de hexágono, pentágono, paralelogramo, trapecio, rectángulo, triángulo, etc.

Answer 4

Estos problemas son rutinariamente resuelto mediante el algoritmo de Euclides. El máximo común divisor de $7 a$ y $3$ es $1$, y este número se puede escribir como una integral combinación de us $7$ y $3$ (la identidad de Bezout). De hecho, aquí se puede escribir de inmediato $$1\cdot 7-2\cdot 3=1$$ Multiplicar por $5 dólares, y obtenemos $$5\cdot 7-10\cdot 3=5$$ Esto le da una posible solución: el Relleno de la media ($7$ kg) cubo de cinco veces, y el uso de la más pequeña cubeta para eliminar $3$ kg diez veces. Esto no es muy eficiente, pero podemos producir nuevas soluciones sumando y restando la identidad $$3\cdot 7 - 7\cdot 3=0$$ como tantas veces como se desee. Restando una vez, obtenemos $$2\cdot 7-3\cdot 3=5$$ Esto muestra una forma mucho más eficiente de la solución, donde llenamos el medio cubo de dos veces, y el uso de la más pequeña cubeta para eliminar $3$ kg tres veces. Podemos restar la identidad de $3\cdot 7-7\cdot 3=0$, una vez más, lo que resulta en $$(-1)\cdot 7 + 4\cdot 3=5$$ Esto le da una solución en la que llenamos el más pequeño cubo de cuatro veces, y utilizar el medio cucharón para sacar us $7$ kg.

Hay infinitamente muchas más maneras de escribir $5$ como parte integrante de la combinación de los $7$ y $3$, pero estos dos son los únicos con los coeficientes más cercano a cero, de modo que ellos son los únicos candidatos para resolver el problema.

Ya que tenemos una falta de grandes contenedores, queda el problema práctico de la implementación de estas soluciones sin derramar la leche. Esto tiene que ser hecho por el vertido de ida y vuelta entre los cubos que tenemos. Esto siempre se puede hacer, y en cualquier etapa del proceso sólo hay una manera de proceder de acuerdo con la solución que deseamos implementar. Buscando la solución dada por la OP en el enunciado del problema, vemos que se han llenado los $7$ kg balde dos veces, y nos hemos volcado a $3$ kg desde el medio hasta el más pequeño cubo de cuatro tiempos, lo que hace que esta sea la implementación de la solución de $2\cdot 7-3\cdot 3=5$. Mirando a la parte inferior de la solución por @Xoff, vemos la implementación de la solución $(-1)\cdot 7+4\cdot 3=5$, donde hemos volcado $3$ kg en el medio cubo de cuatro veces, y se retira $7$ kg una vez. La comparación de estas dos alternativas, como en varias de las respuestas anteriores, tenemos que la solución dada por el OP es de hecho la óptima.

Answer 5

He encontrado una mejor manera, en 10 pasos. He intentado mejorarlo, pero a mí me parece que es la opción con menos pasos. Aquí va:

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)

En cualquier caso, voy a dibujar un árbol (esto puede sonar un poco infantil) con el fin de probarlo. ;)