Un problema interesante con la "descomposición" de números naturales.

Question

Considera el siguiente juego de una sola persona:

Un jugador comienza con una puntuación de $0$ y escribe el número $20$ en un pizarrón blanco vacío. En cada paso, puede borrar un entero (llamémoslo $a$) y escribir dos enteros positivos (llamémoslos $b$ y $c$) tal que $b + c = a$. Luego, el jugador suma $b × c$ a su puntuación. Repite el paso varias veces hasta que termina con todos los $1$ en el pizarrón. Entonces el juego termina, y se calcula la puntuación final.

Ejemplo: En el primer paso, un jugador borra $20$ y escribe $14$ y $6$, y obtiene una puntuación de $14 × 6 = 84$. En el siguiente paso, borra $14$, escribe $9$ y $5$, y suma $9 × 5 = 45$ a su puntuación. Su puntuación ahora es $84 + 45 = 129$. En el siguiente paso, puede borrar cualquiera de los números restantes en el pizarrón: $5$, $6$ o $9$. Continúa hasta que el juego termine.

Alya y Bob juegan el juego por separado. Alya logra obtener la puntuación final más alta posible. Bob, sin embargo, logra obtener la puntuación final más baja posible. ¿Cuál es la diferencia entre las puntuaciones finales de Alya y Bob?

Intenté "descomponer" en algunos números y obtengo los mismos puntajes. No estoy seguro de cómo probar la conjetura de que cualquier número dará el mismo resultado sin importar qué camino se tome.

Answer 1

Aquí tienes una prueba visual, para complementar el álgebra de otras respuestas:

Cuando comiences el juego (desde 20), dibuja una forma de "escalera" como en la figura, pero con 19 cuadrados en la base (así también 19 cuadrados de altura). A medida que juegas, para cada número en el tablero siempre tendrás una escalera correspondiente, con base y altura 1 menos que ese número. Cada turno, al dividir un número como $n = b+c$, divide su escalera como se muestra en la imagen; eso te da un rectángulo de $b \times c$, más dos escaleras más pequeñas para los números resultantes $b$ y $c$. El área de los rectángulos es tu puntuación hasta el momento. Cuando todos los números que quedan sean 1, entonces has convertido toda la escalera original en rectángulos, por lo que tu puntuación final es el área total de la escalera original.

Esta área, el número de cuadrados en la escalera de base $n-1$, está dada por la fórmula $\frac{n(n-1)}{2}$, como se señala en otras respuestas. Esta es una fórmula famosa, y si no la has visto antes, se puede explicar por el hecho de que dos escaleras de este tipo encajan juntas en un rectángulo de $n \times (n-1)$.

Answer 2

Supongamos que tu hipótesis es que comenzando con $n$ terminas con una puntuación de $\frac12 n(n-1)$. Es claramente cierto comenzando con $n=1$ ya que no hay movimientos y por lo tanto una puntuación de $0$.

Ahora supongamos que sabes que esto es cierto para $1 \le n \le k$ para algún $k$, entonces comienza con $k+1$ y divídelo en $a$ y $k+1-a$ donde ambos están entre $1$ y $k$. Obtienes una puntuación inmediata de $a(k+1-a)$ más (por la hipótesis) puntuaciones posteriores de $\frac12 a(a-1)$ y $\frac12 (k+1-a)(k+1-a-1)$. Súmalos y simplifica a $\frac12 (k+1)k$. Por lo tanto es cierto para $n=k+1$.

Usando inducción fuerte, puedes concluir que la hipótesis es cierta para todos los números enteros positivos $n$.

Answer 3

Supongamos que representamos un número $n$ en el pizarrón mediante $n$ objetos distintos. Cuando dividimos $a$ en $b+c$, colocamos $b$ de los objetos en un grupo, y $c$ de los objetos en el otro grupo.

Luego podemos representar los $b\cdot c$ puntos que obtenemos por la división de la siguiente manera: por cada par de objetos que solían estar en el mismo grupo, pero ahora están en grupos diferentes, obtenemos un punto.

Al principio, todos los $20$ objetos están en el mismo grupo. Al final, todos los $20$ objetos están en grupos diferentes, así que debemos haber obtenido $\binom{20}{2}$ puntos por separarlos.

Answer 4

Transformo mi comentario en una respuesta. Tu conjetura es correcta, y puede ser deducida con una prueba por inducción.

Afirmación: Para $n>1$ el juego siempre termina con la puntuación $n(n-1)/2$.

Prueba: Claro para $n=2$. Así que asumimos para números menores que $n$ y comenzamos el juego en $n$ con $n=a+b$ y una puntuación de $ab$. Luego continuas con juegos separados en $a$ y $b$, que terminan ellos mismos con una puntuación de $a(a-1)/2$ y $b(b-1)/2$. Así que tu puntuación final es $ab+a(a-1)/2+b(b-1)/2=n(n-1)/2$.

Answer 5

Comparado con la respuesta de Misha Larov, mi solución tiene esencialmente la misma idea pero una interpretación diferente.

Digamos que el número con el que empezamos es $n$. En cualquier etapa del juego, asignamos un grafo completo $K_i$ a cualquier número $i$ escrito en el tablero.

La acción de dividir un número $a$ en $b$ y $c$ puede ser reinterpretada como

1. Elegir subconjuntos de vértices disjuntos $B$ y $C$ de $K_a$ con $b$ y $c$ elementos respectivamente
2. Eliminar cada arista conectando $i \in B$ y $j \in C$
3. Obtener nuevos grafos completos $K_b$ y $K_c$.

La puntuación que el jugador obtiene después de esta división es el número de aristas eliminadas en el paso 2. A lo largo del juego, contamos en realidad el total de aristas eliminadas.

En la condición final, donde todos los grafos son $K_1$, que son vértices individuales, hemos eliminado todas las aristas del grafo inicial $K_n$. Por lo tanto, la puntuación final es siempre el número de aristas en $K_n$, $\frac{n(n-1)}{2}$.