Demostrar que la suma de los números escritos en la pizarra siempre es igual a $\binom{20}{2}$

Question

Escribimos el número $20$ como la suma de dos números $a,b$ y escribimos $ab$ en el tablero donde $a,b \ge 1$. Hacemos esto de nuevo para $a,b$ hasta que obtengamos solo (múltiples instancias) del número $1$. Demuestra que la suma de los números escritos en el tablero siempre es igual a $\binom{20}{2}$.

No sé cómo debería trabajar para obtener una combinación; ¿es más probable obtener una suma?

Answer 1

Para ampliar la pista que dejé en los comentarios:

Considera un grafo completo con $20$ vértices. Sabemos que el grafo tiene ${20 \choose 2}$ aristas; contaremos las aristas de una manera diferente. Separa el grafo en dos subgrafos disjuntos $A$ y $B$ de orden $a$ y $b$ (por lo tanto, $a+b=20$). Hay $ab$ aristas en total entre $A$ y $B$. Ahora continúa el proceso en $A$ y $B$. Al final, habremos contado cada arista una vez, por lo que la suma de los productos $ab$ debe ser ${20 \choose 2}$.

Answer 2

Generaliza y demuestra por inducción. Para cualquier nodo etiquetado $n$, la suma de los productos sobre su subárbol debe ser $\binom{n}{2}$. Esto es cierto para los nodos hoja (siendo la suma vacía y $\binom{1}{2}=0$), y asumiendo que para los hijos etiquetados $a,b$, la suma total se convierte en $\binom{a}{2}+\binom{b}{2}+ab$. No es difícil mostrar que esto es $\binom{a+b}{2}$. De hecho, el conjunto de pares que se pueden formar a partir de $a$ bolas blancas y $b$ bolas negras contiene $\binom{a}{2}$ pares blancos, $\binom{b}{2}$ pares negros, y $ab$ pares de colores mixtos. O adjunta triángulos de $\binom{a}{2}$ y $\binom{b}{2}$ puntos respectivamente a dos lados de un array rectangular de puntos $a \times b$, para obtener un array triangular con $a+b$ puntos a lo largo de cualquier lado; esto para aquellos más orientados visualmente.

Answer 3

Este proceso puede describirse de la siguiente manera:

$F(n) = a \cdot (n-a) + F(a) + F(n-a)$ donde $F(0) = F(1) = 0$.

(En otras palabras, dado un valor $n$, estamos eligiendo un valor para $a$ y dejando que $b=n-a$, de manera que $a+b=n$)

Intentemos con $a=1$:

$F(n) = 1 \cdot (n - 1) + F(1) + F(n-1) = n - 1 + F(n-1) = \sum_{k=1}^{n} (k-1) = \frac{n(n-1)}{2}$

Esto al menos nos brinda una forma sencilla de calcular $F(n)$ asumiendo que siempre elegimos $a=1$.

Intentemos de nuevo utilizando inducción, con la hipótesis de que $F(n) = \frac{n(n-1)}{2}$ es verdadero independientemente de $a$ al sustituir:

$F(n) = a \cdot (n-a) + \frac{a(a-1)}{2} + \frac{(n-a)(n-a-1)}{2} = \frac{n(n-1)}{2}$

Todos los términos $a$ se cancelan, por lo que $F(n)$ no depende de $a$. Siempre será igual a $\frac{n(n-1)}{2} = \binom{n}{2}$

Answer 4

Este es en realidad un problema bastante encantador.

Intuitivamente, el problema inicialmente parece bastante complicado, o, al menos, lo parecía para mí.

Comenzando con el número natural $n$ lo dividimos en otros dos $a+b$, luego tomamos el producto $ab$ e iteramos este proceso de dividir $a$ y $b$ multiplicando, etc. Eventualmente sumando todos los pares de productos.

Para ganar intuición sobre este proceso me di cuenta de que necesitamos alguna manera de tratar tanto con $a+b$ como con $ab$ juntos. La forma más sencilla de hacer esto es elevar al cuadrado $n$:

$$n^2=(a+b)^2=a^2+2ab+b^2$$

Tenemos la suma $a+b$ a la izquierda (aunque al cuadrado) y el producto $ab$ a la derecha. Luego, al iterar este proceso: Cada uno de $a$ y $b$ pueden escribirse como sumas de números naturales ellos mismos, digamos $a=c+d$ y $b=e+f$, luego expandiendo

$$n^2=c^2+d^2 + e^2 + f^2 + 2(cd+ab+ef)$$

y así sucesivamente hasta que llegamos a

$$n^2=\underbrace{1^2+1^2+\cdots +1^2}_{\text{$n$ veces}} + 2S$$

donde $S$ es la suma deseada de todos los productos.

Debería ser claro que siempre habrá $n$ términos de $1^2$:

Para imaginar esto, considera $n^2$ como el área de un cuadrado de lado $n$. En cada iteración dividimos a lo largo de la horizontal y la vertical de cuadrados más pequeños que están a lo largo de la diagonal. Eventualmente nos quedamos con los $n$ cuadrados diagonales principales $1\times 1$, cada uno de área $1^2$.

Entonces

$$n^2=n+2S$$

por lo tanto

$$S=\frac{n(n-1)}{2}=\binom{n}{2}$$