Relativamente primos propiedad de verificación

Question

Estoy leyendo una ciencia de la computación puzzles libro.

Y tengo la siguiente pregunta -

"Tiene cinco cuartos de galón jarra, tres cuarto de galón jarra y suministro ilimitado de agua. ¿Cómo podría usted venir con exactamente cuatro cuartos de galón de agua ?"

La pregunta es bastante simple, y pensé que en la secuencia de "transferencias de agua" para resolverlo.

Pero hay una interesante nota al margen de que yo no sabía.

La nota al margen dijo que mientras los dos jarras de tamaño relativamente primos, es posible encontrar un vierta la secuencia para cualquier valor entre uno y la suma de la jarra de tamaños.

Es cierto por 5 y 3.

Pero quiero saber si realmente es cierto o no ? Si es así, es realmente genial! ¿Qué es el teorema de llamada ? Quien lo descubrió ?

Answer 1

Deja dos copas de vino a y B tienen capacidades de $a$ $b$ onzas, donde $a$ $b$ son relativamente primos números enteros positivos, y $a\lt b$. Supongamos también tenemos un gran barril lleno de vino. Vamos a demostrar que para cualquier entero $w$ donde $0\le w\le b$, podemos medir $w$ onzas de vino. (Esto significa que podemos medir cualquier número entero $y\le a+b$ de onzas de vino, siempre y cuando no nos importa las cosas que posiblemente en dos vasos. Yo no.)

Es suficiente para demostrar que para cualquier $r$,$0\le r\lt a$, podemos medir $r$ onzas. Para $w=qa+r$ algunos $r$$0$$a-1$. Así que si podemos medir $r$ onzas, podemos poner esto en B y, a continuación, llegar a $w$ mediante el uso de vidrio de $q$ veces.

La construcción es como sigue. Supongamos que en una determinada etapa tenemos $x_k$ onzas de vino en la copa A. Llenar la taza B del barril, superior hasta la copa de Un de copa B, vierta el contenido de Una en el cañón, o mejor, la beba. Sigan llenando Una copa B, volcar el contenido de Una en el barril cuando se llena. Después de un tiempo, la cantidad a la izquierda en B será insuficiente para llenar Una, pero se vierte en de todos modos. Llame a la cantidad que está ahora en el nombre de $x_{k+1}$. Entonces $$b=(a-x_k)+an+x_{k+1}$$ para algunos entero $n$. De ello se sigue que $$x_{k+1}\equiv x_k +b\pmod{a}.$$ Empezar con Un vacío, que es, con $x_0=0$. Entonces $x_1\equiv b\pmod{a}$, $x_2\equiv 2b\pmod{a}$, y así sucesivamente.

Pero desde $a$ $b$ son relativamente primos, los números de $0,b,2b.3b,\dots, (a-1)b$ constituyen un residuo del sistema modulo $a$. Así, la secuencia $x_0,x_1,x_2,\dots,x_{a-1}$ carreras, en cierto orden, a través de todos los números de $0$$a-1$. Esto completa la prueba.

Answer 2

Sí, es cierto. De Diophantine Ecuaciones en Wikipedia

El más simple lineal Diophantine ecuación toma la forma ax + by = c, donde a, b y c se indican los números enteros. Las soluciones son completamente descrito por el siguiente teorema: Esta ecuación Diophantine tiene un solución (donde x y y son enteros) si y sólo si c es un múltiplo el máximo común divisor de a y b. Por otra parte, si (x, y) es un la solución, entonces las otras soluciones de la forma (x + kv, y - ku), donde k es un entero arbitrario, y u y v son los cocientes de un y b (respectivamente) por el máximo común divisor de a y b.

Mira el artículo de la Wikipedia para obtener más detalles de una prueba.

---

Para tratar de conectar las cosas, considere la ecuación: 5x+3y=4 cuando x se puede representar el número de llenado o vaciado de la de 5 cuartos de galón jarra mientras que y representa la misma cosa para los de 3 cuartos de galón jarra. Si hay un factor común entre estos, esto podría ser un factor para que cualquier respuesta sería un múltiplo de ese número entero. Dado que una solución es (2,-2) para que la ecuación de Diophantine, esto podría implicar que uno llena el 5 cuartos de galón jarra y se vacía sobre el de 3 cuartos de galón jarra de un par de veces para obtener exactamente 4 cuartos de galón asumiendo que uno tiene otro recipiente para contener el 4 cuartos de galón.

---

He de admitir que he visto este problema de Die Hard 3, por lo que yo sé de una solución alternativa.

---

Considere el caso donde hay un factor común entre la jarra tamaños, donde uno tiene jarras de tamaño 8 y 12. Ahora, el máximo común divisor de 8 y 12 es 4 y por lo tanto, cualquier combinación de emanaciones te dejará con un múltiplo de 4 para una respuesta como 8x+12y=4(2x+3y) y así, mientras uno puede fácilmente resolver 2x+3y=1, es un poco diferente para resolver 4(2x+3y)=1, donde x e y son valores enteros como no existen soluciones aquí.

En contraste, considere la posibilidad de que, si para un determinado par de jarra de tamaños que se pueden obtener exactamente 1 de la unidad, entonces esto puede ser repetido para cualquier número Natural mayor que 1 por lo que para cualquier otro valor es bastante fácil si usted puede obtener 1.

---

La primera parte de mi respuesta cubre este en un caso general, pero por el bien del argumento, vamos a tomar $5x+3y=z$. Si $z=1$, luego por la inspección puedo notar que x=-1,y=2 es una solución. Hay muchas soluciones como uno podría tomar esa solución y realizar la parametrización de la solución de $x=-1+k,y=2-k$ k ser cualquier número entero. Ahora, si z es algún otro valor, me podría multiplicar la solución inicial para obtener ese valor. Por lo tanto, si $z=4$ $x=-4,y=8$ es una solución que funciona como $5*(-4)+3*8=-20+24=4$.

Esta última parte es bastante trivial para mi mente si te recuerdo que uno puede tomar una ecuación y se multiplican ambos lados por un valor distinto de cero y mantener la igualdad.