En este post, veremos la solución general del acertijo de los triángulos que hemos estado resolviendo esta semana. En el primer post, los lados del triángulo grande habían sido partidos en dos trozos y la solución era 8. En el segundo post, los lados habían sido partidos en tres trozos y la solución era 27. En el tercer post, te propuse que encontraras la solución para el caso general, cuando los lados se han partido en n trozos. ¿Cuántos triángulos aparecen entonces?
Sin anestesia: la solución es n3. Se puede demostrar mediante inducción. El caso base es trivial, lo tenemos ya resuelto con el primer acertijo de este tipo que hemos visto esta semana. Ejemplificaré el caso de inducción con el cambio desde n = 2 a n = 3.
Observa que el primer dibujo está contenido en la parte inferior del segundo, y lo mismo ocurre siempre cuando pasamos de n-1 a n.
Por lo tanto, todos los triángulos que ya habíamos contado en el caso anterior nos los podemos ahorrar. La solución será todos los que había antes más los que añadimos nuevos. Así que sólo nos interesa saber cuántos estamos añadiendo.
Algunos de esos triángulos contendrán un fragmento (o la totalidad) del lado izquierdo del triángulo mayor desde el vértice inferior. ¿Cuánta parte de ese lado? Tenemos tres opciones posibles: quedarnos en la primera partición, en la segunda o coger el lado entero. Para cada una de esas elecciones, también tenemos otras tres opciones en función de cuánto de grande queremos nuestro triángulo: si sólo cogemos el pequeño que está pegado al lado izquierdo, si tomamos un poco del triángulo central (el que era el caso n = 2), o si vamos hasta abajo y cogemos también la base del triángulo mayor (éste último es el ejemplo de la siguiente imagen). Es decir, tenemos 3x3 elecciones posibles. En general, el argumento es el mismo, y el número de triángulos es n2.
Análogamente, hacemos lo mismo con el lado derecho y tenemos otros n2 triángulos. Pero, cuidado, hay uno que aparece en los dos casos: el propio triángulo mayor, así que tendremos que restar 1 a nuestro resultado. En resumen, lo que hemos hallado hasta ahora es que Tn = Tn-1 + 2n2 - 1 + (los triángulos que no nacen de las particiones inferiores de los lados mayores). En nuestro ejemplo, es muy fácil ver los triángulos que nos quedan. Son dos y uno de ellos es (el otro es el simétrico):
En general, son triángulos que no contienen ni los segmentos iniciales ni finales de los lados derecho e izquierdo (si lo hacen, ya los hemos contado antes). Así, tienen parte de uno de los lados (asumamos el derecho, como en la imagen) y van hasta el vértice opuesto. Hay n-2 segmentos posibles del lado con los que podemos jugar. Quizás, el triángulo sólo contiene UNO de estos segmentos: hay n-2 posibilidades. Quizás, contiene DOS segmentos adyacentes: hay n-3 posibilidades. Quizás, contiene TRES,... Es fácil ver que el total de estos triángulos es la suma de todos los números desde 1 hasta n-2, que es 1⁄2(n-1)(n-2). Para el lado izquierdo, el resultado es análogo, así que multiplicamos este resultado por 2: (n-1)(n-2).
Retomemos la igualdad de antes, ya reformulada: Tn = Tn-1 + 2n2 - 1 + (n-1)(n-2). Por la hipótesis de inducción, Tn-1 = (n-1)3 y tenemos que Tn = (n-1)3 + 2n2 - 1 + (n-1)(n-2) = n3 - 3n2 + 3n - 1 + 3n2 - 3n + 1 = n3, probando así nuestra resultado.
No hay parte 5 para triángulos en los que las particiones no son simétricas?
ResponderEliminarMe refiero a que de la esquina izquierda salgan n 'secciones' (n-1 divisiones) y de la derecha lo hagan m, con m no necesariamente igual a n. (en este post la partición es con n=m, simétrica)
La ecuación es también muy sencilla y sorprendentemente simple (y obviamente cuando n=m se reduce a n^3).
Por cierto, la forma en la que lo he sacado no es mediante inducción, sino mediante una forma de contar que muestra un patrón oculto (y fácil de calcular). Consiste en marcar cada región (cada polígono en el que la figura final queda dividido, en el caso 3x3 hay 9 regiones) con un número igual al número de triángulos que se pueden formar con esa región como parte superior.
Es decir, la región central inferior siempre es 1 (sólo hay un triángulo, él mismo), la región de abajo más a la izquierda es n, y la región de mas arriba (la cúspide) es 2n-1. En el caso nxm cambia un poco, pero el patron se sigue viendo igual de claro.
¡Qué interesante, Abel! Muchas gracias por tu comentario. No se me había ocurrido tu método, es muy ingenioso. Y el caso asimétrico... lo dejo como ejercicio para el lector jajajaja
EliminarPara el caso asimétrico: nm(n+m)/2
EliminarYo he contado triángulos:
- Con los dos vértices inferiores del triángulo original (es decir, la base horizontal): Hay n opciones que salen del vértice izquierdo, m opciones del vértice derecho. Así, hay m*n triángulos.
- Con solamente el vértice inferior izquierdo del triángulo original (es decir, no hay base horizontal): Hay que elegir dos lados que salen de ese vértice entre n posibles (n sobre 2) y el tercer lado debe venir de una de las líneas que sale del vértice inferior derecho (sin contar la horizontal), así que hay m posibilidades. En total, (n sobre 2)*m.
- Con solamente el vértice inferior derecho del triángulo original. Caso análogo anterior intercambiando n y m: (m sobre 2)*n.
Así, en total hay m*n + (n sobre 2)*m + (m sobre 2)*n triángulos. Simplificando un poquito, da mn(m+n)/2.
Bonito problema!