La generalización de las dos cubo rompecabezas

Question

El clásico puzzle va algo como esto: "Usted está de pie en frente de un lago con un 3 galones cubo y un balde de 5 galones, ¿cómo se puede obtener 4 litros de agua?"

Hay una manera fácil de generar el triple (a,B,C) donde se puede obtener C galones de agua con cubos de tamaño a y B?

Answer 1

Simon respuesta señala que el algoritmo de Euclides demuestra que mcd(a,B) divide a C es necesaria, pero la falta de un contenedor de grandes dimensiones hace que el problema más difícil, porque, obviamente, usted no puede conseguir a $C$ si $C \gt A+B$. Sin embargo, la siguiente modificación del algoritmo parece funcionar.

Supongamos $A \lt B$ y mcd$(A, B)=1$ por la simplicidad. Mediante el vertido de B en a y el dumping, usted puede conseguir cualquier entero positivo $B-nA$ a la izquierda en B. Haga esto hasta que la respuesta es menos de $A$. A continuación, mediante la transferencia de los contenidos a Un cubo y llenarlo de B, obtenemos $2B-(n+1)A$. A continuación, reste $A$ otra vez hasta que usted ha $0 \lt 2B-kA \lt A$, y podemos repetir este proceso para llevar a $3B-(k+1)A$, etc. Esto le da a cualquier número entero combinación lineal $rB-sA$ hasta el tamaño de $A+B$ porque una vez que tienes el derecho de varios de $B$ en la combinación, siempre se puede añadir bucketsful de $A$.

Usted sólo tiene que conseguir $rB\equiv C$ (mod A) con el fin de encontrar una combinación de $C$, que pasa si gcd$(A, B)=1$. Con este algoritmo se ejecute en el caso general, usted puede conseguir cualquier múltiplo de gcd($A, B$) a $A+B$ (esto es trivialmente al $A=B$).

(Lo siento, tuve que editar esta respuesta varias veces porque las partes desaparecido, hasta que me di cuenta de que mi desigualdad señales eran analiza como etiqueta HTML comienza incluso después de signos de dólar.)

Answer 2

No una respuesta, sino más bien una buena cosa a tener en cuenta en relación con el problema-

http://numb3rs.wolfram.com/501/puzzle.html

Answer 3

Sí. La respuesta se desprende de Bezout del teorema que dice que dados los enteros a,B y C, C puede ser escrito como XA+YB si y sólo si C es un múltiplo de la mayor factor común de a y B. el algoritmo de Euclides dice cómo calcular X y Y.

No es demasiado difícil ver que los volúmenes solo puede obtener son aquellos de los que se entero combinación lineal de a y B, y usted puede conseguir cada positivos volumen que se plantea en esta manera (siempre y cuando usted tiene un gran contenedor adicional para almacenar todo).

Answer 4

Yo no soy un profesional, matemático, pero un desarrollador de software dada la generalización de este problema como un reto de codificación. He implementado un sitio web sencillo y de código abierto, el código mucho a la ayuda de este hilo aclarar la ecuación así que pensé que sería una adición muy valiosa.

Mi código de algoritmo se puede ver en https://github.com/metame/infinite-lake/blob/master/app/js/algorithm.js.

También puede utilizar la herramienta en vivo http://michaeljerwin.com/twobuckets.