Les dejo el problema del día.
Se tienen $n$ vasos que aguantan una cantidad suficiente de agua. Al inicio todos tienen la misma cantidad de agua. En un paso puedes vaciar de un vaso $A$ a un vaso $B$ la cantidad de agua que tiene el vaso $B$ (siempre y cuando el vaso $A$ tenga agua suficiente). ¿Para qué valores de $n$ es posible conseguir un vaso con toda el agua?
miércoles, 23 de febrero de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
9 comentarios:
No comprendí el problema...
Leelo de nuevo, es muy claro!
Ah, ya entendí, y podemos pensar en que los vasos tienen capacidad infinita, no? a eso se refiere con suficiente, verdad?
Veamos primero que si cada vaso inicia con agua $m$ en los enteros, entonces todos los vasos siempre tendrán agua múltiplo de $m$, por lo que podemos suponer aún mejor que $m=1$ y todos siempre contienen cantidad de agua entera, ahora veamos que al final buscamos que este vaso tenga toda el agua, y entonces en el paso anterior, hubo dos vasos que contenían respectivamente la mitad del agua cada uno y como esto significa que cada uno tiene $n/2$ de agua, con $n$ par, entonces $2|n$. En el paso anterior a este se puede una de dos cosas, que haya habido una interacción entre estos dos vasos una cantidad ininterrumpida de $r$ veces que implica que al menos hubo otra y no sólo eso sino que en el paso anterior hubo un vaso con $3n/4$ y el otro con $n/4$ y entonces $4|n$ y por cada vez que se repita, el factor que multiplica a $n$ es impar y el denominador baja a la mitad todo el tiempo, ya que alguno posee el doble que antes y entonces $2^{r}|n$. En caso de que después de esta cantidad ininterrumpida de interacciones hubo una interacción con otro vaso que ahora está vacío, significa que entonces antes, cada vaso tenía la mitad de esa agua y entonces, al menos $2^{r+1}|n$, de donde vemos que cuando menos $4|n$.
Si expresamos a los números de la siguiente forma: $\dfrac{na}{b}$ que, a pesar de que esto nos dé entero, lo llamaremos 'semi-irreducible' ya que $\dfrac{a}{b}$ es irreducible para $a$, $b$ enteros, entonces veamos que $b$ siempre será de la forma $2^{k}$ para alguna $k$ entera no negativa. Primero, eliminemos de nuestra notación a la $n$ por un momento, aunque somos concientes de que siempre está ahí. Por inducción veamos que en el caso del final (como en este problema vamos de adelante para atrás, la inducción también) se cumple puesto que $k=0$ y tenemos que el vaso tiene $1$ de agua y como los otros son vacíos, por vacuidad también es cierto. Ahora supongamos que funciona hasta cierto momento. Veamos que para el momento anterior a éste, también funcionaba y acabaremos.
Veamos que por cada vez que interactuaron dos vasos con agua $\dfrac{2k_{1}+1}{2^{a}}$ y otro con agua $\dfrac{2k_{2}+1}{2^{b}}$ para todos enteros, entonces al menos uno de los dos denominadores se vuelve el doble (si nos regresamos), y su numerador no cambia, además, si suponemos sin pérdida de generalidad que el vaso que se fue a la mitad fue el que tenía $\dfrac{2k_{1}+1}{2^{a}}$ agua, entonces el otro tiene $\dfrac{2k_{2}+1}{2^{b}}+\dfrac{2k_{1}+1}{2^{a+1}}$. Si suponemos que $a+c=b$ para $c$ algún entero positivo entonces veamos que esto es igual a $\dfrac{2k_{2}+1+2^{c-1}(2k_{1}+1)}{2^{b}}$ y a menos que $c=1$ esto sigue siendo irreducible, en caso contrario, veamos que de cualquier modo, los únicos factores que podemos eliminar con el denominador son $2$'s y entonces se sigue cumpliendo. Si suponemos para $b+c=a$ con c entero no negativo, de manera similar se prueba lo mismo.
Ahora veamos qué pasa si tomamos uno vacío y otro que no lo es como $\dfrac{2k_{1}+1}{2^{a}}$, eso significa que en el anterior, ambos tenían $\dfrac{2k_{1}+1}{2^{a+1}}$ de agua y se sigue cumpliendo. Por lo que acabamos nuestro paso inductivo.
Ahora, como el denominador siempre es de la forma $2^{k}$ para alguna $k$ en los enteros no negativos, y en algún momento debemos llegar a que todos son $\dfrac{1}{n}$ eso significa que $n$ es de la forma $2^{k}$. Ahora veamos que estos casos siempre funcionan.
Probémoslo por Inducción: en nuestra base tenemos cuando $n=1$ es trivialmente cierto. Supongamos que sirve para vierta $n=2^{k}$, veamos que para $n=2^{k+1}$ también, para esto, simplemente agrupemos por parejas los vasos y en los primeros $k$ movimientos vaciemos el agua de uno de la pareja en el otro hasta que todos tengan 2 de agua. Ahora, por la hipótesis inicial, tenemos $2^{k}$ vasos con la misma cantidad de agua, por lo que se puede hacer y acabamos.
perdon, en la última parte no es en $k$ movimientos sino en $2^{k}$ movimientos
Podemos suponer que al principio todos tienen 1 de agua y entonces siempre van a ser enteras la cantidad de agua de cada vaso.
La condición lo que nos dice es que de una pareja (A,B) con A mayor o igual a B, podemos pasar a una de la forma (A-B,2B) dicho de otra forma es que una pareja (X,Y) tuvo que haber venido de una de la forma ((2X+Y)/2,Y/2) con X mayor o igual a 0.
Ahora supongamos que hemos acabado, entonces llegamos a un acomodo de la forma (n,0,...,0). Supongamos que un primo p distinto de dos divide a n. Entonces como p divide a 0, p divide a todos los números de nuestro conjunto, por lo tanto si nos regresamos a ver de donde viene una pareja (X,Y) vamos a ver que viene de ((2X+Y)/2,Y/2) pero como p divide a X y p divide a Y. Entonces p divide a los nuevos números. Haciendo esto repetidamente vemos que p siempre divide a todos los números.
Pero se supone que el conjunto (n,0,...,0) viene de (1,1,..,1) por lo tanto p divide a 1 lo cual es una contradicción. Por lo tanto ningun primo distinto de 2 divide a n, es decir n es una potencia de 2.
Por inducción es claro que las potencias de dos funcionan. Por lo tanto las n que funcionan son las potencias de dos.
FIN
Podemos suponer SPG que al inicio cada vaso tiene una cantidad 1 de agua. Sea n el número a analizar y sea $2^{k}|| n$, entonces $n=2^{k}i$ con i impar mayor a 1, entonces demostraré que no se puede. Sea p primo tal que p|i, entonces p|n. Vemos que si se puede concluir, tendremos n-1 vasos vacíos y 1 vaso con cantidad n de agua, entonces todos los vasos tienen una cantidad múltiplo de p de agua. Demostraré que si en algún momento todos los vasos llegaron a una posición múltiplo de p, es porque en la posición anterior, todos los vasos eran múltiplos de p. Supongamos que tenemos una posición en que no todos los vasos son múltiplos de p, pero que en un movimiento podamos llegar a que todos sean múltiplo de p, es porque dicha posición tiene n-2 vasos múltiplos de p, y los otros dos no divisibles por p. Ahora bien, sean $a_{1}$ y $a_{2}$ dichos vasos, y $a_{1}<a_{2}$, los vasos pasarán a las posiciones $2a_{1}$ y $a_{2}-a_{1}$, pero ninguno es múltiplo de p, contradicción. Entonces si n cumple debe ser potencia de 2. Es sencillo ver que los caso para n=1,2 funcionan. Supongamos que funciona para $2^{k}$, entonces demostraré que funciona para $2^{k+1}$. Separamos los vasos en dos montones con la misma cantidad de ellos, y sabemos que cada uno de estoscojuntos los podemos llevar a que uno contenga el agua de todos. Ahora, quedarían dos vasos con la misma cantidad de agua (uno en cada conjunto), y los operamos entre ellos, y es fácil notar que si se puede. Por lo tanto, para toda potencia de dos son los casos que cumplen.
Bien Chuck, Manuel y George.
Entonces si un vaso no tiene la cantidad suficiente, se le echa toda, o no se le echa?
Por ejemplo si un vaso tiene 2 y el otro 1 y quieres vaciar del segundo al primero.
Publicar un comentario