Desafíos GaussianosyGuijarro – Desafío nº 5: Coloreando vértices (ACTUALIZADO)
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.
 |
Autor: ^DiAmOnD^ | Publicado el 3 de agosto de 2012
Categorías: Juegos | 
Imprime este post
Trackback | 3 ago, 2012
Bitacoras.com
JJGJJG | 3 de agosto de 2012 | 23:50
Vótalo
0
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.
Imanol Pérez | 4 de agosto de 2012 | 11:10
Vótalo
0
¿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
Víctor | 4 de agosto de 2012 | 12:32
Vótalo
0
No me queda muy clara la 2). ¿Pregunta por el número necesario o suficente?
Antonio | 4 de agosto de 2012 | 15:16
Vótalo
0
Una cuestión, en el apartado 2) los segmentos añadidos pueden cruzarse entre sí?
Norby | 4 de agosto de 2012 | 18:47
Vótalo
0
O no entiendo bien el enunciado o 1) es demasiado fácil
Marc | 5 de agosto de 2012 | 11:58
Vótalo
0
¿En la pregunta 2), si los segmentos pueden cruzarse, en los cruces cuántos vértices se cuentan?
Alberto | 5 de agosto de 2012 | 15:58
Vótalo
0
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 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? Naturalmente estas nuevas aristas son simplemente algo que une dos vértices, por lo tanto se pueden cruzar, pero al cruzarse no se crea ningún nuevo vértice: los vértices son siempre los originales.
Evidentemente, no sólo hay que decir cuántas aristas hay que añadir, también hay que decir dónde y demostrar que con menos aristas no se puede).
Muchas gracias a todos.
Encar | 5 de agosto de 2012 | 16:37
Vótalo
0
Pero, si no se crean vértices nuevos a partir de esas aristas, cómo aumenta el número de colores?
Alberto | 5 de agosto de 2012 | 16:58
Vótalo
0
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).
Clara Grima | 5 de agosto de 2012 | 18:52
Vótalo
0
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
Imanol Pérez | 5 de agosto de 2012 | 19:46
Vótalo
0
Clara Grima, bufff, me parece que eso es dar mucha pista ya, porque ya das parte de la solución del segundo apartado… jaja
Clara Grima | 5 de agosto de 2012 | 19:47
Vótalo
0
¿Estás seguro Imanol?
julio | 6 de agosto de 2012 | 10:56
Vótalo
0
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.
julio | 6 de agosto de 2012 | 13:34
Vótalo
0
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.
Antonio Galán | 6 de agosto de 2012 | 21:15
Vótalo
0
En el segundo apartado me da 3 soluciones, alguien piensa lo mismo?
Antonio Galán | 7 de agosto de 2012 | 11:12
Vótalo
0
En el segundo apartado… cuantos casos hay? me salen varios…
cartesiano caotico | 7 de agosto de 2012 | 17:20
Vótalo
0
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.
Imanol Pérez | 8 de agosto de 2012 | 10:09
Vótalo
0
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”.
cartesiano caotico | 8 de agosto de 2012 | 12:12
Vótalo
0
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
Encar | 8 de agosto de 2012 | 12:29
Vótalo
0
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.
Imanol Pérez | 8 de agosto de 2012 | 12:35
Vótalo
0
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í.
Alberto | 9 de agosto de 2012 | 10:45
Vótalo
0
Prueba (ignorar este comentario).
Alberto | 9 de agosto de 2012 | 10:58
Vótalo
0
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 estrategia que proponéis no siempre tiene que conducir a una coloración con el mínimo número de colores. Imaginad un grafo con 5 vértices y 5 aristas formando un pentágono, no creo desvelar mucho si digo que necesito 3 colores digamos que coloreo los vértices en orden cíclico (1,2,1,2,3), pero si uno los dos vértices con el color 1 con una arista, puedo dar la siguiente coloración: (1,2,3,2,3) y si uno los dos vértices con el color 2 también puedo dar una coloración con sólo 3 colores, luego, en este caso, la solución no es 1.
JJGJJG | 9 de agosto de 2012 | 11:26
Vótalo
0
Un sobre necesita cuatro colores
Alberto | 9 de agosto de 2012 | 11:29
Vótalo
0
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.
Imanol Pérez | 9 de agosto de 2012 | 11:30
Vótalo
0
JJGJJG, yo creo que un sobre necesita sólo 3 colores…
JJGJJG | 9 de agosto de 2012 | 12:34
Vótalo
0
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.
Alberto | 9 de agosto de 2012 | 12:48
Vótalo
0
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.
Trackback | 23 ago, 2012
Ampliación del plazo para enviar la solución del 5º desafío GyG - Gaussianos | Gaussianos
Norby | 23 de agosto de 2012 | 20:31
Vótalo
0
La Laia esa que ni siquiera ha hecho el primer año de universidad ¿como ha entrado a trabajar en el CERN?¿De limpiadora?
gaussianos | 24 de agosto de 2012 | 02:22
Vótalo
0
Norby, ¿?¿?¿?
Trackback | 21 sep, 2012
Desafío GaussianosyGuijarro nº 5 "Coloreando vértices" - Solución y ganador - Gaussianos