miércoles, 1 de febrero de 2012
Problema del día.
Sea $A_1A_3...A_{2n+1}A_2A_4...A_{2n}$ un $2n+1$-ágono convexo. Demuestra que de todas las líneas quebradas cerradas (osea todos los $2n+1-$-ágonos posibles, incluyendo los que tienen lados que se intersectan) cuyos vértices son los mismos que los del polígono inicial, la $A_1A_2...A_{2n+1}A_1$ tiene la mayor longitud.
Suscribirse a:
Comentarios de la entrada (Atom)
6 comentarios:
El caso $n=1$ es trivial, pues es el único camino. El caso $n=2$, con algunas desigualdades de triángulo, pues si una no es diagonal, entonces hay dos lados en la línea quebrada máxima y entoncs remplazando los lados con las diagonales de el cuadrilátero que forman sus vértices, se aumenta la distancia de la recta (algo así pero más formal viene abajo en el sieguiente párrafo). Supongamos que la línea quebrada cerrada de mayor tamaño es $B:=B_{1}B_{2}\dots B_{2n+1}B_{1}$ dónde $\{B_{1},\dots,B_{2n+1}\}$ es una permutación de $\{A_{1},\dots,A_{2n+1}\}$. Supongamos que la línea quebrada cerrada $B$ es distinta a $A:=A_{1}A_{2}\dots A_{2n+1}A_{1}$.
Supongamos que existen dos pares de valores de $B$, $B_{i}B_{i+1}$ y $B_{j}B_{j+1}$ tales que no se intersectan (en los segmentos) y tales que si $B_{i}B_{j}$ y $B_{i+1}B_{j+1}$ se intersectan (o la pareja que lo haga, así que supondremos que es esta, que es un caso análogo a este) no existen en $B$ (no están unidos). Claramente, dado que $B$ era cerrado, si cambiamos estos por $B_{i}B_{j}$ y $B_{i+1}B_{j+1}$ entonces sabemos que lo que resulta también es una línea quebrada cerrada pues cada vértice está conectado con exactamente otros dos (es conocido que como el grado de cada vértice es par, entonces existe un camino hamiltoniano (hay una línea quebrada cerrada)). Llamemos a la intersección de ambas $X$, de modo que $B_{i}X+B_{i+1}X\textgreater B_{i}B_{i+1}$ y $B_{j}X+B_{j+1}X\textgreater B_{j}B_{j+1}$ por la desigualdad del triángulo, así que $A_{i}B_{j}+A_{i+1}B_{j+1}\textgreater A_{i}A_{i+1}+B_{i}+B_{i+1}$ y como el resto de la línea sigue igual, así que la nueva línnea es mayor a $B$ lo que es contradicción y por lo tanto no existen dos partes de $B$ así, por lo que para cada pareja de segmentos de la línea quen o intersectan, entonces existe al menos una diagonal ( es un segmento que si consideramos los cuatro puntos que conforman los dos segmentos claramente por hipótesis del problema, forman un cuadrilátero convexo y entonces por hipótesis de al inicio del párrafo es diagonal de éste) que una e estos dos directamente en $B$.
Supongamos que hay tres segmentos que no se intersectan, dos a dos, en $B$, esto significa que entre ellos hay al menos una diagonal dos a dos, lo que implica que el ciclo se cierra y por lo tanto hay sólo $6$ vértices que es par, así que es imposible (pues hablamos de un $2n+1-$ágono).
Supongamos que hay dos segmentos no adyacentes en $B$ tal que tampoco se intersectan, por lo que vimos, cualquier otro segmento quen o sea adyacente al primero ni lo intersecte, entonces es adyacente al segundo o lo corta. Sean $B_{i}B_{i+1}$ y $B_{j}B_{j+1}$ estos segmentos, entonces una diagonal los une así que son consecutivos, así que SPG, $j=i+2$, además $B_{i+1},B_{i+2}$ tienen grado dos así que todas los demás segmentos deben intersectarlos, así mismo, como $B_{i}$ y $B_{i+3}$ tienen conexión con otro vértice, todos los demás segmentos deben cotrar los segmentos iniciales y en particular, $B_{i+3}B_{i+4}$ corta a $B_{i}B_{i+1}$ y $B_{i-1}B_{i}$ corta a $B_{i+2}B_{i+3}$. Si existe un segmento que corte a uno y no al otro, entonces debe ser adyacente a éste por lo que ya vimos.
En la figura convexa, no debe haber vértices entre las terminaciones de un segmento y las del otro (a menos que entre ellos esté la otra terminación del mismo segmento de donde empezamos a contar), pues un segmento que nace ahí, no puede cortar a ambos segmentos iniciales. entonces separemos al convexo en dos convexos, cada uno que tenga como lado a uno de los segmentos iniciales, así, estos dos conjuntos están bipartitos, excepto por estos lados, pues cualquier línea no adyacente a estos vértices, corta los dos segmentos. Además de que si es adyacente a uno, corta al otro así que el punto está en el otro convexo (si fuera adacente a ambos, es un $4-$ágono y $4$ es par así que no se puede). Por lo tanto, hay tantos puntos de un lado como del otro (porque es simétrico el comportamiento (no la figura), una línea de un convexo llega al otro y ambos tienen exactamente una línea dentro) pero entonces $2n+1$ es par, lo que es contradicción y entonces no existen tales segmentos, pues todos se cortan entre sí (o son adyacentes).
Con esto último, para un $i$, $B_{i}B_{i+1}$ y $B_{i+1}B_{i+2}$ son adyacentes pero todas las demás líneas cortan a ambos así que en el convexo, no hay ningun vértice entre $B_{i}$ y $B_{i+2}$ o un segmento saliendo de ahí no cortaría a ambos, además de que simétricamente, si partimos al convexo de manera similar a la anterior, pero ponemos a $B_{i+1}$ fuera de ambos, entonces hay tantos puntos en uno como en otro por la misma razón, así que $B_{i}B_{i+1}$ y $B_{i+1}B_{i+2}$ parten al convexo en dos partes con puntos diferiendo sólo en uno (para el primero, el $B_{i+2}$ y para el segundo el $B_{i}$) así que son en efecto, para alguna $j$, $A_{j}A_{j+1}A_{j+2}$, por lo que aplicándolo para todos, todos son así y entonces la línea quebrada más grande es la propuesta por el problema, QED. (Feo pero terminado)
Jorge, ¿cómo definiste la "nueva gráfica", donde intercambiaste $B_iB_{i+1}$ por $B_iB_j$? Por que según yo si nada más intercambias los dos segmentos quedan 2 ciclos cerrados, no 1...
Decimos que un polígono es válido si sus vértices son el del original. Primero veamos que si dos lados de un polígono váilido no se intersectan entonces hay un polígono válido con mayor prímetro.
Sea $Q$ un polígono válido en donde $A_aA_b$ y $A_xA_y$ son lados de $Q$ y son ajenos ($A_aA_bA_xA_y$ es un cuadrilátero convexo), sea $P$ el poligono que tiene los lados iguales a $Q$ excepto por los dos mencionados en donde $P$ tiene ahora a los lados $A_aA_x$ y $A_bA_y$ los cuales se intersenctan, entonces claramente por la desigualdad del triángulo $A_aA_x+A_bA_y\textgreater A_aA_B+A_bA_y$ y además $P$ es también válido entonces $Q$ no puede ser el de mayor perímetro.
Ahora veamos que si un polígono no es como el que dice el problema que tiene mayor perímetro entonces tiene dos lados que no se intersecta.
Sea $Q$ un polígono distinto al que queremos ver que es el máximo, sea $T$ el polígono convexo original, por definición de existe un lado de $Q$ (llamemos $r$ al lado) que parte al perímetro de $T$ de tal forma que uno de los dos conjuntos de la partición tiene igual o menos de $n-2$ vértices, sea $A$ ese conjunto de vértices y sea $B$ el conjunto de vértices de $T$ que quedaron del otro lado a los vértices de $A$ respecto a $r$. Si $Q$ es máximo, por lo que ya vimos cualquier pareja de lados de $Q$ se intersectan, entonces todos los lados intersectan a $r$, pero en $A$ a lo más hay $n-2$ vértices por lo que a lo más hay $2(n-2)$ segmentos que intersectan internamente a $r$ más los dos con los que $r$ comparte vértice a lo más tenemos entonces $2n-2$ lados intersectando a $r$ entonces por casillas hay un lado de $Q$ que no intersecta a $r$ (pues $Q$ tiene $2n$ lados) con lo cual se llega a una contradicción.
Disculpen, al final era "(pues $Q$ tiene $2n$ lados distintos a $r$)".
El caso n=1 y 3 es trivial, asi q n>= 2. Probemos el prooblema por contradicción. Supongamos que hay un "ciclo" $B_1B_2...B_{2n+1}B_1$ que pasa por todos los vértices del poligono sólo una vez, diferente de $A_1A_2...A_{2n+1}A_1$ y con la máxima longitud entre todas las líneas quebradas cerradas cuyos vértices son los mismos que los del polígono inicial.
Lema 1: si $B_1B_2$ y $B_iB_{i+1}$ no se intersectan con i e (i+1) diferentes de 1 y 2. Entonces
$B_1B_{i}B_{i-1}...B_2B_{i+1}B_{i+2}...B_{2n+1}B_1$
Tiene mayor longitud q $B_1B_2...B_{2n+1}B_1$.
Demostración.
El nuevo ciclo tiene los mismos lados con excepcion de $B_1B_2$ y $B_iB_{i+1}$ que los sustituye por $B_1B_i$ y $B_2B_{i+1}$, entonces basta demostrar $B_1B_i$ + $B_2B_{i+1}$ > $B_1B_2$ + $B_iB_{i+1}$. Como $B_1B_2$ y $B_iB_{i+1}$ no se intersectaban entonces $B_1B_i$ y $B_2B_{i+1}$ se intersectan en X.
Entonces por la desigualdad del triángulo
$B_1X$ + $B_2X$ > $B_1B_2$
y $XB_i$ + $XB_{i+1}$ > $B_iB_{i+1}$
Entonces $B_1B_i$ + $B_2B_{i+1}$ =
$B_1X$ + $XB_i$ + $B_2X$ + $XB_{i+1}$ >
$B_1B_2$ + $B_iB_{i+1}$. Con lo que se demuestra Lema 1.
Entoncs por Lema 1
$B_1B_2...B_{2n+1}B_1$ no tiene dos segmentos ajenos que no se intersectan, pues B_1 puede ser cualquier punto en el ciclo. Pero como no es igual q $A_1A_2...A_{2n+1}A_1$ y el polígono es convexo con 2n+1 lados. Entonces hay un segmento S.P.G $B_1B_2$ tal que divide al poligono en dos partes una parte C con menos de n-1 vertices de un lado y una parte D con más de n del otro.
Pero todos los 2n - 2 > 0 (pues n>=2) segmentos de $B_1B_2...B_{2n+1}B_1$ que son ajenos a B_1 y B_2 deben intersectar a $B_1B_2$, entonces deben ir de vertices de la parte C a vertices de la parte D pues el poligono es convexo.
Pero en la parte C hay a lo más n-2 vértices y de cada vértice salen a lo más dos segmentos. Entonces hay a lo más 2n - 4 segmentos q salen de vértices de C. Contradicción pues había al menos 2n-2.
Por lo tanto de todas las líneas quebradas cerradas (osea todos los $2n+1-$-ágonos posibles, incluyendo los que tienen lados que se intersectan) cuyos vértices son los mismos que los del polígono inicial, la $A_1A_2...A_{2n+1}A_1$ tiene la mayor longitud.
Publicar un comentario