Juego "Haz que todos los números sean iguales"

Question

Este problema fue publicado originalmente en math.stackexchange.

Dado que no hay respuestas ni comentarios allí aún, lo estoy publicando aquí para saber si ya es conocido y factible.

Aquí está el problema, ligeramente restringido con respecto al original:

partiendo de un multiconjunto de $6$ números enteros, lo modificamos repetidamente reemplazando dos elementos $a,b$ a elección con $a+b,a+b$. ¿Es posible hacer que todos los elementos sean iguales para cualquier elección del multiconjunto original? ¿Cambia la respuesta si reemplazamos "entero" por "racional"?

Nótese que el autor original en math.stackexchange parece tener una prueba para $n=3,5$ elementos. Como se señala en los comentarios a continuación, es imposible igualar $a,a,b$ con $a \gt b \ge 0$, porque tendrás otra secuencia de la misma forma.

Answer 1

Reclamo que siempre es posible hacer que todos los enteros sean iguales entre sí. Para ver esto, considera las transformaciones permitidas

1. $(a,b,c,d,e,f)\mapsto(a+b,a+b,c,d,e,f)$,

2. $(a_1,\dots,a_6)\mapsto(a_{\sigma(1)},\dots,a_{\sigma(6)}) y

3. $(a,b,c,d,e,f)\mapsto(a/n,b/n,c/n,d/n,e/n,f/n)$ siempre que $a/n,b/n,c/n,d/n,e/n,f/n$ sean todos enteros.

Escribiremos $(a,b,c,d,e,f)\mapsto^*(g,h,i,j,k,l)$ si $(g,h,i,j,k,l)$ se puede obtener de $(a,b,c,d,e,f)$ mediante una secuencia de transformaciones permitidas. Observamos que si $(a,b,c,d,e,f)\mapsto^*(1,1,1,1,1,1)$, entonces podemos transformar $(a,b,c,d,e,f)$ en $(n,n,n,n,n,n)$ para algún $n$ usando solo las transformaciones $1$ y $2$, pero la transformación 3 facilita usar la inducción para mostrar que siempre podemos obtener $(a,b,c,d,e,f)\mapsto(1,1,1,1,1,1)$.

Observamos que $(a,b,c,d,e,f)\mapsto^*(a+b+c+d,a+b+c+d,a+b+c+d,a+b+c+d,e+f,e+f)$. Ahora, establezcamos $\alpha=a+b+c+d,\beta=e+f$. Reclamo que $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)=(0,0,0,0,0,0)$ o $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(1,1,1,1,1,1)$ por inducción en el cuadrado de la norma $\ell^2$ $4\alpha^2+2\beta^2$ de $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)$.

Caso 0: $\alpha=0,\beta=0$. Esto es trivial.

Caso 1: $\alpha=0,\beta\neq 0$. En este caso, $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(\beta,\beta,\beta,\beta,\beta,\beta)\mapsto^*(1,1,1,1,1,1)$.

Caso 2: $\alpha\neq 0,\beta=0.$

$(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(\alpha,\alpha,\alpha,\alpha,\alpha,\alpha)\mapsto^*(1,1,1,1,1,1)$.

Caso 3: $\alpha\neq 0,\beta\neq 0$, $\alpha$ es par.

Si $\alpha$ es par, entonces $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(\alpha,\alpha,\alpha,\alpha,2\beta,2\beta)\mapsto^*(\alpha/2,\alpha/2,\alpha/2,\alpha/2,\beta,\beta)$ y $(\alpha/2,\alpha/2,\alpha/2,\alpha/2,\beta,\beta)\mapsto^*(1,1,1,1,1,1)$ por la hipótesis de inducción.

Caso 4: $\alpha\neq 0,\beta\neq 0$, $\beta$ es par. $(\alpha,\alpha,\alpha,\alpha,\beta,\beta)\mapsto^*(2\alpha,2\alpha,2\alpha,2\alpha,\beta,\beta)\mapsto^*(\alpha,\alpha,\alpha,\alpha,\beta/2,\beta/2)$, y $(\alpha,\alpha,\alpha,\alpha,\beta/2,\beta/2)\mapsto^*(1,1,1,1,1,1)$ por la hipótesis de inducción.

Caso 5: $\alpha\neq 0,\beta\neq 0$, $\alpha,\beta$ son ambos impares.

Sea $\alpha=2\gamma+1,\beta=2\delta+1.$ Entonces $(\alpha,\alpha,\alpha,\alpha,\beta,\beta) \mapsto^*(2(2\gamma+1),2(2\gamma+1),2(\gamma+\delta+1),2(\gamma+\delta+1),2(\gamma+\delta+1),2(\gamma+\delta+1))$ $\mapsto^*(2\gamma+1,2\gamma+1,\gamma+\delta+1,\gamma+\delta+1,\gamma+\delta+1,\gamma+\delta+1)=(\alpha,\alpha,\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2}).$

Si $\alpha=\beta$, entonces claramente $(\alpha,\alpha,\alpha,\alpha,\beta,\beta) \mapsto^*(1,1,1,1,1,1)$, y si $\alpha\neq\beta$, entonces podemos usar la hipótesis de inducción para concluir que $(\alpha,\alpha,\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2},\frac{\alpha+\beta}{2})\mapsto^*(1,1,1,1,1,1).$

Answer 2

El problema es soluble para números reales, e incluso para cualquier tupla $(x_1, \dots, x_n)$ con $n$ par y $x_i$ real (o en cualquier grupo abeliano) para todo $i$. (Para la imposibilidad para tuplas de longitud impar ver este comentario o este comentario.)

Para valores racionales, el problema se resuelve en la respuesta de Joseph Van Name y el comentario de Jarosaw Basiok. Reduciremos el caso real al caso racional. Nota que esto también implica que el número de operaciones necesarias para una longitud de tupla fija está realmente acotado.

Solución para $n=6$:

Una tupla arbitraria puede reducirse fácilmente a la forma $(x, x, y, y, y, y)$ (en cinco pasos). Sea $z = x + y$. Entonces

$$\begin{align} (x, x, y, y, y, y) &\to (z,z,x,y,y,y) && (\text{sumar $x$ y $y$})\\ &\to (z, z+x, z+x, y, y, y) && (\text{sumar $z$ y $x$})\\ &\to (z, 2z, 2z, z+x, y, y) && (\text{sumar $z+x$ y $y$})\\ &\to (z, 2z, 3z+x, 3z+x, y, y) && (\text{sumar $2z$ y $z+x$})\\ &\to (z, 2z, 4z, 4z, 4z, 4z) && (\text{sumar $3z+x$ y $y$ dos veces}). \end{align}$$ En este punto, la tupla es equivalente a la tupla de enteros $(1,2,4,4,4,4)$ y podemos proceder como en la respuesta de Joseph Van Name.

Solución para una longitud de tupla par arbitraria $n$:

Podemos hacer que $2^k$ elementos arbitrarios sean iguales (con $k2^{k-1}$ movimientos), por lo que reducimos la lista a la forma $(x, \dots, x, y, \dots, y)$ haciendo que los primeros $2^{[\log_2(n)]}$ elementos sean iguales y luego haciendo que los últimos $2^{[\log_2(n)]}$ elementos sean iguales. Por lo tanto, asumimos que la lista tiene la forma $(x,\dots,x,y,\dots,y)$ donde $x$ e $y$ aparecen $X$ y $Y$ veces respectivamente, y tanto $X$ como $Y$ son pares.

Podemos asumir que $X, Y > 0$, que $y$ no es cero (de lo contrario, aplicar $(x, 0) \to (x,x)$ repetidamente) y que $x/y$ es irracional. Posteriormente, todas las entradas permanecen en $\mathbb Z x + \mathbb Z y$. Sea $z = x + y$.

Ahora considera una tupla arbitraria $(x_1, \dots, x_n) \in (\mathbb Z x + \mathbb Z y)^n$ y define contadores $a, b, c \ge 0$ de la siguiente manera:

$$\begin{align} a &= \#\{i: x_i \in \mathbb Z z + x\},\\ b &= \#\{i: x_i \in \mathbb Z z + y\},\\ c &= \#\{i: x_i \in \mathbb Z z\}. \end{align}$$

Observa que con la operación $(x_i,x_j) \to (x_i+x_j,x_i+x_j)$ podemos hacer cualquiera de lo siguiente:

1. si $a, b> 0$, disminuir $a$ y $b$ en $1$ e incrementar $c$ en $2$,
2. si $a, c> 0$, disminuir $c$ en $1$ e incrementar $a$ en $1$,
3. si $b, c> 0$, disminuir $c$ en $1$ e incrementar $b$ en $1$.

Al hacer 2+1 o 3+1 obtenemos las siguientes operaciones adicionales:

4. si $a,b,c > 0$, disminuir $b$ en $1$ e incrementar $c$ en $1$,
5. si $a,b,c > 0$, disminuir $a$ en $1$ e incrementar $c$ en $1$.

Ahora, empezando desde la tupla $(x,\dots, x,y,\dots,y)$, inicialmente tenemos $(a,b,c) = (X,Y,0)$. Después de la operación 1 tenemos $(a,b,c) = (X-1,Y-1,2)$. Haciendo la operación 4 y 5 muchas veces, alcanzamos $(a,b,c) = (1,1,n-2)$. Ahora la operación 1 completa el trabajo.

Answer 3

Este es simplemente un añadido a las publicaciones de jackdean y Joseph Van Name para escribir el proceso combinado para $n = 6$ explícitamente. Cada adición reemplaza los dos elementos "en su lugar" con su suma.

1. Suma 1 y 2. $(a + b, a + b, c, d, e, f)$
2. Suma 3 y 4. $(a + b, a + b, c + d, c + d, e, f)$
3. Suma 5 y 6. $(a + b, a + b, c + d, c + d, e + f, e + f)$
4. Suma 3 y 5. $(a + b, a + b, c + d + e + f, c + d, c + d + e + f, e + f)$
5. Suma 4 y 6. $(a + b, a + b, c + d + e + f, c + d + e + f, c + d + e + f, c + d + e + f)$.

Renombra $x = a + b, y = c + d + e + f$, ahora tenemos $(x, x, y, y, y, y)$.

6. Suma 1 y 3. $(x + y, x, x + y, y, y, y)$
7. Suma 1 y 2. $(2x + y, 2x + y, x + y, y, y, y)$
8. Suma 1 y 4. $(2x + 2y, 2x + y, x + y, 2x + 2y, y, y)$
9. Suma 1 y 2. $(4x + 3y, 4x + 3y, x + y, 2x + 2y, y, y)$
10. Suma 1 y 5. $(4x + 4y, 4x + 3y, x + y, 2x + 2y, 4x + 4y, y)$
11. Suma 2 y 6. $(4x + 4y, 4x + 4y, x + y, 2x + 2y, 4x + 4y, 4x + 4y)$

Renombra $z = x + y = a + b + c + d + e + f$, entonces nuestra tupla es $(4z, 4z, z, 2z, 4z, 4z)$

12. Suma 1 y 3. $(5z, 4z, 5z, 2z, 4z, 4z)$
13. Suma 1 y 3. $(10z, 4z, 10z, 2z, 4z, 4z)$
14. Suma 2 y 4. $(10z, 6z, 10z, 6z, 4z, 4z)$
15. Suma 2 y 5. $(10z, 10z, 10z, 6z, 10z, 4z)$
16. Suma 4 and 6. $(10z, 10z, 10z, 10z, 10z, 10z)$

(gracias a Emil Jerábek por encontrar un atajo de 2 pasos en la parte final)

Answer 4

Con el propósito de determinar cuántos pasos son necesarios para un $n$ arbitrario:

Supongamos que $n \geq 6$ es par y no es una potencia de $2$ (ya tenemos una respuesta fácil para cuando lo es). Sea $k = \lfloor \log_2(n) \rfloor$, y $m = \lfloor \log_2(\frac{2n}{3})\rfloor$. Entonces no es difícil ver que $2^m + 2^k \geq n$, y que $\frac{n}{3} \leq 2^m \leq \frac{2n}{3}$.

Comenzamos el proceso igualando los primeros $2^k$ elementos de nuestra tupla. Una vez hecho esto, igualamos los últimos $2^m$ elementos de nuestra tupla. Como $2^k + 2^m \geq n$, todos los elementos de nuestra tupla recién igualados toman uno de dos valores, con $a$ copias de un valor $x$ y $b$ elementos del otro valor $y$. Sin pérdida de generalidad, supongamos que $a \geq b$; notar que por las restricciones anteriores, tanto $a$ como $b$ son pares, y que $a \leq 2b$.

Por lo tanto, podemos dividir nuestra tupla de $n$ en $\frac{a - b}{2}$ séxtuples de la forma $x, x, x, x, y, y$, y $2b - a$ dupletos de la forma $x, y$. Sea $z = x + y$. Podemos convertir el séxtuplo en seis copias de $8z$ de la siguiente manera:

$(x, x, x, x, y, y) \rightarrow (x+y, x, x, x, x+y, y) \rightarrow (x+2y, x, x, x, x+y, x+2y)$

$\rightarrow (2x+2y, 2x+2y, x, x, x+y, x+2y) \rightarrow (3x+4y, 2x+2y, x, x, x+y, 3x+4y)$

$\rightarrow(4x+4y, 2x+2y, 4x+4y, x, x+y, 3x+4y)$

$\rightarrow (4x+4y, 2x+2y, 4x+4y, 4x+4y, x+y, 4x+4y) = (4z, 2z, 4z, 4z, z, 4z)$

$\rightarrow (4z, 3z, 4z, 4z, 3z, 4z) \rightarrow (4z, 6z, 4z, 4z, 6z, 4z) \rightarrow (4z, 12z, 4z, 4z, 12z, 4z)$

$\rightarrow (16z, 16z, 4z, 4z, 12z, 4z) \rightarrow (16z, 16z, 16z, 4z, 16z, 4z) \rightarrow (16z, 16z, 16z, 16z, 16z, 16z)$

y podemos convertir el dupleto en dos copias de $16z$ sumándolo 5 veces.

En total, esto toma: $k*2^{k - 1}$ pasos para igualar los primeros $2^k$ elementos, $m*2^{m - 1}$ pasos para igualar los últimos $2^m$ elementos, $13*\frac{a - b}{2}$ pasos para llevar todos los séxtuples a $8z$, $\frac{5}{2}*(2b - a)$ pasos para llevar los dupletos a $16z$

Las dos últimas partes pueden combinarse fácilmente para dar $\frac{8a - 3b}{2} = \frac{11}{2}a - \frac{3}{2}n$ pasos. Notar que $a \leq \frac{2n}{3}$, así que los pasos finales toman a lo sumo $\frac{13n}{6}$ pasos.

La igualación de $2^k$ elementos de manera obvia toma $k2^{k - 1}$ pasos (y sospecho que no se puede mejorar), así que al usar $m \leq k \leq \log_2(n)$, obtenemos un límite de $n \log_2{n} + \frac{13n}{6}$ pasos. Notar que este límite no es ajustado; podemos mejorar el coeficiente para $n \log_2{n}$ a $\frac{3}{4}$ al considerar los casos de $m = k$ y $m = k - 1$ por separado, lo que ya nos coloca aproximadamente al doble del límite en el escenario "fácil" donde $n$ es una potencia de 2.

---

Un enfoque alternativo e inductivo para $n \geq 10$:

Claramente tenemos una respuesta para $n = 0, 2, 4, 6, 8$. Si $n$ es divisible por $4$, entonces podemos dividir la tupla de $n$ en dos partes de longitud par, igualar cada una (por inducción), y luego mezclarlas de manera obvia.

Si $n$ no es divisible por $4$, entonces dividimos la tupla de $n$ en dos partes de longitud par cuyas longitudes difieren por $2$. Igualamos ambas. Luego tomamos 3 elementos de la parte más pequeña y 5 elementos de la parte más grande, dando un octuplet de la forma $(x, x, x, y, y, y, y, y)$. Seguimos los siguientes pasos para el octuplet:

\begin{align} (x, x, x, y, y, y, y, y) &\rightarrow (x, x, x+y, x+y, y, y, y, y) \\ &\rightarrow (x, 2x+y, 2x+y, x+y, y, y, y, y)\\ &\rightarrow (2x+y, 2x+y, 2x+y, 2x+y, y, y, y, y)\\ &\rightarrow (2x+2y, 2x+2y, 2x+2y, 2x+2y, 2x+2y, 2x+2y, 2x+2y, 2x+2y) \end{align} donde cada línea excepto la última toma un paso, y la última toma 4. Luego quedan $\frac{n - 8}{2}$ copias tanto de $x$ como de $y$ fuera del octuplet, así que podemos agruparlos y sumarlos. Finalmente, podemos sumar copias de $x$ y $y$, para que todos los elementos terminen siendo iguales a $2x + 2y$.

Si $f(n)$ denota el número de pasos que este proceso recursivo toma para igualar todos los elementos, entonces obtenemos que $f(n) = \begin{cases} 2 f(\frac{n}{2}) + \frac{n}{2} & 4|n \\ f(\frac{n - 2}{2}) + f(\frac{n + 2}{2}) + n - 1 & 4\not| n \end{cases}$

Nuestros casos base actualmente son $f(0) = 0, f(2) = 1, f(4) = 3, f(6) = 16, f(8) = 12$. Creo que esta relación de recurrencia da una respuesta asintótica de $f(n) \sim \frac{3}{4} n \log_2(n)$, ya que la partición "peor" (cuando $4 \not | n$) siempre incluye una parte con longitud divisible por 4. Esta no es una solución óptima - para $n = 10$, hay una solución que funciona en 24 pasos basada en dividir en un dupleto y un octuplet, mientras que lo anterior toma 28 pasos, y para $n = 14$ es más rápido igualar todos los 8 en lugar de solo los últimos 6.