Os traigo hoy el problema de esta semana. Ahí va su enunciado:
Supongamos que tenemos
puntos del plano,
, para los que se cumple que no hay tres de ellos que sean colineales (que estén en la misma recta). Demostrar que podemos construir
triángulos disjuntos cuyos vértices están en los puntos
.
Que se os dé bien.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Por construcción creo que se ve bastante claro (uniendo puntos dos a dos podemos partir el conjunto inicial, empezando por un extremo, vamos formando triángulos), aunque dudo que (salvo parrafada aburridísima) sirva de demostración.
Para las demostraciones elegantes desde luego no estoy dotado, espero con ansia alguna de ellas.
Digo yo que por «disjunto» se entiende que se puedan cortar en algún vértice o en algún lado, pero no en una porción del plano.
Disjunto es, que no tengan puntos en común.
(Luego no pueden compartir ni intersectar vértices ni aristas).
Se traza una recta que no sea paralela al segmento formado por ningún par de puntos, las cuales existen por haber infinitas inclinaciones de rectas y un número finito de pares de puntos. A continuación, barremos el plano, y cada tres puntos que pasemos los unimos (la recta nunca contendrá dos puntos a la vez). Por construcción, no puede haber triángulos cuya intersección sea no nula, por haber dividido el plano con rectas paralelas entre sí, y cada parte contener exactamente tres puntos. De esta manera se ha construido una solución.
Información Bitacoras.com…
Valora en Bitacoras.com: Os traigo hoy el problema de esta semana. Ahí va su enunciado: Supongamos que tenemos puntos del plano, , para los que se cumple que no hay tres de ellos que sean colineales (que estén en la misma recta). Demostrar que pode……
Sean los puntos de la forma (x,y). Ordenamos todos los puntos de la siguiente forma: un punto será «mayor» que otro si está más a la derecha (es decir, con la coordenada x mayor). En caso de empate (que compartan la coordenada x), el punto «mayor» será el de más arriba (es decir, con la coordenada y mayor). Una vez ordenados, vamos cogiendo los puntos de 3 en 3 formando triangulos. Podemos asegurar que los triangulos se forman porque no hay 3 puntos alineados. También podemos asegurar que todos los triángulos son disjuntos porque, dados dos triángulos cualesquiera, uno de… Lee más »
Puede ser un punto con menores coordenadas pero con un ángulo polar mayor y esto intesectará las aristas
Ahora que lo miro, creo que he dicho lo mismo que X pero con otras palabras!
Pirer, exactamente ese método es el que he implementado aquí usando HTML5.
Y no es el mismo que el indicado por X, pues como bien dices, no hace falta buscar una pendiente para la recta «partidora», pues en el peor de los casos, habrá dos puntos en la misma recta, en cuyo caso, tanto da tomar uno que otro para el rectángulo anterior y posterior.
Yo lo veo así: Si llamamos f a la función que es igual a la suma de los perímetros de n triángulos, veremos que cuando el valor de esta función es mínimo es cuando podemos construir n triángulos disjuntos. Me explico: de existir una intersección entre cualquiera de los lados, l y L, de dos triángulos (algo incompatible con la idea de que los triángulos sean disjuntos), los vértices que contienen estos lados formarían un cuadrilátero de diagonales l y L. Estas diagonales son siempre mayores que cualquiera de los lados del cuadrilátero, entones basta con hacer una agrupación en… Lee más »
Es casi trivial, ya que una solución se obtiene, por ejemplo, de esta forma: el primer triángulo se forma con los tres puntos de menor abscisa, y en caso de haber dos con igual abscisa (no puede haber más de dos por la condición de no linealidad), se puede elegir cualquiera de ellos. El segundo triángulo se forma, siguiendo el mismo criterio, con los puntos restantes, y repitiendo el proceso n veces se habran formado los n triángulos, los cuales serán disjuntos por estar contenidos en bandas verticales que , a lo sumo, tendrán en común la recta límite, pero… Lee más »
Se me ocurre, así de forma ‘batallera’, suponer que hay dos triángulos que no son disjuntos. Con lo cuál, el número de vértices no cumple la condición de que los An tengan 3n vértices. Aunque incluso a mí mismo me parece un razonamiento demasiado trivial e, incluso, incompleto (habrá que darle más vueltas).
Pues si comenzamos con un barrido de una recta, por ejemplo vertical, comenzando por el punto más a la izquierda, vamos avanzando hasta encontrar el tercer punto, esos formarán un triángulo, y repetimos hasta el final.
l hecho de que estén en posición general, es decir, sin que existan tres colineales, asegura que en ningún instante del barrido, la recta usada contendrá a 3 a la vez, que no formarían ningún triángulo.
se puede hacer también por induccion, si se cumple para 3n entonces para 3(n+1) basta con tomar los 3 «más alejados».
isaacv5, esa es la demostración que yo poseía, pero la de ClaraGrima me ha gustado más :).
Yo pensé lo mismo que Clara Grima, pero la demostración de X me parece más elegante.
En realidad es la misma idea, sólo que X se asegura primero de hacer el barrido con una recta en que jamás se encontrará con dos puntos al mismo tiempo, con lo que se ahorra considerar ese caso especial.
Como Clara Grima, ordeno los puntos de menor a mayor (o viceverza) de sus accisas (o por ordenadas, es indiferente), si hay repetición de accisa (u ordenada) es indistinto en la colocación. Y luego cada terna (empezando por el primer punto o cualquier multiplo de 3 y sus dos anteriores) de esta ordenación seran los vertices de los triangulos.
Lobo, hay una cosa errónea en tu razonamiento: 3 puntos alineados no forman ningún triángulo. Por tanto, siempre tendremos el caso en el que n=1, y tengamos 3 puntos alineados (según cualquier orientación) que no se pueden agrupar en un triángulo.
A) acentos una traslación de coordenadas al punto Ai.
B) con las nuevas coordenadas en su representación polar, tomamos aquel punto con el ángulo theta menor y el siguiente en tamaño formando con esos puntos el primer triángulo.
C) continuando con los puntos subsecuentes en tamaño del ángulo theta por pares.
Nota observé que si 3n es impar se formarán (3n-1)/2 triángulos con la descripción dada y si es par sobrará un punto y serán (3n-2)/2 pero en ambos casos son igual o más de n triángulos por lo que queda demostrado.