Pintando mapas

Enunciado

Aunque el problema está perfectamente resuelto por Eynar en los comentarios del enunciado, quisiera añadir algo del método para trabajar estos problemas, de combinatoria, en la solución.

La idea para contar de cuántas formas se puede hacer algo, es fijar el principio y comprobar la cantidad de opciones que nos quedan.

Un ejemplo sencillo. Si en un mapa como el indicado hemos rellenado tres de las zonas con tres colores diferentes, la cuarta zona podemos llenarla de 3 formas distintas, ya que podemos usar el color en diagonal y los dos no utilizados. Esto sucederá para cualquier relleno en el que se usen tres colores diferentes, por lo que cuando tengamos el número de rellenos de esas tres zonas usando tres colores distintos, bastará multiplicarlo por 3 y tendremos de cuántas formas podremos completar el relleno.

Una vez dicho esto, procedo a copiar la solución de Eynar, que es tremendamente completa. Hay cinco formas de colorear el país de arriba a la izquierda (por ejemplo). Quedan cuatro maneras de colorear el país de arriba a la derecha (para los dos, 5*4 = 20 formas). El país de abajo a la derecha se puede colorear de cuatro formas distintas: tres de ellas son con colores que aún no se han usado, y una de ellas es empleando el mismo color que se usó para el país de arriba a la izquierda (que no está en contacto con el de abajo a la derecha), es decir, 5*4*4 = 80 formas, en 20 de las cuales se usan sólo 2 colores distintos, y en 60 se usan 3. Esto nos deja dos opciones: o bien tengo tres colores para el país restante (si los países de arriba a la izquierda y de abajo a la derecha tienen colores distintos), o bien tengo cuatro colores para dicho país restante (si los países de arriba a la izquierda y de abajo a la derecha tienen igual color). Resumiendo: existen 5*4*3*3 + 5*4*1*4 = 260 formas de colorear los cuatro países.

Otra manera de hacer el recuento, alternativa a ésta, sería la descrita a continuación. Si uso exactamente 4 de los cinco colores, dispongo de 5 opciones para el país de arriba a la izquierda, 4 para el de arriba a la derecha, 3 para el de abajo a la izquierda y 2 para el de abajo a la derecha. En total, dispongo de 5*4*3*2 = 120 formas. Si uso sólo tres colores, los dos países del mismo color pueden estar en la diagonal de arriba a la derecha, o la de arriba a la izquierda. En cada una de esas opciones tengo 5*4*3, es decir, tengo 2*60 = 120 formas más de pintar el mapa. Por último, si uso tan sólo dos colores, sólo dispongo de 5*4 = 20 formas de pintarlo, ya que los países de abajo están determinados por los de arriba, una vez elegidos los colores. En total, 120 + 120 + 20 = 260.