Mayor número de lados y diagonales.

Question

Me han pedido para resolver el siguiente: Para que dado un número entero $n\ge3$, encontramos el mayor número positivo $k_n$ para que: para cada convexo $n-$polígono (con $n$ lados), podemos encontrar $k_n$ segmentos, cada segmento está en un lado o en una diagonal de esta $n-$polígono, tal que para cualesquiera dos segmentos, que siempre tiene un punto en común.

Por ejemplo: $n=3$: Triángulo $ABC$, se puede elegir el conjunto de $\{AB,BC,CA\}$ que es $k_3=3$.

$n=4$: Cuadrilátero $ABCD$ podemos optar $\{AB,BC,AC,BD\}$$k_4=4$.

No tengo idea para solucionar esto? Podría alguien ayudarme?

Answer 1

Creo $k_n = n$. Mi razonamiento es que podemos elegir los segmentos de forma sistemática con el fin de ver este resultado:

En primer lugar, vamos a elegir un punto de la $n$-gon $A_1A_2...A_n$. Sin pérdida de generalidad, podemos suponer que se trata de regular y elija $A_1$ mediante el uso de la simetría. A continuación, cada segmento que tiene un punto final $A_1$ se incluye a nuestra cuenta (porque $A_1$ será el vértice común) por lo que no se $(n-1)$ dichos segmentos. Ahora, para los lados $A_1A_2$$A_1A_n$, la diagonal $A_2A_n$ también se cruza con el resto de $(n-1)$ segmentos. Y este el máximo que se puede conseguir porque salvo que en diagonal, no podemos encontrar ninguna otra diagonal que tiene puntos en común con $A_1A_2$ $A_1A_n$ ambos. Por lo tanto, la respuesta es $k_n = n$.

Ahora, si no tenemos un regular $n$-gon, este argumento se sostiene porque $A_1A_2$ $A_1A_n$ son los dos lados del triángulo $A_1A_2A_n$ y todos los otros vértices $A_i$ ( $i \ne 1,2,n$ ) $n$- gon no se coloca de tal manera que $\angle A_1A_2A_i > 180^\circ$ o $\angle A_1A_nA_i > 180^\circ$ porque $n$-gon es convexa (observe También que incluso el ángulo de $180^\circ$, ya que en este caso $A_1A_2 \cap A_1A_i = A_1A_2$ no habría sido más que una mutua puntos). Por lo tanto para todos $A_i$, $A_1A_i$ cruza $A_nA_2$. Y el mismo razonamiento para $k_n=n$ a ser máxima es todavía válida.

Answer 2

ArsenBerk proporciona un algoritmo que muestra la elección de $n$ estos segmentos es posible, pero no que la elección de más es imposible. Aquí es una prueba de eso.

Supongamos que para algunos convexo $n$-gon, $n+1$ segmentos de haber sido elegido el cumplimiento de las condiciones. Vamos a obtener una contradicción.

Por el principio del palomar, existe un vértice que es el extremo de, al menos, dos segmentos. Etiqueta de ese vértice $A_0$, y todos los demás, en la dirección de las agujas del reloj, empezando y terminando con sus vecinos,$A_1, A_2, \dots, A_{n-1}$. Deje que el primero de ellos, que está conectado a $A_0$ (aquí y en lo sucesivo, "conectado" significa "conectados por un segmento elegido") $A_r$ y el último en ser$A_{n-s}$,$1\leq r < n-s \leq n-1$. El número máximo de segmentos con $A_0$ como extremo, a continuación,$(n-s)-(r-1) = n-s-r+1$.

Cualquier elegido segmentos no tener $A_0$ como un punto final debe ser de la forma $A_iA_j$$1\leq i < j \leq n-1$. Si $i > r$, $A_0A_r \cap A_iA_j = \emptyset$ (debido a que no son adyacentes a los lados del cuadrilátero convexo $A_0A_rA_iA_j$), por lo que debemos tener $i \leq r$. Del mismo modo, si $j < n-s$, $A_iA_j \cap A_{n-s}A_0 = \emptyset$, por lo tanto,$j \geq n-s$.

Deje que nos re-etiquetar los puntos de $A_j$, por lo que $j \geq n-s$ (hay $s$ de las personas) como $B_1, B_2, \dots, B_s$, manteniendo el mismo sentido de las agujas-es-orden ascendente: $A_{n-s}$ ahora $B_1$, y así sucesivamente. Una visualización útil podría ser la que nos están pintando estos puntos de color azul, y si también imagine $A_1, \dots, A_r$ rojo, luego hemos demostrado que todos los elegidos de los segmentos no se adjunta a $A_0$ debe conectarse a un punto rojo con un punto azul.

---

Lemmma: En el polígono convexo $A_1A_2\dots A_rB_1B_2\dots B_s$,$r,s \geq 1$, el número máximo de segmentos del tipo $A_iB_j$, de modo que cualquiera de los dos tienen un punto en común, es $r+s-1$.

Prueba: Por inducción. Si $r+s = 2$, no es sólo un segmento, de modo que es el máximo que puede ser elegido. Asumir la afirmación es verdadera para cada polígono con $r+s = t-1$ algunos $t > 2$. Podemos comprobarlo por $r+s = t$.

Si $r = 1$, entonces cada segmento elegido conecta a la misma red point con uno de $s = t-1$ azul puntos, lo que hace que en la mayoría de las $t-1$ segmentos. De manera similar para el caso de $s = 1$.

Ahora supongamos $r,s > 1$, y al menos $t$ segmentos han sido elegidos. Considerar los vértices $A_1$$B_1$. Si ambos son extremos de más de un segmento elegido, luego cada uno debe estar conectado a al menos otro punto. Deje $A_1$ estar conectado a $B_j$ ($j > 1$) y $B_1$ estar conectado a $A_i$ ($i > 1$). Pero, a continuación, $A_1A_iB_1B_j$ es un convexo cuadrilátero con dos lados adyacentes elegido, una contradicción. De modo que al menos uno de $A_1$ o $B_1$ es un extremo de un segmento elegido. Si queremos eliminar, en el resultado (aún convexo) $t-1$-gon hemos perdido a más de un segmento elegido, así que al menos $t-1$ elegido segmentos restantes, contradiciendo la hipótesis inductiva. Por lo tanto, en la mayoría de las $t-1= r+s-1$ segmentos pueden ser elegidos.

---

Volviendo a la original polígono que tiene en la mayoría de los $n-s-r+1$ elegido segmentos conectados a $A_0$, y del lema, en la mayoría de las $r+s-1$ segmentos no se adjunta a $A_0$, o en total en la mayoría de los $n$ elegido segmentos.