Rompecabezas de matemáticas / lógica
¿Alguien tiene alguna idea de cómo resolver este problema? Mi amigo me preguntó al respecto y me ha estado molestando durante unos días. Traté de abordarlo por inducción (el caso base con dos personas es sencillo, pero me quedé atascado en el paso inductivo). De todos modos, pensé que era un problema divertido y tenía curiosidad por saber cómo abordarlo. ¡Cualquier consejo sobre posibles soluciones sería fantástico!
Algunas personas se paran en círculo intercambiando objetos. Cada uno de ellos comienza con un número par de chocolates, no necesariamente iguales. Cada minuto, cada una de las personas pasa la mitad de sus objetos a la persona de su derecha. Si alguien acaba con un número impar de bombones, coge otro objeto de un frasco en el centro. Demuestre que independientemente de la distribución inicial de chocolates, después de un número finito de pasos, todos terminan con el mismo número de objetos.
Respuestas
Podemos describir una situación con tres números. $(M,m,r)$, dónde $2M$ es la cantidad máxima que tiene un jugador, $m$ es la cantidad mínima, y $r$ es el número de jugadores con $2m$.
Si un jugador como $2a$ piezas y su vecino izquierdo tiene $2b$ piezas, en la próxima ronda, este jugador tendrá $ (2a-a)+b= a+b\le 2M$piezas. Incluso si$a+b$ es extraño, es $\le 2M-1$ y luego de volver a llenarlo del frasco, todavía es $\le 2M$. Asimismo, la nueva cantidad es$\ge 2m$ con igualdad si y solo si $a=b=m$. Concluimos que una situación$(M,m,r)$ se convierte en $(M',m',r')$ con $m\le m'\le M'\le M$. Además, si$m'=m$, luego $r'\le r$.
Pero no puede pasar que $(M',m',r')=(M,m,r)$ a no ser que $M=m$. De hecho, si$m<M$, entonces debe haber alguna persona con $2m$piezas mientras que su vecino de la izquierda tiene más. Entonces esta persona tendrá$>2m$ piezas en la siguiente ronda, lo que significa que $m'>m$ o al menos $r'<r$.
En cualquier caso, si $M>m$, entonces solo se necesitan pasos finitos hasta que $M-m$disminuye en al menos uno. Entonces, aún después de un número finito de pasos, llegamos$M=m$.
Considere una persona con la menor cantidad de chocolates en un paso. Ella pasa la mitad de sus chocolates, pero recibe la mitad de los chocolates de alguien que tiene al menos tantos chocolates como ella. Entonces, su número de chocolates aumenta o permanece igual si la persona a su izquierda también tiene el mismo número de chocolates. Por lo tanto, la menor cantidad de chocolates en un escalón nunca disminuye.
Ahora suponga que una persona tiene más que lo mínimo. Si el menor número de chocolates es$L$ y la persona con más de lo que menos tiene $L + 2a$ entonces él regala $\frac 12L + a$ pero consigue al menos $\frac 12L$ y también lo ha hecho $L + a > L$. Entonces, una persona que no tiene lo mínimo en un paso no puede ir, no lo haga en el siguiente paso.
Por lo tanto, la menor cantidad de chocolates en un paso nunca puede disminuir a un número menor en el siguiente paso. Y si la menor cantidad de chocolates en un paso es igual que la menor cantidad de chocolates en el siguiente paso, eso solo puede ocurrir si una persona con la menor cantidad de chocolates estaba a la derecha de una persona con la misma cantidad de chocolates. y esa persona termina con la misma cantidad de chocolates.
[Nota: una persona con más que el número mínimo anterior puede terminar en el siguiente paso con el nuevo número mínimo que sea mayor que el número mínimo anterior, pero esa persona puede terminar con el número mínimo anterior .]
Pero si no todas las personas tienen la misma cantidad de chocolates (si lo tienen, terminamos) entonces hay una cadena máxima de personas con la menor cantidad de chocolates $n$gente larga. Cada paso, la persona al final de la cadena tendrá más chocolates y la cadena se acortará en uno. (Y del párrafo anterior sabemos que ninguna persona nueva terminará con esa cantidad mínima anterior ).$n$ pasos todos tendrán más chocolates y el menor número posible aumentará.
Entonces, si hay un límite superior para el número máximo de chocolates posibles, entonces el menor número al final de un paso eventualmente alcanzará un punto en el que todos tengan el mismo número de chocolate para un número igual o menor que ese máximo potencial.
Así que considere la mayor cantidad de chocolates que una persona tiene al final de un paso. Llámalo$M$En el siguiente turno, esa persona da la mitad de los chocolates y recibe la mitad o menos chocolates. Si recibe tantos como regaló, tiene una cantidad par y termina con el mismo número de$M$. Si recibe menos, incluso si agrega un chocolate, termina como máximo con lo que comenzó.
Entonces ... la mayor cantidad de chocolates que una persona puede tener es un $M=$ la mayor cantidad de chocolates que alguien tuvo al paso $1$. La menor cantidad de chocolates que una persona puede tener es$L=$ los menos chocolates que alguien tenía al paso $1$pero ese mínimo siempre aumentará en un número finito de pasos a menos que todas las personas tengan el mismo número. Como hay un límite de cuán alto puede ser el mínimo, el proceso debe terminar en igualdad. Finalmente.