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:
- 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.
- 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.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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 GaussianosyGuijarro (GyG), de Gaussianos y Libros Guijarro. En esta ocasión nos lo propone David Orden (@ordend en Twitter), profesor titul……
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 🙂
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.”
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.
@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! 🙂
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
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
@Julian: Los pseudo-triángulos pueden ser de 3 lados o de 4 lados, pero no de otros tamaños.
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.
@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.
[…] 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 optar a llevarte un premio. Tú juegas a unir puntos, divirtiéndote mientras piensas, y te […]
[…] Universidad de Alcalá y autor del blog Cifras y Teclas. Podéis acceder al enunciado del desafío haciendo click en este enlace, donde también podréis ver cómo enviar vuestra solución. El plazo para ello sigue siendo, en […]
[…] unas semanas que terminó el plazo para el envío de soluciones del Desafío GaussianosyGuijarro nº 10: Pseudo-triángulos y pseudo-triangulaciones, y hoy os traigo la solución del mismo y el ganador de Las mil caras de la belleza geométrica, de […]