Hay ocho puntos de conexión entre uno y otro. Consulte la figura [1]
Además de que el punto rojo, de tres segmentos de línea que no se intersectan en un punto.
- Cuántos triángulos hay en la imagen?
- Si usted retire los tres segmentos, el máximo número de triángulos de la izquierda?
Muchas gracias!
Resumen
Para la primera parte de la pregunta, la respuesta es $$\binom{8}{3} + 4\binom{8}{4} + 5\binom{8}{5} + \binom{8}{6} = 644$$ El número señalado por bof en uno de hir comentarios.
Para la segunda parte, si interpretamos el término "segmento" como una de las $\binom{8}{2} = 28$ bordes entre el $8$ vértices, la respuesta va a ser $583$. Esto se logra mediante la eliminación de 3 consecutivos bordes del perímetro del círculo. Por ejemplo, la eliminación de los bordes $12$, $23$ y $34$ nos dejó con $583$ triángulos.
Parte I - el número de triángulos.
Nos deja cambiar a la forma de obtener la respuesta para la primera parte de la pregunta analíticamente.
En lugar de $8$, considere la posibilidad de la generalización de la colocación de $n$ puntos rojos en un círculo, forma un grafo completo de ellos y luego contar el número de triángulos formados por estas líneas. Asumimos, además, que los puntos rojos son, en general, de posición, de manera que no hay tres líneas que se cortan en el mismo punto (excepto en los puntos rojos). Como podemos ver a continuación, esta suposición es crucial.
WOLOG, vamos a la etiqueta de la $n$ puntos rojos por $1, \ldots, n$ y se colocan en el círculo en sentido antihorario manera.
Un triángulo tiene 3 lados y cada lado está acostada en una línea formada por dos puntos rojos. Ya que es posible que algunas líneas de intercambio de puntos rojos, un triángulo puede implicar $m$ puntos rojos donde $3 \le m \le 6$.
$\hspace0.5in$ 
Caso 1. $m = 3$
Hay $\binom{n}{3}$ formas para recoger $3$ puntos rojos $\{ a, b, c \}$ $n$ puntos rojos. WOLOG, podemos suponer $1 \le a < b < c \le n $. Dado $a, b, c$, es claro que cada punto rojo es compartida por $2$ líneas y sólo hay una manera para formar un triángulo con las tres líneas de $\{ ab, bc, ac \}$ (fig $1a$).
Esto significa que hay una zona de $\binom{n}{3}$ triángulos $m = 3$.
Caso 2. $m = 4$,
Hay $\binom{n}{4}$ formas para recoger $4$ puntos rojos $\{ a, b, c, d \}$ $n$ puntos rojos. WOLOG, podemos suponer $1 \le a < b < c < d \le n$. Dado $a, b, c, d$, hay dos posibilidades, o bien uno de ellos se conecta a todas las tres líneas (fig $2a$), esto nos lleva a ninguna parte, o dos de los puntos rojos son compartidos por dos líneas. Considere el caso $a$ es uno de estos dos puntos rojos y vamos a enumerar las posibilidades:
$c$ es el otro punto rojo, hay dos posibles arreglos línea $\{ ac, cd, ab \}$ o $\{ ac, bc, ad \}$ (fig. $2b)$. Sin embargo ninguno de ellos forma un triángulo dentro del círculo.
$b$ es el otro punto rojo, hay dos posibles de la línea de arreglos de nuevo $\{ ab, bc, ad \}$ (fig $2c$) y $\{ ab, bd, ac \}$ (fig $2d$). Sólo la segunda configuración se forma un triángulo dentro del círculo.
$d$ es el otro punto rojo, esto es similar a la anterior sub caso con $d, a, b, c$ asuma el papel de las $a, b, c, d$. Entre los dos posibles arreglos ine sólo uno de ellos forma un triángulo dentro del círculo. Si usted bucle sobre otras posibilidades de los dos puntos rojos que comparten líneas. Nos encontramos hay un total $4$ configuración para cada elección de $(a, b, c, d)$.
Esto significa que hay $4 \binom{n}{4}$ triángulos para $m = 3$ de los casos.
Caso 3. $m = 5$
Hay $\binom{n}{5}$ formas para recoger $5$ puntos rojos $\{ a, b, c, d, e \}$ $n$ puntos rojos. WOLOG, podemos suponer $1 \le a < b < c < d < e\le n$. Dado $a, b, c, d, e $, es claro que cualquier sólo uno de los puntos rojos son compartidos por dos líneas. Considere el caso en $a$ es que distinguía a los puntos rojos. Existen seis posibles arreglos línea $$ \{ ab, ac, de \} (\text{fig } 3a),\quad \{ ab, ad, ce \} (\text{fig } 3b),\quad \{ ab, ae, cd \} (\text{fig } 3c),\\ \{ ac, ad, ser \} (\text{fig } 3d),\quad \{ ac, ae, bd \} (\text{fig } 3e),\quad \{ ad, ae, bc \} (\text{fig } 3f) $$ y sólo de ellos $\{ ac, ad, be \}$ forma un triángulo dentro del círculo.
Dado que hay 5 posibles maneras de escoger el distinguido puntos rojos, hay $5\binom{n}{5}$ formas de la $m = 5$ de los casos.
Caso 4. $m = 6$
Hay $\binom{n}{6}$ formas para recoger $6$ puntos rojos $\{ a, b, c, d, e, f \}$ $n$ puntos rojos. WOLOG, podemos suponer $1 \le a < b < c < d < e < f\le n$. Dado $a, b, c, d, e, f$, $15$ maneras de agrupar en parejas y en forma de $3$ líneas. Es fácil ver que cualquier disposición de líneas que contiene el vecino par $ab, bc, cd, de, ef, af$ no forma un triángulo dentro de un círculo (por ejemplo, fig $4a$). Esto elimina $11$ de ellos y nos quedamos con $4$ línea de arreglos. $$\{ ac, be, df \},\quad \{ ad, be, cf \},\quad \{ ad, bf, ce \},\quad \{ ae, bd, cf \}$$ Si usted dibujar $4$ arreglos en un pedazo de papel, se dará cuenta de la $1^{st}$, $3^{rd}$ y $4^{th}$ disposición todo se ve como en la fig $4b$. Asimismo, no producen ningún triángulo dentro del círculo. Esto nos deja con la $2^{nd}$ de acuerdo $\{ ad, be, cf \}$. Hay dos posibilidades. Las 3 líneas de formar un triángulo dentro del círculo (por ejemplo, fig $4c$) o que se cortan en un único punto. Desde que hemos asumido el último caso no va a suceder. Esto significa que para cada elección de $\{ a, b, c, d, e, f \}$, existe una y sólo una manera de unirse a ellos para obtener un triángulo.
Como consecuencia de esto, se $\binom{n}{6}$ formas de la $m = 6$ de los casos.
Combinar estos cuatro casos, podemos concluir que el número de triángulo para general $N$ está dado por
$$\binom{n}{3} + 4\binom{n}{4} + 5\binom{n}{5} + \binom{n}{6}$$
Parte II - el máximo número de triángulos que quedan después de una quita de 3 segmentos.
Esto se hace por la fuerza bruta. Puedo escribir un programa para localizar todos los $644$ triángulos y proceder a comprobar el efecto en la eliminación de cualquiera de las $28$ bordes. Deje $N_{ab}$ el número de triángulos que se destruye cuando se retire el borde de la $ab$, tenemos
$$\begin{array}{r:l} N_{ab} & ab\\ \hline 21 & 12, 23, 34, 45, 56, 67, 78, 18\\ 66 & 13, 24, 35, 46, 57, 68, 17, 28\\ 99 & 14, 25, 36, 47, 58, 16, 27, 38\\ 111 & 15, 26, 37, 48 \end{array}$$
Desde $3 \times 21 < \min(66,99,111)$, la configuración que maximizar el número de triángulos que quedan es formado mediante la eliminación de tres de los bordes del perímetro de la circunferencia (que yo.e los de la primera fila de la tabla anterior).
El uso de la simetría rotacional, podemos suponer $18$ es una de las tres aristas a ir. Sólo tenemos que ir a través de $\binom{7}{2} = 21$ pares de aristas desde las $\{ 12, 23, 34, 45, 56, 67, 78 \}$ a identificar las configuraciones óptimas.
No es una respuesta - sólo un límite superior.
Observe que cada triángulo de la figura contiene exactamente tres aristas en el grafo. Y $3$ bordes se pueden formar en la mayoría de los $1$ triángulo. Así que un límite superior para esta cantidad es:
$$e \choose 3$$
donde $e = {8 \choose 2}$.
Nuevo aviso de que no hay 3 líneas son paralelas. Por lo tanto, cualquier elección de 3 líneas se cruzan en algún lugar. El número de triángulos en la figura a continuación, es el número de conjuntos de tres líneas de cuyo 3 puntos de intersección que se encuentran dentro del octágono. Quizás este es un problema más fácil de resolver. Tal vez podamos apretar el obligado. Suponemos que el límite inferior es de al menos
$$\frac14 {e \choose 3}$$
porque no puede ser $0, 1, 2, 3$ puntos de intersección dentro del octágono, y siento que difícilmente puede ser más fuera que dentro. Obviamente, esto es sólo mi instinto de hablar.
no es una respuesta correcta, ver comentarios
Podemos elegir cualquier triángulo:
Seleccione uno de los bordes de la gráfica (es decir, entre 2 red de nodos).
Seleccione cualquiera de los dos puntos en que el borde, ya sea de la red de nodos o intersecciones.
Los dos puntos seleccionados de forma uno de los lados de un triángulo.
Cada triángulo puede ser identificado por 3 mini segmentos de línea por lo que podemos dividir por 3.
Hay 8 puntos y, por tanto, 8 aristas de cada uno de varios tipos.
8 de las aristas entre nodos consecutivos de forma que sólo tiene 2 puntos y dan lugar a 1 segmento.
8 de las aristas entre los nodos separados por 2 lados, estos tienen 7 puntos (2 extremos, además de los bordes entre el nodo intermedio y los 5 restantes) y por lo tanto 7×6=42 segmentos.
8 de las aristas entre los nodos separados por 3 lados, estos tienen 10 puntos (2 extremos, además de los bordes entre los 2 nodos intermedios y los 4 restantes) y por lo tanto 10×9=90 segmentos.
4 de las aristas entre los nodos separados por 4 lados, estos tienen 11 puntos (2 extremos, además de los bordes entre los 3 nodos en un lado y 3 en el otro) y por lo tanto 11×10=110 segmentos.
Total = 8 + 8×42 + 8×90 + 4×110 = 440+720+336+8 = 1504
esto no dividir por 3, así que debe haber algo mal, ver comentarios
Si hay una forma cerrada para la n-noded caso, no sé. Sospecho que hay al menos una diferencia entre los números pares y los impares.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
