¿Cuál es la forma más eficaz de poner todas las piedras en un montón?

Question

Hay $k$ montones de $n_i$ piedras, en cada movimiento puedes elegir dos pilas con tamaños $a$ y $b$ y si $a \ge b$ tomar de la primera pila $b$ piedras y poner a la segunda, por otro lado si $a < b$ - tomar $a$ del segundo y ponerlos en el primero. ¿Cuál es la condición necesaria y suficiente para poner todas las piedras en un mismo montón y cuál es el menor número de operaciones de este tipo para hacerlo?

La primera cuestión es bastante sencilla: si $\frac{\sum{n_i}}{\gcd(n_1, n_2 ... n_k)}=2^p$ Pero no sé la respuesta para la segunda, puedo probar que es $O(kp)$ pero creo que podemos hacerlo mucho más rápido y mi hipótesis es $O(k + p))$ . ¿Puede alguien demostrarlo o negarlo?

Puede que exista alguna estimación mejor para el número de movimientos, si la tienes, por favor dímelo.

Answer 1

Parece lo siguiente.

Arreglar $p$ y $k$ . Sin pérdida de generalidad, podemos suponer que $\gcd(n_1, n_2 ... n_k)=1$ .

Al principio calculamos el número $P(p,k)$ de diferentes posiciones iniciales posibles $(n_1, n_2 ... n_k)$ . Es bien conocido y fácil de demostrar que el número $S(K,k)$ de diferentes secuencias $(n_1, n_2 ... n_k)$ de enteros no negativos (que no necesariamente satisfacen la condición $\gcd(n_1, n_2 ... n_k)=1$ ) con $\sum n_i=K$ es igual a ${K+k-1}\choose{k-1}$ . Afortunadamente, en nuestro caso $K=2^p$ es una potencia de un número primo $2$ . Por lo tanto, tenemos que $\gcd(n_1, n_2 ... n_k)\not=1$ si todos $n_i$ están en paz. Por lo tanto, el número $P(p,k)$ de diferentes secuencias $(n_1, n_2 ... n_k)$ que satisface la condición $\gcd(n_1, n_2 ... n_k)=1$ con $\sum n_i=K$ es igual a $S(K,k)–S(K/2,k)$ .

Ahora tenemos el árbol de posiciones con la inicial $P(p,k)$ vértices y $k$ raíces y en cada movimiento estamos bajando a la raíz. Es fácil comprobar que si una posición $B$ se obtuvo de una posición $A$ moviendo piedras de $i$ -a la pila a $j$ -th, entonces la posición $A$ está determinada de forma única por $B$ , $i$ y $j$ . Por lo tanto, cada vértice del árbol no tiene más que $k(k-1)$ vértices por encima de ella. Por lo tanto, si podemos llegar a una raíz del árbol desde cada uno de sus vértices después de bajar como máximo $m$ se mueve, deberíamos tener la desigualdad $k[k(k-1)]^{m-1}\ge P=(p,k)$ . En particular, para los grandes $k$ y $2^p>>k$ debería dar un límite inferior asintótico en $m$ de orden $\frac{pk}{\operatorname{log}_2 k}-k$ .