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.

Print Friendly, PDF & Email