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.

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