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.