¿Cuántos triángulos?

Question

Vi esta pregunta hoy, pregunta cuántos triángulos hay en esta imagen.

No sé cómo resolver esto (sin contar directamente), aunque supongo que tiene algo que ver con alguna recurrencia.

¿Cómo se puede contar el número de todos los triángulos en la imagen?

Answer 1

Digamos que en lugar de cuatro triángulos a lo largo de cada borde tenemos $n$. Primero contemos los triángulos que apuntan hacia arriba. Esto es fácil de hacer si los cuentas por vértice superior. Cada vértice en la imagen es la parte superior de un triángulo para cada línea de cuadrícula horizontal debajo de él. Así, el vértice más alto, que tiene $n$ líneas de cuadrícula horizontales debajo de él, es el vértice superior de $n$ triángulos; cada uno de los dos vértices en la siguiente fila hacia abajo es el vértice superior de $n-1$ triángulos; y así sucesivamente. Esto nos da un total de

$$\begin{align*} \sum_{k=1}^nk(n+1-k)&=\frac12n(n+1)^2-\sum_{k=1}^nk^2\\ &=\frac12n(n+1)^2-\frac16n(n+1)(2n+1)\\ &=\frac16n(n+1)\Big(3(n+1)-(2n+1)\Big)\\ &=\frac16n(n+1)(n+2)\\ &=\binom{n+2}3 \end{align*}$$

triángulos que apuntan hacia arriba.

Los triángulos que apuntan hacia abajo se pueden contar por sus vértices inferiores, pero es un poco más complicado. Primero, cada vértice que no está en el borde izquierdo o derecho de la figura es el vértice inferior de un triángulo de altura $1$, y hay $$\sum_{k=1}^{n-1}=\binom{n}2$$ de ellos. Cada vértice que no está en el borde izquierdo o derecho o en las líneas de cuadrícula inclinadas adyacentes a esos bordes es el vértice inferior de un triángulo de altura $2$, y hay

$$\sum_{k=1}^{n-3}k=\binom{n-2}2$$ de ellos. En general, cada vértice que no está en el borde izquierdo o derecho o en una de las $h-1$ líneas de cuadrícula inclinadas más cercanas a cada uno de esos bordes es el vértice inferior de un triángulo de altura $h$, y hay

$$\sum_{k=1}^{n+1-2h}k=\binom{n+2-2h}2$$ de ellos.

Álgebra corregida a partir de este punto.

Por lo tanto, el número total de triángulos que apuntan hacia abajo es

$$\begin{align*} \sum_{h\ge 1}\binom{n+2-2h}2&=\sum_{k=0}^{\lfloor n/2\rfloor-1}\binom{n-2k}2\\ &=\frac12\sum_{k=0}^{\lfloor n/2\rfloor-1}(n-2k)(n-2k-1)\\ &=\frac12\sum_{k=0}^{\lfloor n/2\rfloor-1}\left(n^2-4kn+4k^2-n+2k\right)\\ &=\left\lfloor\frac{n}2\right\rfloor\binom{n}2+2\sum_{k=0}^{\lfloor n/2\rfloor-1}k^2-(2n-1)\sum_{k=0}^{\lfloor n/2\rfloor-1}k\\ &=\left\lfloor\frac{n}2\right\rfloor\binom{n}2+\frac13\left\lfloor\frac{n}2\right\rfloor\left(\left\lfloor\frac{n}2\right\rfloor-1\right)\left(2\left\lfloor\frac{n}2\right\rfloor-1\right)\\ &\qquad\qquad-\frac12(2n-1)\left\lfloor\frac{n}2\right\rfloor\left(\left\lfloor\frac{n}2\right\rfloor-1\right)\;. \end{align*}$$

Establezcamos $\displaystyle m=\left\lfloor\frac{n}2\right\rfloor$, y esto se convierte en

$$\begin{align*} &m\binom{n}2+\frac13m(m-1)(2m-1)-\frac12(2n-1)m(m-1)\\ &\qquad\qquad=m\binom{n}2+m(m-1)\left(\frac{2m-1}3-n+\frac12\right)\;. \end{align*}$$

Esto se simplifica a $$\frac1{24}n(n+2)(2n-1)$$ para $n$ par y a

$$\frac1{24}\left(n^2-1\right)(2n+3)$$ para $n$ impar.

La figura final, entonces es

$$\binom{n+2}3+\begin{cases} \frac1{24}n(n+2)(2n-1),&\text{si }n\text{ es par}\\\\ \frac1{24}\left(n^2-1\right)(2n+3),&\text{si }n\text{ es impar}\;. \end{cases}$$

Answer 2

Tabulando números

Sea $u(n,k)$ el número de triángulos apuntando hacia arriba de tamaño $k$ incluidos en un triángulo de tamaño $n$, donde tamaño es un término abreviado para longitud de lado. Sea $d(n,k)$ el número de triángulos hacia abajo. Puedes tabular algunos números para tener una idea de esto. En la siguiente tabla, la fila $n$ y la columna $k$ contendrán dos números separados por una coma, $u(n,k), d(n,k)$.

$$ \begin{array}{c|cccccc|c} n \backslash k & 1 & 2 & 3 & 4 & 5 & 6 & \Sigma \\\hline 1 &  1, 0 &&&&&&  1 \\ 2 &  3, 1 &  1,0 &&&&&  5 \\ 3 &  6, 3 &  3,0 &  1,0 &&&& 13 \\ 4 & 10, 6 &  6,1 &  3,0 & 1,0 &&& 27 \\ 5 & 15,10 & 10,3 &  6,0 & 3,0 & 1,0 && 48 \\ 6 & 21,15 & 15,6 & 10,1 & 6,0 & 3,0 & 1,0 & 78 \end{array} $$

Encontrando un patrón

Ahora busca patrones:

• $u(n, 1) = u(n - 1, 1) + n$ ya que el cambio de tamaño agrega $n$ triángulos hacia arriba
• $d(n, 1) = u(n - 1, 1)$ ya que los triángulos hacia abajo se basan en la cuadrícula de triángulos de un tamaño menor
• $u(n, n) = 1$ ya que siempre hay exactamente un triángulo de tamaño maximal
• $d(2k, k) = 1$ ya que necesitas al menos el doble de la longitud de su lado para contener un triángulo hacia abajo.
• $u(n, k) = u(n - 1, k - 1)$ al usar el triángulo de tamaño $(k - 1)$ en la parte superior como representante del triángulo de tamaño $k$, excluyendo la fila más baja (es decir, la fila $n$).
• $d(n, k) = u(n - k, k)$ ya que la cuadrícula continúa expandiéndose, agregando una fila a la vez.

Usando estas reglas, puedes extender la tabla anterior arbitrariamente.

El dato importante a tener en cuenta es que obtienes la misma secuencia de $1,3,6,10,15,21,\ldots$ una y otra vez, en cada columna. Describe cuadrículas de triángulos del mismo tamaño y orientación, aumentando el tamaño de la cuadrícula en uno en cada paso. Por esta razón, esos números también se llaman números triangulares. Una vez que sepas dónde aparece el primer triángulo en una columna dada, el número de triángulos en filas subsecuentes es fácil.

Buscando la secuencia

Ahora lleva esa columna de sumas a OEIS, y encontrarás que se trata de la secuencia A002717 que viene con una fórmula agradable:

$$\left\lfloor\frac{n(n+2)(2n+1)}8\right\rfloor$$

También hay un comentario que indica que esta secuencia describe el

Número de triángulos en un arreglo triangular de fósforos de lado $n$.

Lo cual suena justo a lo que estás preguntando.

Referencias

Si quieres saber cómo obtener esa fórmula sin buscarla, o cómo verificar esa fórmula sin simplemente confiar en una enciclopedia, entonces algunas de las referencias proporcionadas en OEIS probablemente te ayudarán:

• J. H. Conway y R. K. Guy, El Libro de los Números, p. 83.
• F. Gerrish, Cuántos triángulos hay, Math. Gaz., 54 (1970), 241-246.
• J. Halsall, Una serie interesante, Math. Gaz., 46 (1962), 55-56.
• M. E. Larsen, El triángulo eterno: una historia de un problema de conteo, College Math. J., 20 (1989), 370-392.
• C. L. Hamberg y T. M. Green, Una aplicación de números triangulares, Mathematics Teacher, 60 (1967), 339-342. (Referenciado por Larsen)
• B. D. Mastrantone, Comentario, Math. Gaz., 55 (1971), 438-440.
• Problema 889, Math. Mag., 47 (1974), 289-292.
• L. Smiley, Una solución rápida de conteo de triángulos, Mathematics Magazine, 66, #1, Feb '93, p. 40.

Answer 3

Editar: Intenté escribir esto como una generalización del caso más simple de contar los triángulos pequeños, pero claramente no anticipé los problemas que surgirían. Mi solución propuesta no funciona, ya que cuenta líneas rectas además de triángulos. Se puede corregir de varias formas diferentes, pero esto simplemente complica un método que ya es ineficiente.

---

Etiqueta cada esquina de cada triángulo y considéralas nodos en un grafo. Luego puedes escribir la matriz de adyacencia para ese grafo. Debido a que el grafo tiene una estructura tan regular, la matriz se puede calcular bastante fácilmente y se escala de manera eficiente. IMPORTANTE: dos nodos son "adyacentes" si están conectados por una línea recta, no solo un segmento de línea.

Las matrices de adyacencia tienen la propiedad interesante de que si tomas su producto, te dice cuántas formas hay de ir de un punto a otro. Si tomas el cubo de la matriz, las entradas diagonales te dirán cuántas formas hay de volver a un punto en tres movimientos (es decir, formar un triángulo).

A partir de ahí, solo necesitas calcular la traza de esta matriz y dividir el resultado entre seis (ya que cada triángulo se cuenta seis veces; dos veces por cada esquina).

editar: dividir entre seis, no tres.

Answer 4

Sea $T_n$ el número de triángulos cuando la longitud del lado del triángulo grande es $n\geq0$. Entonces $T_0=0$, $T_1=1$. Para obtener una fórmula de recurrencia para los $T_n$ tenemos que distinguir entre $n$ par e impar.

Supongamos que $n=2m$, y agreguemos una fila de triángulos $2m+1$ en la parte inferior. Entonces cada triángulo "viejo" aparecerá en $T_{2m+1}$, además, cada punto de la cuadrícula "viejo" es un vértice de un triángulo con la base en la parte inferior de la nueva figura, y finalmente, los nuevos puntos de la cuadrícula inferior $z$ sirven como vértices de nuevos triángulos de abajo hacia arriba cuyos tamaños están entre $1$ y la distancia de $z$ desde las esquinas inferiores de la figura. Se sigue que

$$T_{2m+1}=T_{2m}+\sum_{k=0}^{2m} (k+1)+2\sum_{k=1}^m k\ ,\qquad(*)$$

y de manera similar obtenemos

$$T_{2m+2}=T_{2m+1}+\sum_{k=0}^{2m+1} (k+1)+2\sum_{k=1}^m k + (m+1)\ .$$

Sustituyendo $T_{2m+1}$ de la primera fórmula en la segunda obtenemos

$$T_{2m+2}=T_{2m}+2\sum_{k=0}^{2m} (k+1) +(2m+2)+4\sum_{k=1}^m k +(m+1)=T_{2m}+6m^2+11m +5\ .$$

Esto implica que $$T_{2m}=(m-1)m(2m-1)+11{(m-1)m\over2}+5m={1\over2}(4m^3+5m^2 +m)\ ,$$ y usando $(*)$ obtenemos $$T_{2m+1}={1\over2}(4m^3+11m^2+9m+2)\ .$$ (Esto coincide con los resultados de Brian M. Scott.)

Answer 5

Hay un montón de respuestas complicadas para un problema simple. Está bien, pero solo estamos tratando de resolver este problema simple aquí, no su generalización completa. Solo ve por tamaño.

Triángulos de tamaño 1 (como en 1 pequeño triángulo): 16 Triángulos de tamaño 16: 1 (el triángulo grande) Triángulos de tamaño 9: 3, esto es bastante claro

Esto deja solo los triángulos de tamaño 4, que probablemente sea la única parte difícil del problema. Supongo que cada triángulo va a tener un punto en la parte superior y estar plano en la parte inferior, o estar plano en la parte superior y tener un punto en la parte inferior. Una vez que reconoces esto, tampoco hay nada complicado en esta parte. Hay 6 con el punto arriba y 1 con el punto abajo. Así que el total es

$$16 + 1 + 3 + 6 + 1 = 27$$