Nuevo desafío de la serie Desafíos GaussianosyGuijarro (GyG), de Gaussianos y Libros Guijarro. Hoy os traigo el quinto de la serie, propuesto en este caso por mis queridos y apreciados Alberto Márquez y Clara Grima. El problema se titula Coloreando vértices y tiene dos partes. Vamos con el enunciado:
1) Coloreamos los vértices de un polígono de tal forma que dos vértices no pueden tener el mismo color si son los extremos de una arista. ¿Cuántos colores son necesarios para colorear un polígono de n lados?
2) ¿Cuántos segmentos que unan dos vértices de un polígono se han de añadir a dicho polígono (dejaría de serlo) para que necesitemos más colores de los obtenidos en 1)?
Un par de imágenes que me ha enviado Clara Grima para aclarar algo más el desafío:
- Al añadir una nueva arista el polígono deja de serlo y, posiblemente, hay que cambiar la coloración de los vértices implicados:
- Al añadir aristas, las que sean, entre los vértices iniciales del conjunto, éstas se pueden cruzar entre ellas, o incluso cortar a las aristas originales del polígono, pero estos cruces no generan nuevos vértices. El conjunto de vértices no varía, es siempre el inicial. En el caso de la figura, sólo los puntos rojos son vértices:
Como siempre se pide tanto la solución del problema como el razonamiento que ha llevado a la misma. Las respuestas deben enviarse antes de que termine el domingo 26 de agosto 16 de septiembre de 2012 a la dirección de correo electrónico desafiosgyg (arroba) gmail (punto) com.
Sobre el premio, todavía no está decidido cuál será el de este desafío. En cuanto lo esté os lo comunicaré en este post, pero mientras tanto podéis enviar vuestras soluciones. Ya tenemos premio. Será la novela Quantic Love, de Sonia Fernández-Vidal. Os dejo la descripción que aparece en Libros Guijarro:
Quantic Love es la novela que resuelve la ecuación del amor.
En el CERN, el centro de investigación más avanzado del mundo, entre experimentos de viajes en el tiempo y de teletransportación, entre partículas que superan la velocidad de la luz y otras que revelan el origen del Universo, la joven Laila se enfrenta al mayor misterio que existe: cómo decidir entre dos amores. Por un lado, Alessio, un atractivo periodista; y, por otro, Brian, un cerebral científico que oculta un gran secreto.
Laila es una jóven sevillana con un único objetivo, trabajar durante el verano para poder pagarse su primer año en la universidad. Una vez allí conoce a Angie, su compañera de piso, que convierte un verano sacrificado y duro en algo inolvidable; un verano en el conocera a gente nueva que le abrirá nuevas fronteras y la harán sentirse como en casa. Amigos y compañeros con los que intentará resolver la ecuación del amor.
Quantic Love es, en fin, una historia entretenida y original en la que los personajes están muy bien definidos y provocan empatía sincera con el lector. Un nuevo experimento de Sonia Fernandez Vidal vivo y divertido.
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.
Actualización:
Se amplía el plazo para enviar la solución de este quinto desafío GyG hasta el 16 de septiembre. Esperamos vuestras respuestas.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: Nuevo desafío de la serie Desafíos GaussianosyGuijarro (GyG), de Gaussianos y Libros Guijarro. Hoy os traigo el quinto de la serie, propuesto en este caso por mis queridos y apreciados Alberto Márquez y Clara Grima. El pro……
Se supone que en donde dice arista debe decir lado.
La pregunta 1) tiene dos respuestas. La pregunta 2) tiene dos repuestas.
En tres de las cuatro respuestas se utiliza el mismo número mínimo de colores y en la cuarta se necesita un número de colores inferior al de las otras tres.
¿Soy yo o este desafío es especialmente fácil? O a lo mejor lo he planteado mal, cosa que no me extrañaría, jaja
No me queda muy clara la 2). ¿Pregunta por el número necesario o suficente?
Una cuestión, en el apartado 2) los segmentos añadidos pueden cruzarse entre sí?
O no entiendo bien el enunciado o 1) es demasiado fácil
¿En la pregunta 2), si los segmentos pueden cruzarse, en los cruces cuántos vértices se cuentan?
Voy a intentar aclara algunas de las dudas manifestadas en los comentarios: En realidad lo que tenemos es un grafo http://es.wikipedia.org/wiki/Grafo : Los vértices del grafo son los vértices del polígono y las aristas del grafo son los lados del polígono. Así la pregunta 1 es: ¿cuántos colores son necesario para colorear los vértices del grafo obtenido a partir de un polígono de tal forma que dos vértices que compartan una arista no pueden tener el mismo color? Evidentemente esta pregunta, tal y como dicen algunos, es muy, muy sencilla: de calentamiento. La pregunta 2 sería: Al grafo anterior le… Lee más »
Pero, si no se crean vértices nuevos a partir de esas aristas, cómo aumenta el número de colores?
Si aumenta el número de aristas (sin aumentar el número de vértices), aumentan las incompatibilidades entre los vértices (recordemos que si dos vértices están unidos por una arista, entonces no pueden tener el mismo color) y por tanto necesitaremos más colores (en general).
Os dejo un dibujo sobre la 2)
https://twitter.com/ClaraGrima/status/232154526436704257/photo/1/large
En la figura de la izquierda, los dos vértices en amarillo pueden tener el mismo color, pero en la de la derecha, al añadir la nueva arista, ya deben usar colores distintos.
Por si aclara 🙂
Clara Grima, bufff, me parece que eso es dar mucha pista ya, porque ya das parte de la solución del segundo apartado… jaja
¿Estás seguro Imanol? 😉
Sí que es cierto que hay dos respuestas para cada pregunta. La primera es un poco más sencilla de exponer, la segunda hay que generalizarla con algún detalle adicional.
Al menos es mi impresión a simple vista.
Sólo una cosa, creo que habría que matizar algo más la segunda pregunta, quiero entender que se pide el mayor número de segmentos que obliga a utilizar más colores, porque el cambio lo puedes obligar con un sólo segmento, y eso sería muy obvio.
En el segundo apartado me da 3 soluciones, alguien piensa lo mismo?
En el segundo apartado… cuantos casos hay? me salen varios…
Estoy de acuerdo con Julio, yo lo expondria como: el minimo numero de segmentos que.colocados al azar aseguran que se necesiten mas colores.
En cuanto al numero de soluciones yo no diria que son dos. Yo diria que son 3. Y ademas al no estsr el enunciado totalmente claro podriamos hablar de mas soluciones.
Cartesiano caotico: No, no es el mínimo número de segmentos que colocados al azar aseguran que se necesiten más colores. Si te fijas, Alberto deja claro en su comentario que: «¿cuál es el número mínimo de aristas que necesitamos añadir, y CÓMO, para aumentar el número necesario de colores a los obtenidos en la pregunta 1?».
Por lo tanto, como hay que decir cómo colocarlas, los segmentos no se colocan al azar, sino siguiendo una «estrategia».
Yo creo que asi no tiene sentido. En ese caso, como apuntaba Julio bastaria un solo seg.ento para unir dos vertices del mismo color. Estrategia Trivial.
Cuando digo al azar me refiero al numero minimo que asegure que al menos uno de los segmentos obligue a aumentar el numero de colotes
Estoy contigo cartesiano caótico, bastaría con uno o dos segmentos(según los tipos de soluciones); el problema es encontrar el número mínimo de segmentos que nos obligue a aumentar esos colores.
Lo sé, sé que así es muy fácil, pero el mismo Alberto (coautor del desafío) ha sido el que ha dejado el comentario, así que para bien o para mal me imagino que será así.
Prueba (ignorar este comentario).
Imanol, cartesiano: tal y como dice Imanol la segunda parte del desafío es: «Al grafo anterior le añadimos algunas aristas además de las ya existentes: ¿cuál es el número MÍNIMO de aristas que necesitamos añadir, y CÓMO, para aumentar el número necesario de colores a los obtenidos en la pregunta 1?» Pero: tal y como se ha dicho, la primera parte es fácil es para preparar esta segunda: hay que probar cuántos segmentos necesitamos añadir en cada uno de los caso obtenidos en la primera parte y, espero que ^DiAmOnD^ no me riña, la respuesta no siempre es 1. La… Lee más »
Un sobre necesita cuatro colores
JJGJJG, o no dibujas el sobre como yo (abierto) o sólo necesitamos 3 colores: 2 para el rectángulo y un tercero para el vértice central y para el pico del sobre abierto.
JJGJJG, yo creo que un sobre necesita sólo 3 colores…
Yo supongo el sobre cerrado, cuatro vértices y dos diagonales. el cruce central no es un vértice. Al estar unidos los vértices exteriores tres a tres, no puede haber dos del mismo color, luego se necesitan cuatro.
JJGJJG, efectivamente si consideras 4 vértices todos unidos entre sí, lo que obtienes es el grafo completo de 4 vértices $K_4$ , es fácil ver que el grafo completo de n vértices necesita n colores.
[…] esta pequeña nota para informaros de que se amplía el plazo para el envío de soluciones del quinto desafío GaussianosyGuijarro hasta el 16 de septiembre de 2012. Recordad que tenéis que enviar vuestra propuesta de solución a […]
La Laia esa que ni siquiera ha hecho el primer año de universidad ¿como ha entrado a trabajar en el CERN?¿De limpiadora?
Norby, ¿?¿?¿?
[…] de un período de tiempo mayor del habitual os traigo la solución del Desafío GaussianosyGuijarro nº 5 – Coloreando vértices y, por tanto, del ganador de Quantic love. Se han recibido solamente 18 respuestas, de las cuales […]