Disminuyendo enteros en la pizarra

Question

Hay $n \geq 2$ copias de un entero $k > 0$ escrito en la pizarra. Un movimiento consiste en elegir un entero $m > 0$ en la pizarra, y reemplazarlo junto con otro entero en la pizarra (puedes elegir cuál) por el entero $m-1.

Por ejemplo, si tienes los números $(3,0,1)$ en la pizarra, un movimiento puede cambiarlos a $(2,2,1)$ o $(2,0,2)$ o $(3,0,0)$ o $(0,0,0).

¿Cuál es el número máximo posible $f(n,k)$ de movimientos que puedes hacer? Una respuesta asintótica sería suficiente (creo que podría ser $O(kn^2)$).

Answer 1

Esa es otra respuesta que surge de todas las ideas en otras respuestas.

Considera un pizarrón $B$ con $n$ números $a_1,a_2,\dots,a_n$, tales que $a_i\le a_{i+1}$.

Sea $W$ la función de peso definida por $$W(B)=\sum_{i=1}^n \sum_{k=1}^{i-1}\binom{a_i}{k} $$

Hacemos un movimiento en $B$. Elegimos $1\le i\le n$, y $1\le j\le n$ (con $j\neq i$), y transformamos $a_i$ (y $a_j$) en $a_{i}-1$ para obtener el pizarrón $B'$ con $n$ valores $b_1,b_2,\dots,b_n$ ($b_i\le b_{i+1}$ : Ordenamos los valores nuevamente)

• si $a_j\ge a_i$, entonces ambos valores son reducidos. Por inducción trivial, $b_i\le a_i$ (y para algún $i>1$, tenemos $b_i) y $W(B').

• si $a_j, podemos considerar (sin pérdida de generalidad) que $a_i>a_{i-1}$. Por lo tanto $B'$ será tal que :

  • para $i< k\le n$ : $b_k=a_k$
  • $b_{i-1}=b_i=a_i-1$ (ese es el antiguo $a_i$ y $a_j$)
  • para $j\le k : $b_k=a_{k+1}$ (simplemente movemos el antiguo $a_j$ desde el índice $j$ al índice $i-1$)
  • para $k : $b_k=a_k$

Por lo tanto :

$$W(B)-W(B')=\sum_{k=j}^{i}\sum_{l=1}^{k-1}\binom{a_k}{l}-\binom{b_k}{l}$$ Para $k=i$, tenemos : $$\left(\sum_{l=1}^{i-1}\binom{a_i}{l}-\binom{a_i-1}{l}\right)=\sum_{l=1}^{i-1}\binom{a_i-1}{l-1}=1+\sum_{l=1}^{i-2}\binom{b_{i-1}}{l}$$

Por lo tanto (dejamos que el lector atento entienda las cancelaciones que vienen de $b_k=a_{k+1}$) $$W(B)-W(B')=1+\sum_{l=1}^{j-1}\binom{a_j}{l}+\sum_{k=j+1}^{i-1}\binom{a_k}{k-1}>0$$

Observa que ahora, si tomas $j=1$ y $a_i$ ($i>1$) el menor $a_k>0$, obtendrás

$$W(B)-W(B')=1$$

Entonces $W(B)$ es la cantidad máxima de movimientos que puedes hacer en $B$.

$$f(n,k)=\sum_{i=1}^{n-1} (n-i)\binom{k}{i} $$

Answer 2

Como señaló @Alex, lo siguiente demuestra la optimalidad local de su algoritmo y el de @Yong en cierta medida. De hecho, la medida que utilizo no puede probar la optimalidad global en estados generales, ya que la puntuación para $(5,5,1,0,0)$ es $56$ mientras que para $(5,4,4,4,4)$ es $58$. En dos pasos óptimos cada uno, las secuencias llegan respectivamente a $(5,4,4,0,0)$ y $(5,4,4,2,2)$, donde es fácil ver que la segunda es al menos dos pasos mejor.

5,4,4,4,4    5,5,1,0,0
5,4,4,3,3    5,4,4,1,0
5,4,4,2,2    5,4,4,0,0

Sea $T$ igual a $k+1$. $a_i$. Primera observación, si estamos seleccionando $i$ y $j$, entonces siempre deberíamos reemplazarlos por el mayor entre $a_i-1$ y $a_j-1$. Escriba los números en orden decreciente y léalo como una expansión de base $(T+1)$ para que $a_i$ corresponda a $a_i(T+1)^i$. Entonces $j>i$.

Ahora, después de la operación, el $a_j-1$ que reemplaza a $a_i$ se mueve a $j-1\ge i$, y todo lo que está en medio se desplaza hacia la derecha. Entonces la operación a realizarse es restar $\delta \ge (T+1)^j - T\times(T+1)^k >0$. Tenga en cuenta que por construcción, o bien $a_j-1 \ge a_i$ o bien $a_j = a_i$.

Así que en primer lugar, el número base $(T+1)$ disminuye. Podemos ver qué hace que esta disminución sea la más pequeña. Tenemos los límites $$(T+1)^{j-1} \leq \delta \le (T+1)^j$$

Por lo tanto, para un dado $i$, $j$ debería ser lo más bajo posible.

Si $a_i =0$, esto significa que $j$ debería ser el más pequeño tal que $a_j>0$, y luego $i$ no importa.

De lo contrario, $j = i+1$, y luego los mismos límites nos dicen que $i$ debería ser lo más bajo posible.

Aquí hay algunos límites superiores.

---

Primero, comenzando desde cualquier estado del tablero, solo podemos hacer finitos movimientos. Para ver esto, primero note que en cualquier movimiento, no podemos aumentar el máximo. Ahora, hacemos una inducción en el número de términos en el tablero.

Observe que una vez que un término maximal ocurre como $i$ o $j$ en un movimiento $M(i,j)$ como en el comentario y respuesta de Ewan, no puede regresar a su valor original, ya que si $T$ es el valor máximo, entonces cada reemplazo es con a lo sumo $T-1$. Ahora, es suficiente mostrar que el máximo tiene que disminuir en un número finito de movimientos. Supongamos, en contrario, que haya una secuencia infinita de movimientos que conserva el máximo. Entonces, algún valor máximo no es utilizado en un movimiento en absoluto. Pero por inducción, solo hay finitos movimientos posibles que se pueden hacer en el resto de los términos.

Esto también nos dice que no puede haber ningún conjunto de estados periódicos, por lo que el número total posible de estados ($-1$) es un límite superior. El número de estados es el número de secuencias no decrecientes de longitud $n$ donde cada término es $\le k$. Esto está dado por $\binom{k+n}{k}-1$. Un límite superior ligeramente mejor se muestra a continuación.

Ahora, suponga que para un multiconjunto de tamaño $n$, con máximo $T$, el máximo número de movimientos posibles (sobre todos esos multiconjuntos) es $f(T,n)$. Obviamente, $$f(T,2 ) = T$$. Por el mismo argumento de arriba, $$f(T,n+1) \le f(T,n)+f(T-1,n) +1 $$ Por inducción, $f(T,n) \le \binom{T+n-1}{T} - 1 \le (T+1)^n-1$ pero esto parece tener margen de mejora.

El límite superior de @AlexRavsky es mucho mejor para un $k$ fijo, mientras que este es mejor para un $n$ fijo.

Aquí hay algunos valores reales para los $k,n$ definidas en el problema, y el mejor de los dos límites superiores anteriores, $\binom{k+n-1}{n-1}-1$ y $n(2^k-1)$:

k\n|   2   3   4   5   6   7   8          k\n|   2   3   4   5   6   7   8  
---+-----------------------------         ---+-----------------------------
 1 |   1   2   3   4   5   6   7           1 |   1   2   3   4   5   6   7
 2 |   2   5   8  11  14  17  20           2 |   2   5   9  14  18  21  24
 3 |   3   9  16  23  30  37  44     <     3 |   3   9  19  34  42  49  56
 4 |   4  14  28  43  58  73  88     =     4 |   4  14  34  69  90 105 120
 5 |   5  20  45  75 106 137               5 |   5  20  55 125 186 217 
 6 |   6  27  68 124 186                   6 |   6  27  83 209 378 
 7 |   7  35  98 196                       7 |   7  35 119 329

Answer 3

Puedo demostrar una respuesta exacta para $n=3$, la cual puedo extender a un algoritmo para $n\geq 4$.
El número de pasos parece corresponder a la tabla de ronno.

[1] Mejor algoritmo para $n=3
Sea $n=3$ y empezamos con $(k,k,k)$.
Consideramos el algoritmo:
Una serie de $M(1,2): (k,k,k)\to (0,0,k)$.
$M(3,2): (0,0,k)\to (0,k-1,k-1)$
Una serie de $M(1,2): (0,k-1,k-1)\to (0,0,k-1)$.
$M(3,2): (0,0,k-1)\to (0,k-2,k-2)$
$\dots$

Esto me dará $\dfrac{(k+1)(k+2)}{2}-1=\dfrac{k^2+3k}{2}$ movimientos.

Afirmo que es el máximo mediante inducción.
Claramente esto es cierto para $k=0$.
Ahora consideramos $(k+1,k+1,k+1)$.
El algoritmo me dice que $\dfrac{(k+1)^2+3(k+1)}{2}=\dfrac{k^2+5k+4}{2}$ es un límite inferior.

El primer movimiento debe darme $(k,k,k+1).
Si el siguiente lo hago $(k,k,k)$, el máximo que puedo obtener es $2+\dfrac{k^2+3k}{2}=\dfrac{k^2+3k+4}{2}<\dfrac{k^2+5k+4}{2}$.
Por lo tanto, solo puedo superar el límite inferior haciendo mi próximo movimiento $(k-1,k-1,k)..
Es claro que usando este argumento, debo llegar a $(0,0,k+1)..
De lo contrario, en el paso $r+1$ obtendré $(k-r,k-r,k+1)\to (k-r,k,k)..
Entonces, el máximo de movimientos es $r+1+\dfrac{k^2+3k}{2}=\dfrac{k^2+3k+2+2r}{2}$, lo cual es siempre $\leq \dfrac{k^2+5k+4}{2}$ ya que $r\leq k+1

[2] Extensión a $n \geq 4
La generalización más "natural" de este algoritmo para $n\geq 4$ es:
(1) Reducir a $(0,0,0,k,\dots,k)$ vía el algoritmo $n=3$.
(2) $(0,0,0,k,\dots,k)\to (0,0,k-1,k-1,\dots,k)$.
(3) $(0,0,k-1,k-1,\dots,k)\to (0,k-2,k-2,k-1,\dots,k)$.
(4) Repetir el algoritmo $n=3$ en $(0,k-2,k-2)$.
(5) Repetir el procedimiento. Por ejemplo, el siguiente "inicio" sería $(0,k-3,k-3,k-2,\dots,k)

Debería ser posible derivar una fórmula, pero no tengo idea de cómo hacerlo de manera corta.

Editar 1: Las primeras fórmulas son
$n=3: \dfrac{k(k+3)}{2}$, $n=4: \dfrac{k(k^2 + 3 k + 14)}{6}$, $n=5: \dfrac{k(k^3+2k^2+23k+70)}{24}$.

En general, el algoritmo parece dar alrededor de $O(k^{n-1})$.

La computación se realiza usando:
$$g(n,k)=k+\sum_{i=1}^{k-1} g(n-1,i)$$.
$$f(n,k)=\sum_{i=2}^{n} g(i,k)$$
con condición inicial $g(2,k)=k$, donde $f(n,k)$ es la solución que queremos.
$g(n,k)$ es el número de pasos para $(0,0,\dots,0,k)$.

Answer 4

Hice un pequeño programa para calcular el valor $f(n,k)$ para pequeños valores de $n$ y $k$.

$$\begin{array}{l|cc} k^\mbox{$\;\;n$}& 2& 3& 4 & 5& 6 & 7 & 8 & 9 & 10 & 11\\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 2 & 5 & 8 & 11 & 14 & 17 & 20 & 23 & 26 & 29 \\ 3 & 3 & 9 & 16 & 23 & 30 & 37 & 44 & 51 & 58 & 65 \\ 4 & 4 & 14 & 28 & 43 & 58 & 73 & 88 & 103 & 118 & 133 \\ 5 & 5 & 20 & 45 & 75 & 106 & 137 & 168 & 199 & 230 & 261 \\ 6 & 6 & 27 & 68 & 124 & 186 & 249 & 312 & 375 & 438 & 501 \\ 7 & 7 & 35 & 98 & 196 & 315 & 441 & 568 & 695 & 822 & 949 \\ 8 & 8 & 44 & 136 & 298 & 516 & 762 & 1016 & 1271 & 1526 & 1781 \\ 9 & 9 & 54 & 183 & 438 & 819 & 1284 & 1785 & 2295 & 2806 & 3317 \\ 10 & 10 & 65 & 240 & 625 & 1262 & 2109 & 3076 & 4088 & 5110 & 6133 \\ 11 & 11 & 77 & 308 & 869 & 1892 & 3377 & 5192 & 7172\\ \end{array} $$

Parece que los valores de ronno son buenos. Tenga en cuenta que parece que para $n\ge k$, $f(n+1,k)=f(n,k)+2^k-1$

Y $f(n,n)$ parece ser A058877 = $n(2^{(n-1)}-1)$

---

Aquí está el programa que hice (python 3.3). ¡Podría mejorarse! Debido a que utilicé llamadas recursivas para escribirlo rápidamente, pero no es tan eficiente en python.

import functools
import sys

@functools.lru_cache(maxsize=None)
def val(t) :
    res=[]
    pi= -1 
    for i in range(len(t)) :
        if t[i]>0 and t[i] != pi :
            pj= -1
            for j in range(len(t)) :
                if j != i and t[j] != pj :
                    newt=list(t)
                    newt[i]-=1
                    newt[j]=newt[i]
                    newt.sort()
                    res.append(val(tuple(newt)))
                    pj=t[j]
        pi=t[i]
    return(0 if res==[] else 1+max(res)) 

def vval(k,n) :
    return(val((k,)*n))

def main(m) :
    sys.setrecursionlimit(100000)
    for k in range(1,m) :
        print(k,end=" ")
        for n in range(2,m) :
            print("&",vval(k,n), end=" ")
            sys.stdout.flush()
        print("\\\\")

main(12)