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^

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.

30 Comentarios

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

    Publica una respuesta
  2. ¿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

    Publica una respuesta
  3. No me queda muy clara la 2). ¿Pregunta por el número necesario o suficente?

    Publica una respuesta
  4. Una cuestión, en el apartado 2) los segmentos añadidos pueden cruzarse entre sí?

    Publica una respuesta
  5. ¿En la pregunta 2), si los segmentos pueden cruzarse, en los cruces cuántos vértices se cuentan?

    Publica una respuesta
  6. 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.

    Publica una respuesta
  7. Pero, si no se crean vértices nuevos a partir de esas aristas, cómo aumenta el número de colores?

    Publica una respuesta
  8. 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).

    Publica una respuesta
  9. Clara Grima, bufff, me parece que eso es dar mucha pista ya, porque ya das parte de la solución del segundo apartado… jaja

    Publica una respuesta
  10. 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.

    Publica una respuesta
  11. 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.

    Publica una respuesta
  12. 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.

    Publica una respuesta
  13. 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”.

    Publica una respuesta
  14. 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

    Publica una respuesta
  15. 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.

    Publica una respuesta
  16. 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í.

    Publica una respuesta
  17. 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.

    Publica una respuesta
  18. 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.

    Publica una respuesta
  19. JJGJJG, yo creo que un sobre necesita sólo 3 colores…

    Publica una respuesta
  20. 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.

    Publica una respuesta
  21. 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.

    Publica una respuesta
  22. La Laia esa que ni siquiera ha hecho el primer año de universidad ¿como ha entrado a trabajar en el CERN?¿De limpiadora?

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Nuevo desafío de la serie Desafíos GaussianosyGuijarro (GyG), de Gaussianos y Libros Guijarro. Hoy…
  2. Ampliación del plazo para enviar la solución del 5º desafío GyG - Gaussianos | Gaussianos - [...] esta pequeña nota para informaros de que se amplía el plazo para el envío de soluciones del quinto desafío…
  3. Desafío GaussianosyGuijarro nº 5 "Coloreando vértices" - Solución y ganador - Gaussianos - [...] de un período de tiempo mayor del habitual os traigo la solución del Desafío GaussianosyGuijarro nº 5 – Coloreando…

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 *