Triángulos disjuntos

Os traigo hoy el problema de esta semana. Ahí va su enunciado:

Supongamos que tenemos 3n puntos del plano, A_1, \ldots , A_{3n}, 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 n triángulos disjuntos cuyos vértices están en los puntos A_i.

Que se os dé bien.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

18 Comentarios

  1. 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.

    Publica una respuesta
  2. 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.

    Publica una respuesta
  3. Disjunto es, que no tengan puntos en común.

    (Luego no pueden compartir ni intersectar vértices ni aristas).

    Publica una respuesta
  4. 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.

    Publica una respuesta
  5. 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 ellos estará formado por puntos “mayores” que el otro. Es fácil ver que cualquier punto de este triángulo será “mayor” que cualquier punto del otro triángulo. Por tanto, no tendrán ningún punto en común.

    Sé que es un poco parrafada, pero creo que es la manera más simple.

    Publica una respuesta
    • Puede ser un punto con menores coordenadas pero con un ángulo polar mayor y esto intesectará las aristas

      Publica una respuesta
  6. Ahora que lo miro, creo que he dicho lo mismo que X pero con otras palabras!

    Publica una respuesta
  7. 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.

    Publica una respuesta
  8. 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 la que cada par de puntos conforme un lado del cuadrilátero. Si aplicamos esto a cada inteseccion que encontremos nos daremos cuenta que la suma de los perimetros es la minima que podemos alcanzar.

    No se si mi razonamiento es correcto, pero de todas formas faltaría demostrar que la funcion f tenga un mínimo y no tengo ni idea de como hacerlo… XD

    Publica una respuesta
  9. 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 los vértices situados sobre una misma recta vertical han de tener distinta ordenada por ser puntos distintos. En consecuencia, todos los n triángulos serán disjuntos dos a dos. El algoritmo sería: 1º) Ordenar los puntos por abscisas crecientes (en caso de igualdad, se puede dirimir, por ejemplo, por menor ordenada). 2º) Elegir ternas de puntos siguiendo el orden establecido.

    Este método constructivo (que también se puede hacer mediante bandas horizontales) prueba, a su vez, que no es necesaria la condición de no linealidad para la construcción de n triángulos disjuntos; en efecto, basta una condición más suave: que no haya colinealidad vertical u horizontal (cualquiera de las dos vale).

    Un simple esquema gráfico clarifica la situación.

    Publica una respuesta
  10. 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).

    Publica una respuesta
  11. 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.

    Publica una respuesta
  12. 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”.

    Publica una respuesta
  13. 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.

    Publica una respuesta
  14. 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.

    Publica una respuesta
  15. 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.

    Publica una respuesta
  16. 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.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Os traigo hoy el problema de esta semana. Ahí va su enunciado: Supongamos que…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *