Desafío GaussianosyGuijarro nº 5 «Coloreando vértices» – Solución y ganador

Después 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 11 eran correctas. Supongo que esta baja participación ha estado provocada principalmente por haberse publicado en verano. Pero bueno, no hay problema. A continuación recordamos el enunciado del problema y dejamos la solución de Alberto Márquez y Clara Grima, que fueron quienes lo propusieron:

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)?

Y aquí va la solución propuesta por ellos:

1) Si el polígono tiene un número par de vértices, entonces coloreando alternativamente se ve que con dos colores es posible. Por tanto, para n par la respuesta a la primera pregunta es 2.

Si tiene un número impar de vértices, es imposible colorearlos con dos colores. Coloreando de forma alternativa los vértices con dos colores vemos que el último coloreado tendría el mismo color que el primero, por lo que habría dos seguidos con el mismo color. Este último vértice habría que colorearlo con otro color, por lo que necesitaríamos 3 colores en este caso, con n impar. Ésa es la respuesta.

2) Si el polígono original tiene un número par de vértices, basta añadir una diagonal (lado extra) entre dos vértices adyacentes a uno dado. Como estos dos vértices tenían el mismo color (recordad que habíamos coloreado alternativamente con dos colores en el caso de n par), habríamos formado un triángulo en el que uno de los lados une dos vértices del mismo color, por lo que ya necesitaríamos un color más. La respuesta en este caso es, entonces, que hay que añadir un segmento más.

Si el polígono original tiene un número impar de vértices (mayor que 3, claro), se puede ver con el siguiente razonamiento que añadiendo dos diagonales no es suficiente para incrementar su número cromático (el número de colores suficientes).

Si añadimos dos diagonales cualesquiera, {a,b} y {c,d}, de esos cuatro vértices, si a es adyacente a c y d entonces b no será adyacente a ambos, así podemos decir que b y d no son adyacentes y le damos a estos dos vértices el tercer color. Ahora es trivial probar que el resto de los vértices se pueden colorear con dos dos primeros colores.

Añadiendo tres aristas entre cuatro vértices consecutivos, todos estos cuatro vértices estarían unidos entre sí, por lo tanto los colores necesarios serían 4 en este caso. Luego para el caso impar es necesario añadir 3 segmentos.

El ganador de este desafío ha sido Samuel Pascual, que pronto recibirá Quantic love. Y muchas gracias a todos por participar.

Pronto tendremos la solución del sexto desafío, para el cual todavía podéis enviar vuestra solución. Muchas gracias a todos.