Desafíos GaussianosyGuijarro: Desafío nº 10 – “Pseudo-triángulos y pseudo-triangulaciones”

Después de unos meses sin ellos, publicamos un nuevo desafío de la serie Desafíos GaussianosyGuijarro (GyG), de Gaussianos y Libros Guijarro. En esta ocasión nos lo propone David Orden (@ordend en Twitter), profesor titular del área de Matemática Aplicada en el Departamento de Física y Matemáticas de la Universidad de Alcalá y autor del joven pero muy buen blog sobre matemáticas Cifras y Teclas. El problema en cuestión se titula Pseudo-triángulos y pseudo-triangulaciones y su enunciado es el siguiente:

Todos sabemos lo que es un triángulo, un polígono cerrado con tres vértices, y además sabemos que en esos tres vértices el ángulo interior es menor que 180 grados. Pero no tanta gente sabe lo que es un pseudo-triángulo, que se define como un polígono cerrado con tres vértices tal que el ángulo interior en cada uno de ellos es menor que 180 grados.

La figura muestra tres ejemplos de pseudo-triángulos; el de la izquierda es de hecho un triángulo, el del centro tiene cuatro lados y el de la derecha tiene ocho lados. La diferencia con el triángulo es que, además de los tres vértices con ángulo interior menor que 180 grados, en un pseudo-triángulo puede haber otros vértices, todos ellos con ángulo interior mayor que 180 grados (los ángulos iguales a 180 grados llevarían a casos degenerados, que vamos a descartar aquí).

Supongamos ahora que tenemos un conjunto P de puntos en el plano. De manera análoga a la definición de triangulación, podemos definir una pseudo-triangulación de P como una colección finita de pseudo-triángulos que usan sólo puntos de P y que cumplen dos condiciones:

  1. No hay solapamientos, es decir, dados dos pseudo-triángulos o bien no se intersecan, o bien lo hacen en un punto de P, o bien lo hacen en un lado de un pseudo-triángulo.
  2. La unión de esos pseudo-triángulos es la envolvente convexa de P (el convexo de menor área que lo contiene).

La figura muestra dos ejemplos de pseudo-triangulaciones; la de la izquierda es de hecho una triangulación, porque sólo usa triángulos (que son pseudo-triángulos de 3 lados), mientras que en la de la derecha se usan también pseudo-triángulos de 4 lados.

A este tipo de pseudo-triangulaciones que usan pseudo-triángulos de 3 ó 4 lados se les llama 4-pseudo-triangulaciones y de todas ellas nos vamos a centrar en las 4-pseudo-triangulaciones puntiagudas, aquéllas con la propiedad de que todos los puntos son puntiagudos, es decir, incidentes a algún ángulo mayor de 180 grados.

En la figura anterior, la de la derecha es una 4-pseudo-triangulación puntiaguda, mientras que la de la izquierda no lo es (de hecho, sólo los puntos exteriores son puntiagudos).

PREGUNTA 1: Si tenemos un conjunto de puntos dentro de un triángulo, ¿existe siempre una 4-pseudo-triangulación puntiaguda del conjunto total?

PREGUNTA 2: Supongamos que tenemos un conjunto de puntos dentro de un triángulo y una 4-pseudo-triangulación puntiaguda del conjunto total. Si queremos colorear los puntos de modo que no haya un segmento con ambos extremos del mismo color, ¿cuál es el menor número de colores con el que puede hacerse?

Como siempre se pide tanto la solución del problema como el razonamiento que ha llevado a la misma. Como estamos en verano dejaré más tiempo de lo habitual (que solía ser un mes) para que enviéis vuestra solución. Debéis hacerlo antes de que termine el domingo 29 de septiembre de 2013 a la dirección de correo electrónico desafiosgyg (arroba) gmail (punto) com. Por tanto disponéis de más del doble del tiempo habitual. Así tendréis tiempo para pensarlo con calma. Ah, y por si os sirve de ayuda también podéis echar un vistazo a la entrada que el propio David escribió en su blog acerca de estos pseudo-triángulos.

Las mil caras de la belleza geométricaEntre los que envíen una solución correcta para este desafío se sorteará un premio aún por decidir. En cuanto lo sepa edito este post y lo comento el libro Las mil caras de la belleza geométrica, de Claudi Alsina. La descripción que aparece en la web de Libros Guijarro sobre este libro es la siguiente:

Unas figuras con especial glamour destacan en el mundo de los cuerpos geométricos: los poliedros. Viven entre nosotros y nos ofrecen formas artísticas de gran belleza, pero también soluciones funcionales muy útiles. Han interesado desde siempre a los geómetras, pero también a cristalógrafos y arquitectos, a pintores y escultores, a fabricantes de cajas y joyeros… Verlos es admirarlos. Este libro nos permite adentrarnos en la historia de los poliedros en las matemáticas, en los diferentes tipos, en las formulaciones teóricas vinculadas a ellos de grandes matemáticos, pero también en sus aplicaciones prácticas y en la fascinación que ha provocado siempre su belleza.

Que se os dé bien.


Recordad que en principio los comentarios están abiertos para que habléis sobre el problema y, si acaso, deis alguna ayuda, pero nada más. Por favor, no publiquéis la solución, dejad que la gente se divierta con el problema. Gracias.

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.

9 Comentarios

  1. No entiendo la definición “…un pseudo-triángulo, que se define como un polígono cerrado con tres vértices tal que el ángulo interior en cada uno de ellos es menor que 180 grados.” porque luego pone ejemplos que tienen más de tres vértices. Además el polígono del ejemplo central tiene un vértice con un ángulo interior mayor que 180 grados. Entonces ¿cuál es la definición? Gracias 🙂

    Publica una respuesta
  2. Vale, ahora he entendido la definición, creo que falta una coma: …un pseudo-triángulo, que se define como un polígono cerrado, con tres vértices tal que el ángulo interior en cada uno de ellos es menor que 180 grados.”

    Publica una respuesta
  3. Creo que en las preguntas 1 y 2 hay que decir de los conjuntos de puntos dentro del triángulo que son finitos; supongo que “dentro” alude a puntos no en los lados, es decir, “interiores” (topológicamente) al triángulo.

    Publica una respuesta
  4. @Bosco: Así es, siento si no estaba suficientemente claro. En la entrada de Cifras y Teclas está explicado de otra forma, por si aún quedan dudas.

    @Luis GSA: Efectivamente, los conjuntos de puntos son finitos. En algún momento hablé de una cantidad finita de pseudo-triángulos, pero ahí se me olvidó.

    Si hay más dudas, preguntad. Para contestar a las preguntas no hacen falta conocimientos específicos, sólo pensar y dibujar. ¡Ánimo! 🙂

    Publica una respuesta
  5. Quisiera proponer dos artículos: uno sobre la clasificación de las diferentes ramas de las matemáticas y otro sobre los fundamentos de las matemáticas.

    Saludos para todos.

    Anónimo

    Publica una respuesta
  6. No me queda claro que define 4-pseudo-triangulaciones, se refiere a las pseudo-triangulaciones que usan pseudo-triangulos de lados 3 y 4 a la vez, o se refiere a las que usan pseudo-triangulos de 3 o 4 ?

    Porfavor si alguien pudiera aclararmelo

    gracias

    Publica una respuesta
  7. Al principio me parecía un problema complejo, y que hay que tener algún conocimiento de topología, pero la verdad es que pintando en un papel se puede obtener la solución sin escribir ni fórmulas ni nada.

    Lo que no entiendo es el comentario del “conjunto finito de puntos”. Yo no veo diferencia alguna. Puedo obtener la misma conclusión para infinitos puntos. Así que, o mi conclusión no es exacta (o no cubre totalmente lo propuesto) o bien no hay diferencia entre que sean infinitos puntos o no.

    Publica una respuesta
  8. @Cartesiano Caotico: Enhorabuena por llegar a una solución; como decía, no hacen falta conocimientos específicos, sólo pensar y dibujar 🙂

    El que haya un número finito de puntos y pseudo-triángulos permite buscar soluciones algorítmicas, evitando bucles infinitos. Eso no significa que sólo existan soluciones de ese tipo, pero deja lo más abierto posible el abanico de posibilidades.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Después de unos meses sin ellos, publicamos un nuevo desafío de la serie Desafíos…
  2. Une los puntos con estas condiciones y gana un premio con las pseudo-triangulaciones | Cifras y Teclas - […] vamos a añadir una tercera condición, también facilita, con la que podrás participar en el Décimo desafío Gaussianos-Guijarro y…
  3. Recordatorio: décimo Desafío Gaussianos y Guijarro "Pseudo-triángulos y pseudo-triangulaciones" - Gaussianos | Gaussianos - […] Universidad de Alcalá y autor del blog Cifras y Teclas. Podéis acceder al enunciado del desafío haciendo click en…
  4. Desafíos GaussianosyGuijarro - Desafío nº 10: "Pseudo-triángulos y pseudo-triangulaciones" - Solución y ganador - Gaussianos | Gaussianos - […] unas semanas que terminó el plazo para el envío de soluciones del Desafío GaussianosyGuijarro nº 10: Pseudo-triángulos y pseudo-triangulaciones,…

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 *