Pregunta de combinatoria, Olimpiada de Matemáticas del Área de la Bahía 2016, Encontrar una fórmula general

Question

Las esquinas de un fijo convexo (pero no necesariamente regular) n-gon se etiquetan con distintas letras. Si un observador se encuentra en un punto en el plano del polígono, pero fuera del polígono, que ven las letras en orden de izquierda a derecha, y que deletrear una "palabra" (es decir, una cadena de letras; no necesita para ser una palabra en cualquier idioma).

Determinar, como una fórmula en términos de $n$, el número máximo de distintos $n$letra que se puede leer de esta manera a partir de una sola $n$-gon. No cuentan las palabras, en las que alguna letra que falta porque está directamente detrás de otra carta desde el visor de posición.

//Mi//

• Primero me doy cuenta de que hay un bijection entre el número de palabras y {lados y diagonales}:
• En la ampliación de cada borde a ambos lados, fuera del polígono, el plano se divide en $2n$ partes. De pie en cada uno de estos lados, le da una palabra diferente.
• Además, la ampliación de cada diagonal a ambos lados añade más la división del plano, igual a dos veces el número de diagonales de $n$-gon, que es $$2(\binom{n}{2}-n)$$
• La adición de estos dos da $$2\binom{n}{2}$$
• No sé, pero esto parece el trabajo de triángulos, cuadriláteros y tal vez incluso pentágonos.

En el sitio oficial de la solución de la página, dos soluciones son: Uno es feo y bueno, parece complicado. El otro es dado ser: $$2\binom{n}{2}+2\binom{n}{4}$$ que mi solución está más cerca. Cualquier ayuda para conseguir que se agradece. Y, por favor señalar si he hecho algo mal.

Muchas gracias, buen signiors, por tu ayuda voy a estar eternamente obligado ;-)

Answer 1

Según lo indicado por @WW1 debemos tener en cuenta que un general convexa $n$-gon lo que significa que no hay dos líneas que conectan los rincones de la $n$-gon son paralelas. De lo contrario, la fórmula \begin{align*} 2\binom{n}{2}+2\binom{n}{4} \end{align*} en general no es válida.

Podemos derivar el término $2\binom{n}{2}$ como sigue:

• Fijamos una posición $P$ fuera de la convexo $n$-gon y mirar en las esquinas de la $n$-gon de izquierda a derecha.

  Podemos asumir de acuerdo con el problema que $P$ no se encuentra en una línea de vista de dos esquinas . Esto implica que cada vez que se cruza una línea que conecta dos esquinas cambiamos el orden de las esquinas cuando se mira desde la izquierda a la derecha.

  Desde allí se $\binom{n}{2}$ diferentes líneas que conectan dos de $n$ esquinas podemos leer \begin{align*} \color{blue}{2\binom{n}{2}} \end{align*} diferentes palabras de esta manera.

El siguiente gráfico da $2\binom{4}{2}=12$ azul marcado palabras diferentes en el caso de una $4$-gon. Tenga en cuenta que no hay dos líneas que unen dos vértices están en paralelo.

El plazo adicional $2\binom{n}{4}$:

• Cada vez que escogemos $4$ esquinas de la $n$-gon, nos puede visitar en sentido antihorario y conectar cada dos días consecutivos de las esquinas con una línea.

  Ya que por supuesto, no hay dos líneas son paralelas, dos pares de líneas que se intersecan con la definición de este modo, dos de las regiones que no han sido considerados en el primer caso.

  Hay $\binom{n}{4}$ diferentes formas de seleccionar $4$ esquinas y cada selección da lugar a dos nuevas regiones. Obtenemos \begin{align*} \color{blue}{2\binom{n}{4}} \end{align*} las palabras adicionales de esta manera.

El siguiente gráfico muestra un (general) $4$-gon y el $2\binom{4}{2}+2\binom{4}{4}=12+2=14$ diferentes palabras. Las otras dos regiones, dando $2\binom{4}{4}=2$ palabras están marcados en gris.

Nota: a partir De la gráfica es obvio que las líneas paralelas de reducir el número de regiones que podemos obtener reducir también el número de palabras diferentes.