jueves, 27 de septiembre de 2012

Coloreando vértices

Aquí os dejo la solución que mandé al Desafío nº5 de Gaussianos.com

Dado que preguntaban por los errores que habíamos cometido algunos en nuestras soluciones, aquí podéis comprobar el mío.

En concreto, se pedía en el 2º apartado: ¿Cuántos segmentos que unan dos vértices de un polígono se han de añadir (de alguna forma concreta a determinar) a dicho polígono (dejaría de serlo) para (asegurar) que necesitemos más colores de los obtenidos en 1)?
Y yo lo interpreté como: ¿Cuántos segmentos que unan dos vértices de un polígono se han de añadir (de cualquier forma) a dicho polígono (dejaría de serlo) para (asegurar) que necesitemos más colores de los obtenidos en 1)?

La verdad es que no presté atención a las explicaciones que se dieron en los comentarios, y malinterpreté el enunciado. Aunque para ser sincero, creo que lo que yo resolví es aún más interesante, aunque por supuesto erróneo. El primer paso en un problema consiste en entender que se pide, así que a partir de ahí todo lo que hice no vale. Pero ... siempre está bien ver alguna variación.

Pondré un par de ejemplos para mejor comprensión:
  • Si tenemos un cuadrado, hacen falta 2 colores, y 1 sólo segmento más para obligar a usar 3 colores.
  • Si tenemos un pentágono, hacen falta 3 colores, y según mi solución harían falta 4 segmentos más para que los pongas como los pongas hagan falta 4 colores. Sin embargo, en la solución correcta para el pentágono bastarían 3 segmentos.

----------
Esta fue mi solución:

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? 

Llamamos ‘c’ al número de colores necesarios.

  • Caso par: Si n = 2p , con p € Nc = 2
 
Los n vértices se pueden ordenar de forma consecutiva partiendo de uno cualquiera al que le asignamos el ‘1’ y numerando el siguiente de forma ordenada siguiendo las agujas del reloj arista por arista.

Dado que n es par, el primero es impar (es el ‘1’) y el último es par (es el n = 2p), bastan 2 colores para colorear los vértices pares e impares.

Sólo existe una distribución posible con 2 colores: ( p, p ) es decir, ‘p’ vértices de un color y ‘p’ de otro.

  • Caso impar: Si n = 2p + 1 , con p € Nc = 3
 
Ordenando los n vértices de la misma forma que antes, llegamos a la ordenación de pares e impares, pero en este caso la última arista uniría dos vértices impares. Por tanto no es posible usar sólo 2 colores.

Podemos colorear los ‘p’ primeros impares de un color, y los ‘p’ primeros pares de otro color, mientras que el vértice 2p+1 será de un tercer color

En este caso existe más de una distribución posibles con 3 colores: ( a , b , n-a-b )  

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

Llamamos ‘s’ el número de segmentos necesarios.

  • Caso par: Si n = 2p , con p € Nc = 2

Teníamos una única distribución de colores ( p , p )

El número total de uniones entre vértices de distinto color es p2

El número de uniones del polígono original es 2p

Por tanto el número necesario de segmentos será s = ( p2 ) – ( 2p ) +1 = ( p – 1 )2

Si n = 2p entonces s = ( n/2 – 1 )2

  • Caso impar múltiplo de 3: Si n = 2p + 1 = 3q , con p,q € Nc = 3
 
Teníamos varias distribuciones posibles de colores ( a , b , n-a-b )

El número total de uniones entre vértices de distinto color es ab + a(n-a-b) + b(n-a-b)

El número de uniones del polígono original es 2p+1

Por tanto el número necesario de segmentos será s = ( ab + an – a2 – ab + bn – ab – b2 ) – ( 2p + 1 ) + 1 = an + bn – ab – a2 – b2 – n + 1

Derivando respecto a ‘a’ y ‘b’ e igualando a 0, obtenemos:

n – b – 2a = 0
n – a – 2b = 0

Y se obtiene la solución a = b = n/3

Es decir, la distribución de colores ( n/3 , n/3, n/3 )

Las derivadas segundas respecto a ‘aa’, ‘ab’ y ‘bb’ son: -2, -1, -2

D = (-2) * (-2) – (-1)2 = 3 > 0

Dado que D > 0 y la derivada segunda respecto a ‘a’ es < 0 tenemos que la solución obtenida es un máximo. (El máximo nos garantiza el mínimo número de segmentos paracualquier distribución de colores que puedo escoger).

Si n = 2p + 1 = 3q entonces el valor de s = ( n2 – 3n + 3 ) / 3

Caso impar no múltiplo de 3:

Si n = 2p + 1 = 3q 1 , con p,q c = 3 

Razonando de la misma forma que antes llegamos a la misma solución, pero n/3 no es un valor entero, por lo que la distribución de colores sería ( a , a , b ) = ( a , a , n-2a ). 
Viendo las derivadas de s se observa que es convexa y existe un único máximo, y dado que la solución no puede escogerse no entera, la solución será el punto más próximo.

En la figura se observa un ejemplo gráfico que representa el número de segmentos en función de las distintas distribuciones para n=19, donde se observa que la gráfica es convexa. El número total de uniones entre vértices de distinto color es a2 + 2ab

El número de uniones del polígono original es 2p+1

Por tanto el número necesario de segmentos será s = ( a2 + 2ab ) – ( 2p + 1 ) + 1 = a2 + 2ab – n + 1

Si n = 3q + 1 entonces a = (n-1)/3 y b = a+1 Entonces s = ( n2 – 3n + 2 ) / 3

Y si n = 3q – 1 entonces a = ( n+1 )/3 y b = a – 1

Entonces s = ( n2 – 3n + 2 ) / 3, igual que antes

Si n = 2p + 1 = 3q+-1 entonces el valor de s = ( n2 – 3n + 2 ) / 3

No hay comentarios:

Publicar un comentario

Adelante! Deja tu comentario: