Problema: Supongamos que usted comience con un montón de $n$ piedras y la división este de la pila en $n$ pilas de una piedra cada uno sucesivamente por la división de un montón de piedras en dos pedazos más pequeños. Cada vez que se divide una pila, multiplique el número de piedras en cada uno de los dos más pequeños montones de formar, de manera que si estas pilas tienen $r$ $s$ piedras en ellas, respectivamente, calcular $rs$. Una vez que haya terminado la división de los pilotes, calcular la suma de los productos calculados en cada paso. ¿El orden de cómo dividir las pilas efecto de la presentación final?
Simple fuerte inducción de la prueba: parece como si la suma siempre será $n(n-1)/2$. Brevemente, la pila de $n$ piedras se divide en montones de $r$ $s=n-r$ piedras, donde $r$ es un entero positivo menor que $n$. La clave inductivo paso por la fuerte inducción de la prueba es $$ rs+\frac{r(r-1)}{2}+\frac{s(s-1)}{2}=\frac{(r+s)(r+s-1)}{2}=\frac{n(n-1)}{2}. $$
Mi pregunta: ¿hay alguna limpio maneras de interpretar este problema y su solución?
Este problema aparece en varias fuentes de donde el resultado es a menudo incluido y se le pide que demuestre que el uso de la inducción. Me di cuenta de que hay un número de maneras de ver este problema y su concomitante análogos (pero me falta una buena, intuitiva interpretación geométrica o de análisis):
Combinatoria: en Lugar de sumar los productos para todas las de la pila escisiones de $n$ piedras, la etiqueta de las piedras $1$ a través de $n$ y sean elementos de un conjunto $M$. Para todos los de split, a la par de todas las piedras en el primer set, con todas las piedras en el segundo set. Cada par se produce de esta forma aparece exactamente una vez durante la actividad. Los términos de la suma son el número de nuevos pares generados después de cada división. Considerar el poder establecer $\mathcal{P}(M)$. Al hacer tales emparejamientos, se han generado distintos de 2 elementos de los subconjuntos de a $\mathcal{P}(M)$.
La teoría de grafos: en Lugar de sumar los productos para todas las de la pila escisiones de $n$ piedras, esparcir las piedras sobre una superficie plana. Matemáticamente hablando, vamos a $P_1,P_2,\ldots,P_n$ $n$ puntos en un plano donde no hay tres puntos son colineales. Cada punto representa una piedra o vértice. Con este entendimiento, la situación puede ser modelada por un simple gráfico de $G=(V,E)$. Si vamos a conectar cada par de vértices con una ventaja para un gráfico de $G$, es decir, construir el grafo completo $G=K_n$, entonces el número de aristas de $K_n$ sería igual a la suma de los productos de la actividad original.
Combinatoria y teoría de grafos: Le podemos dar una especie de actualización de la clave de paso inductivo que se utilizó para probar el resultado de la actividad considerando un ejercicio que aparece en D. B. West, Introducción a la Teoría de grafos:
$\underline{\text{Exercise:}}$ Uso completo de gráficos y contando argumentos para demostrar que $$ \binom{n}{2} = \binom{k}{2} + k(n-k) +\binom{n-k}{2}\quad|\quad 0\leq k\leq n. $$ Prueba. Considere el grafo completo $K_n$ ha $\binom{n}{2}$ bordes. Si nos partición de los vértices de $K_n$ a un conjunto con $k$ elementos y un conjunto de con $n-k$ elementos, entonces podemos contar los bordes como aquellos dentro de un bloque de la partición y de aquellos que la elección de un vértice de cada uno. En consecuencia, el número de aristas es dado por $k(n-k)+\binom{k}{2}+\binom{n-k}{2}$.
Creo que son muy interesantes formas de mirar el problema original/actividad. Una interpretación geométrica (o de otros) que añade intuición en cuanto a por qué el resultado de la actividad es verdadero, sería bastante agradable.
