Compartir la cerveza bastante en un número finito de vertidos

Question

Un problema clásico dentro de las mediciones es que tiene un $8\,\text{dl}$ taza de delicioso caro de la cerveza y de la necesidad de compartir de manera uniforme con su amigo. Sin embargo, usted sólo tiene dos copas vacías de $5\,\text{dl}$$3\,\text{dl}$. Es posible dividir el líquido en dos con los dos recipientes? Con un poco de luz ponderar uno llega a la conclusión de que sí, es posible.

8 5 3 

8 0 0 - 0 
3 5 0 - 1 
3 2 3 - 2 
6 2 0 - 3 
6 0 2 - 4 
1 5 2 - 5 
1 4 3 - 6 
4 4 0 - 7

Imaginemos que tenemos una taza que contenga $B\,\text{dl}$ deliciosa cerveza, y dos tazas vacías de los tamaños de las $p$$q$. ¿Qué condiciones debe recaer en $p$ $q$ para asegurarse de que siempre existe un número finito de derrama para split $B$ en la mitad? (Se toma por dado que el $B$ siempre es incluso...)

Answer 1

Suponemos $A=B/2$, $p$, y $q$ son enteros, con $1\le p\le q\le B$, e $q\ge A$. Adoptamos el protocolo,

1. rellenar $q$ $B$
2. rellenar $p$ $q$ si es posible, de otra, vacía $q$ a $p$ y el ir a 1
3. vacía $q$ a $B$ e ir a 2

Vamos a ver cómo esto va con $(B,q,p)=(20,15,7)$. Comenzamos a las $(20,0,0)$ e ir $(5,15,0)$, $(5,8,7)$, $(12,8,0)$, $(12,1,7)$, $(19,1,0)$, $(19,0,1)$, $(4,15,1)$, $(4,9,7)$, $(11,9,0)$, $(11,2,7)$, $(18,2,0)$, $(18,0,2)$, $(3,15,2)$, $(3,10,7)$, $(10,10,0)$ y hemos terminado. Bueno, yo no he puesto un "stop" en cualquier parte en el protocolo, pero es claro que se detiene cuando/como/si usted tiene (algunos de permutación de) $(A,A,0)$. La pregunta es, ¿qué valores de partida de $B,q,p$ garantía de que obtendrá a $(A,A,0)$?

Tenga en cuenta que si $p$ $q$ tienen un divisor común $d$, entonces el contenido de la $p$ - $q$- los contenedores son siempre múltiplos de $d$. De ello se sigue que si $A$ no es un múltiplo de a $d$, no se puede ganar.

Pero ese es el único obstáculo. Si cada divisor común de a $p$ $q$ divide $A$, $\gcd(p,q)$ divide $A$, y podemos dividir por ello (creo que de la medición de nuestra cerveza en unidades de $d$ veces tan grande como de costumbre), así que ahora tenemos $\gcd(p,q)=1$. El contenido de la $B$-contenedor de obtener disminuyó $q$, luego (en repetidas ocasiones) aumentó $p$, por lo que tomar todos los valores de $B-(mq-np)$ (bueno, todos los valores de satisfacciones $0\le B-(mq-np)\le B$). E. g., en el ejemplo, el contenido de la $B$-contenedor comenzó a las 20, se fue abajo por 15 a 5, 7 a 12 y a las 19, por 15 a 4, 7 a 11 y de 18, por 15 a 3, por 7 a 10. Desde $\gcd(p,q)=1$, de la escuela primaria número teoría nos dice que podemos encontrar $m$ $n$ tal que $mq-np=A$, por lo que finalmente el envase grande ha $A$, y hemos terminado.