sábado, 8 de enero de 2011
Problema de Año nuevo
Aun no han salido soluciones del Problema de Triangulaciones que les dejé más abajo, por si no lo han visto, es la publicación anterior al Recordatorio Examen #2.
Suscribirse a:
Comentarios de la entrada (Atom)
8 comentarios:
ya lo habiamos hecho en un entrenamiento del año pasado antes de diciembre
¿Cuentan como subtriángulos los triángulos degenerados? (si no es así, puedo encontrar contraejemplos)
Creo que tengo algo:
Supongamos que no es cierto, buscando el peor caso posible y lleguemos a una contradicción.
Supongamos que tras hacer la subdivisión en el segmento BC quedan n vértices nuevos (para formar subtriángulos). como estos tienen ya sea la etiqueta B, o C, por lo que como los extremos tienen etiquetas distintas, hay al menos un segmento de subtriángulo en BC que recibe etiquetas distintas en los vértices que lo determinan. Como éste es un segmento de subtriángulo, el otro vértice del triángulo debe estar conectado a ambos. Este vértice no puede ser A porque acabaríamos, entonces es B o C.
En el subtriángulo, tenemos que dos vértices tienen una misma etiqueta y el otro tiene una etiqueta distinta. Supongámos sin pérdida de generalidad que los vértices son B, B, y C. Uno de los segmentos de subtriángulo BC está en el segmento del triángulo original BC y el otro está dentro del triángulo (posiblemente en el lado AB, y en el caso de B, C, C en AC).
Si el nuevo segmento de este subtriángulo con etiquetas distintas está a su vez dividido por más vértices y al menos un segmento delimitado por dos vértices (sin que haya un vértice entre ambos) es BC trazamos el otro vértice de este subtriángulo al exterior del primero, porque sino, el primer subtriángulo creado no era el más pequeño abarcando esa área, tal y como habíamos supuesto, y debimos haberlo subdividido más. por lo que el otro vértice debe ser nuevamente B o C.
(continuación)
Repetiríamos el proceso hasta que lleguemos a un lado del triángulo original o hasta llegar a uno de los segmentos de subtriángulo ya analizados. Si el primero ocurre en BC, tendríamos dependiendo del caso, en BC, ya sea tres vértices continuos B, C, B ó C, B, C y en cualquier caso se formó otro segmento de subtriángulo con etiquetas B y C en dos de sus vértices y repetiríamos el proceso, y como sólo hay n vértices en BC esto es finito y en algún momento ya no se podría hacer más.
Si ocurre el primero en AB o en AC, como el otro segmento está delimitado por un vértice etiquetado con B y otro con C, entonces éste para no cumplir con la hipótesis debe ser, en el caso de AB, B y en el caso de AC, C por las reglas de etiquetado, y nuevamente, podemos seguir nuestro proceso de tríangulos B,B,C y C,C,B.
En cambio, si ocurre el segundo, y llega a un segmento de subtriángulo ya hecho, entonces se forma otro segmento de subtriángulo con etiquetas B y C ya que el segmento al cual debieron llegar tiene dos etiquetas iguales, de lo contrario, estos triángulos, o son el mismo, o uno está dentro / atravesando del o al otro, lo cual no es posible. Sin embargo, este nuevo vértice "viene" de otro segmento de subtriángulo BC, (ya que tiene etiquetas distintas) por lo que si el nuevo vértice es de la misma etiqueta que el segmento de subtriángulo al que llegó (digamos sin pérdida de generalidad que es B) entonces o hay un triángulo más a formar por el nuevo segmento de vértices con diferentes etiquetas creado o sucede que este segmento está sobre un segmento de subtriángulo ya creado y eso quiere decir que el nuevo vértice es uno de los vértices determinantes del segmento de subtriángulo al cual llegamos, pero veamos que esto sóle es posible si dos vértices estuvieron "piboteando" alrededor de otro al crear nuevos vértices y fue girando la figura en la que nos fijábamos.
Ahora ignoraremos por un momento el segmento al cual llegó el nuevo vértice y veremos que si estuvo pasando lo que describí, entonces significa que estuvo piboteando alrededor de ya sea un vértice B o uno C, supongamos pues sin pérdida de generalidad que era B. Como éste era originalmente parte de un triángulo con etiquetas B,B,C o B,C,C en sus vértices, entonces para seguir "girando" deberían ser los nuevos vertices que se crean, todos C, de lo contrario, la contrucción ya no se haría sobre un segmento delimitado por éste vértice (alrededor del cual "pibotean") de modo que al llegar alsegmento de subtriángulo del primero considerado, si éste era BC, significa que al triángulo anterior a éste (puesto que si existe, de lo contrario estaría en el lado BC y no se podría hacer esto) ya lo atravesamos y entonces no fue posible hacer esto, por lo que hubo por ahí un vértice que en vez de haber sido C, fue o A o B, en el primer caso, acabamos, en el otro caso, podemos seguir haciendo triángulos siguiendo este método. En caso de que fuera BB, entonces al llegar un C en el segmento de un BB significa que podemos hacer más triángulos (suponiendo de nuevo que hay al menos un segmento de subtriángulo que tiene B y C en sus vértices delimitantes.
(continuación, esta página no me dejó envial la otra mitad, así que en un momento lo escribo de nuevo un poco resumido)
Podemos llevar esto acabo sin importar qué: si llegamos nuevamente al lado BC compartiendo lado, entonces significa que hay al menos otro segmento de subtriángulo BC en BC, en otros lados del triángulo deberíamos incluir cualquier valor posible excepto el A puesto que significaría contradicción. si se llega a compartir lado con un segmento de subtriángulo ya hecho, igual podemos ver que o cortó un triángulo ya hecho, o se formó un nuevo lado delimitado por etiquetas distintas al compartir segmentos completos en los subtriángulos, o en los tres puntos colineales, hay dos parejas de puntos con diferentes etiquetas en esa recta que forman segmentos de subtriángulos y aunque una ya no la podemos usar, la otra sí y continuamos formando triángulos con base BC (si seguimos suponiendo que entre cada B y C hay al menos un segmento BC)
Ahora, si no hubiese tal cosa como vértices B y C continuos en el segmento de subtriángulo, entonces hay cuando menos una A y siempre hay un segmento de subtriángulo formado por un A y un C, y otro con un A y un B. Para probar esto, veamos que cada BC debe estar separado por al menos una A, entonces tomamos ese C y el A más próximo, y del otro lado al B y al A más próximo. entonces, sobre ambos vamos a crear subtriángulos, sobre estos segmentos.
tomemeos por ahora al AC, si el tercer vértice es A, entonces debe haber ya sea otro BC o nuevamente hay un AC por ahí y nuevamente podemos seguir creando más y más triángulos de esta manera sin detenernos en ningún momento (sea cual sea el caso, por los casos analiados anteriormente aplicados para AB, y AC también, incluso si también entre esos encontramos o no algunos BC, siempre podemos hacer más triángulos), lo mismo para con el subtriángulo de hace rato que tenía base AB, de manera que para que no se cumpla la hipótesis, deberíamos poder trazar infinitamente triángulos de cuando menos uno de estos tipos, pero como la subdivisión ya está hecha, en algún momento nos acabaremos los subtriángulos disponibles, así que de cualquier modo, encontraremos algún triángulo que en sus vértices tendrá las tres etiquetas (a menos que se puedan hacer trazos indefinidamente).
O.o simpre si se envió.... qué raro, a mi me apareció "Error, su mensaje no ha podido ser enviado" pero bueno...
@Enrique:
Sí valen degenerados, si, por ejemplo, tres de tus vértices quedan en una linea, sí puede considerarse un subtriángulo..
Llamemos segmento bicolor a un lado de algun triangulo de la triangulacion con sus dos vertices con distinta letra.
Hay tres tipos de triangulos
*)con los tres vertice de la misma letra y no tendra segmentos bicolores
**)con un vertice de una letra y dos de otra y tendra dos segmentos bicolores
***)sus tres vertices distintos y tendra 3 segmentos bicolores.
Contamos los segmentos bicolores en la triangulacion,
todo segmento en el interior petenecera a dos triangulos, asi que lo contamos doble, por lo tanto en el interior habra una cantidad par.
nos fijamos ahora en los segmentos de un lado(quesolo pertenecen auntriangulo),si nos situamos en el vertice A y caminamos al B, cada que haya un vertice bicolor cambiaremos de B a A o de A a B(de otro modo no habra cambio), y como vamos de un vertice A a uno B, tendra q haber una canidad impar de cambios y por lo tanto habra una cantidad impar de segmentos bicolores en cada lado, y como hay 3 lados, habra una cantidad impar desegmentos bicolores en los 3 lados, y tambien en total habra una cantidad impar de segmentos bicolores.
Si los triangulos fueran solo del primer o segundo tipo, habria una cantidad par de segmentos bicolores y esto no se puede, por lo tanto habra al menos uno con sus tres vertices distintos.
Publicar un comentario