domingo, 17 de enero de 2016

Formas de colorear un polígono

Enunciado

Se trata de construir una fórmula, y es casi un trabajo de investigación matemática, por lo que me parece muy complejo.

Lo más lógico es estudiar completamente un caso sencillo, luego un caso un poco más complejo, y luego empezar ya a efectuar hipótesis, para luego comprobarlas.

Empezamos a colorear los vértices de un triángulo (n = 3) sin atender a si sus lados cumplen o no la condición y luego clasificarlos. Como cada vértice puede tener un color entre tres, se presentan 3x3x3 = 27 casos. Llamaré a los colores A, B y C. Los casos son: AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC.

De estos, observamos que hay tres casos en los que ningún lado tiene colores diferentes, que no está contemplado en el problema (AAA, BBB y CCC), y de los 24 casos restantes, 18 tienen dos lados con colores diferentes (m = 2) (AAB, AAC, ABA, ABB, ACA, ACC, BAA, BAB, BBA, BBC, BCB, BCC, CAA, CAC, CBB, CBC, CCA y CCB) y 6 tienen los tres lados con colores diferentes (ABC, ACB, BAC, BCA, CAB y CBA). Observa que los lados están entre dos de los vértices (letras), y que la última letra tiene un lado que la une a la primera.

El siguiente caso completo (n = 4) tiene 81 elementos y puede llevar mucho tiempo clasificarlos, así que debemos descartarlo de momento y tratar de contar directamente un caso particular que nos ilumine mejor la forma de contar esta cantidad.

Vamos a estudiar, por ejemplo, el caso n = 7 y m = 4, es decir, un heptágono en el que exactamente cuatro lados tienen extremos de colores diferentes. Si queremos poner un ejemplo, lo primero que haremos será situar qué lados vamos a elegir, por ejemplo, el segundo, el tercero, el quinto y el séptimo. Eso conlleva que el primer y segundo vértice tienen el mismo color, el tercero lo tendrá diferente del segundo, el cuarto diferente del tercero, el quinto igual que el cuarto, el sexto diferente, y el séptimo igual que el sexto pero diferente del primero. En el dibujo, he rodeado con una elipse los vértices que deben ser del mismo color. De esta forma, en realidad sólo debo elegir cuatro colores diferentes a sus vecinos, y los otros tres se colorearán de forma automática. Por ejemplo, puedo elegir AABCCBB.

Entonces, si quiero contar la cantidad de formas en la que puedo hacer esto, se trata de elegir cuatro colores por un lado con la condición de ser diferentes de sus vecinos, y los cuatro lados que quiero que tengan la condición pedida. Por lo menos puedo estudiar por separado ambas elecciones.

El número de elecciones de los lados es un sistema más estudiado. Para el otro habrá que improvisar bastante.

Si has estudiado combinatoria, reconocerás que elegir cuatro lados entre 7 se llama combinaciones de cuatro elementos escogidos entre 7, y sabrás como calcularlos. En el siguiente párrafo razono la cantidad para aquellos que no tengan este concepto.

El primer lado lo selecciono entre 7 posibilidades, el segundo entre los 6 restantes, y así sucesivamente, de forma que tendría, en principio, 7*4*3*2 formas de elegir los cuatro, pero cada elección la estaría contando muchas veces. En efecto, una elección de 4 lado estaría contándola una vez por cada lado que tomara como primer lado (4), multiplicada por una vez cada vez que contara otro como segundo, y así sucesivamente, es decir, la estaría contando 4*3*2*1 veces. Por tanto, el número total de formas diferentes de elegir sería (7*6*5*4)/(4*3*2*1), en total en nuestro ejemplo eso da 35 formas diferentes.

Puede que conozcas la fórmula para este cálculo, es n!/(m!*(n-m)!).

Ahora, debemos elegir los cuatro colores diferentes, es decir, ver de cuantas formas lo podemos hacer. Para el primer color disponemos de 3 posibilidades, pero para el segundo sólo 2, para el tercero otros 2, y el cuarto es mucho más complejo, ya que depende de si el primer y el tercero son iguales o diferentes. Si son iguales, tendré dos formas diferentes de lograrlo, y si son diferentes, sólo una. Para esto, podemos partir del estudio que hemos hecho antes, para el triángulo. Había exactamente 6 casos en que todos los colores eran diferentes cada uno del siguiente, que derivarán en una única elección para el cuarto color. Si el primero y el tercero son iguales sólo eliges dos colores realmente diferentes antes de elegir el cuarto (3*2 posibilidades) y entonces tienes otras 2 de elegir el último, lo que hace un total de 12 posibilidades, es decir, tenemos 18 formas de elegir los colores.

Al final, tendremos 18*35 = 630 coloraciones diferentes para el heptágono con cuatro lados de diferente color en los extremos. No las voy a poner todas, desde luego.

La elección de los lados es sencilla de convertir en una fórmula, pero la selección de colores no. Tendremos que estudiarla más a fondo. Hay que calcular de cuántas formas se pueden conseguir elegir un cierto número de colores entre tres, diferentes cada uno del siguiente y el primero del último.

Además, tendremos que hacerlo a partir de 2. Para 2 son 6 las formas de hacerlo, para 3 ya sabemos que 6 también, y para 4 hemos visto que 18. Veamos para 5 y creemos una fórmula.

Si queremos escoger una cadena de 5 colores con esa condición, podemos partir de las anteriores. Si tomamos una cadena de 4 diferentes (18 formas) y añadimos un color diferente del primero y el último tendremos 18 formas diferentes, las 18 en las que el penúltimo y el primero son distintos. Para las restantes, como sabemos que primero y penúltimo han de ser iguales, partimos de una cadena de 3 diferentes (6 formas), añadimos otra igual que el primero (podemos, porque el tercero es diferente del primero), y luego disponemos de dos posibilidades para el último color, es decir, que tendremos 6*2 = 12 formas más, hasta un total de 30.

Observa que hemos calculado el valor para la cuarta elección a partir de la tercera y la segunda. De ahí se puede sacar una primera fórmula que nos ayude, que sería inductiva (a partir de los números previos). Se trataría de tomar la anterior y sumarle el doble de la anterior de la anterior. Es decir, Cm = Cm - 1 + 2 Cm - 2.

La secuencia vendría a ser 6, 6, 18, 30, 66, 126, ...

Si nos fijamos bien, se parece enormemente a las potencias de 2 (4, 8, 16, 32, 64, 128, ...), sólo que se le suma o resta 2. Esa fórmula se podría poner como 2m + 2*(-1)m.

Para comprobar que es válida, lo demostramos por inducción, ya que 2m - 1 + 2*(-1)m - 1 + 2*(2m - 2 + 2*(-1)m - 2) = 2m - 1 + 2*(-1)m - 1 + 2m - 1 + 4*(-1)m = 2m - 2*(-1)m + 4*(-1)m = 2m + 2*(-1)m, como se quería demostrar.

Por lo tanto, la fórmula para la cantidad de formas de elegir los colores con esa condición, para n y m genéricos, es (n!*(2m + 2*(-1)m))/(m!*(n-m)!).

Como veis, un problema muy largo y complejo para cerrar la olimpiada.

6 comentarios:

Guillermo Fernández dijo...

Hola, no se supone que hay que utilizar siempre los 3 colores?

Proble Mático dijo...

En realidad el enunciado no lo indica claramente, pero en el caso de incluir la necesidad de utilizar siempre los dos colores (porque hacemos esa interpretación), podemos completar el problema eliminando de la cuenta aquellos casos en los que la coloración con dos colores sea posible.

Observa que no es posible si la diferencia n - m es impar. En ese caso, el valor será el mismo.

Si es par, debemos quitar dos posibilidades por tres colores (un total de seis combinaciones) multiplicado por el número de elecciones de las aristas.

Guillermo Fernández dijo...

Gracias, he mirado con atención la resolución y efectivamente se contempla que se utilizan los 3 colores. En general, estoy de acuerdo con el procedimiento, yo había pensado en lo mismo pero sin llegar a un resultado concluyente.

No obstante... ¿no habría que dividir el resultado final por "n"? Como estamos hablando de polígonos cerrados, finalmente habría que constatar que las configuraciones que se han calculado están agrupadas en clases de equivalencia de "n" elementos. Algo análogo a cuando se calcula el número de permutaciones circulares, para entendernos.

Proble Mático dijo...

Es problemático. Siempre me ha parecido lo de la geometría combinatoria muy complejo, debido a estas trampas.

Algunas combinaciones no se cuentan n veces.

Por ejemplo, supongamos un polígono de 6 lados.

A-B-B-A-B-B tiene una de las 6 rotaciones que coincide con ella misma, pero A-B-B-B-A-B no, y se cuentan como n = 6 y m = 4 ambas. Incluso tienen dos colores.

Guillermo Fernández dijo...

Es verdad, hay clases de equivalencia pero no todas tienen por qué tener el mismo número de elementos. Así que mejor no considerar esa cuestión, eso ya hace el problema directamente impracticable.

Por otra parte, definiendo c(m) como el número de maneras de colorear con 3 colores (utilizando necesariamente los 3) los vértices de un polígono de m lados, sin que dos vértices consecutivos tengan el mismo color, deduzco otra ecuación en diferencias:

c(m)=3*2^(m-2)+c(m-2),

con c(3)=6, c(4)=12. Esto arroja que c(m)=-3+2^m-(-1)^m. He comprobado que es correcto calculando con diagramas de árbol todas las configuraciones, desde el caso m=3 hasta el caso m=8. Así que me inclino por la solución

C(n,m)*(-3+2^m-(-1)^m).

Nótese que para m=2 el resultado es 0, y es que efectivamente no hay manera de colorear un polígono de n lados utilizando 3 colores y de forma que exactamente 2 lados tengan extremos diferentes.

Guillermo Fernández dijo...

Vale, y tu solución es en el caso de que puedan utilizarse los 3 colores, o 2 de ellos. Comprobado, ya lo tengo todo claro.

Supongo que ambas interpretaciones son válidas. Un cordial saludo.