6: El mapa dels quatre colors al cel

Problema 6

A mitjans del segle XIX un jove universitari britànic es va entretenir un dia acolorint el mapa dels comtats anglesos, de manera que dos que compartissin frontera mai no fossin del mateix color. Va aconseguir amb certa facilitat fer-ho amb només quatre colors, i també va veure que amb tres era impossible.

Aleshores es va preguntar si qualsevol mapa es podria acolorir d’aquesta manera amb només quatre colors. En tots els mapes que ho va provar, ho va aconseguir, però no va trobar cap sistema per demostrar-ho.

Un mapa acolorit amb quatre colors.

El problema va arribar a les orelles dels matemàtics professionals —el primer que se’n va ocupar va ser Augustus de Morgan— que tampoc no van aconseguir la demostració.

Alguns avenços sí que es van fer: es va demostrar que no era possible que cinc regions compartissin frontera cadascuna amb les altres quatre, que amb cinc colors sempre era possible acolorir qualsevol mapa, que un mapa sobre una esfera era equivalent en aquest aspecte a qualsevol mapa pla, i fins i tot, que sobre d’altres superfícies el nombre de colors necessaris podia ser superior. Per exemple, sobre un tor —la figura en forma de pneumàtic— son possibles set regions que dos a dos comparteixin frontera i va ser possible demostrar que amb 7 colors és sempre possible acolorir qualsevol mapa pintat sobre aquesta superfície. Però l’esfera i el pla es resistien.

124 anys després es va demostrar, però no va ser una demostració “normal”, amb llapis i paper, sinó que va precisar un ordinador que comprovés totes i cadascuna d’uns milers de configuracions de regions, anomenades irreductibles, en les quals es pot transformar mantenint el problema, qualsevol configuració.

No ho hem esmentat, però quan aquí parlem d’un mapa dividit amb regions, volem dir un mapa simple: on cada zona estigui envoltada per una línia fronterera simple, no s’hi valen els “països” dividits en dues o més zones. També cal la condició que si més de tres regions conflueixen al mateix punt, es consideri que les que només entren en contacte en aquest punt, no són veïnes, o sigui que el veïnatge necessita compartir una línia, no tan sols un punt.

Dos mapes que precisen 5 colors

Sense aquestes condicions, poden caldre més de quatre colors per pintar un mapa.

Per exemple, al mapa de la dreta, imaginem que les dues zones blaves marcades A, són el mateix país; B, C i D hauran de ser de colors diferents ja que toquen A i també entre elles; però aleshores, E necessita un cinquè color, ja que té frontera comú amb A, B, C i D que ja són de quatre colors diferents.

En el mapa de la dreta, si consideréssim veïnes W i Y, i també X i Z, ja ens caldrien quatre colors per a aquestes zones; aleshores V, que les toca a totes, precisaria un cinquè color.

Aquests aclariments són necessaris pel problema que plantegem.

Fins a principis del segle XX, les constel·lacions van ser conjunts d’estrelles que d’una manera més o menys vaga recordaven un objecte, personatge o sovint animal. La seva representació sovint incloïa superposat el dibuix corresponent, encara que més modernament es va substituir per unes poques línies representatives unint les estrelles més brillants.

Però a partir de 1930 es va anomenar constel·lació a una regió del cel, limitada per línies rectes que seguien els meridians i paral·les celestes i que incloïa l’antiga configuració d’estrelles.

Es van definir 88 constel·lacions que abasten tota la volta celeste. O sigui que qualsevol punt del cels està inclòs de manera unívoca en alguna de les 88 constel·lacions grans o petites i que es pot dibuixar un mapa del cel amb les fronteres de la mateixa manera que podem dibuixar un mapa del món amb els estats —prescindim ara dels mars—.

Les 88 constel·lacions del cel en projecció mercator (si surts per la dreta del mapa entres per l’esquerra)

Podem assegurar que aquest mapa es podrà acolorir amb quatre colors?

En principi no, perquè hi ha una anomalia, una de les constel·lacions —Serpens, marcada amb la vora groga— per motius històrics està dividida en dues zones. A més, posem la condició suplementària que als quatre punts —marcats en vermell— on conflueixen quatre constel·lacions, han de ser les quatre de colors diferents.

Podeu, amb aquestes condicions, acolorir el mapa del cel amb quatre colors?

Solució 6

És perfectament factible dibuixar el mapa tot i les condicions suplementàries.
He marcat amb × les constel·lacions  que estan envoltades per altres tres que es toquen mútuament i que en conseqüència han de ser de tres colors diferents; les marcades, senzillament, s’han de pintar del quart color i no afecten la resta del mapa.
Probalement el més fàcil és començar per Serpens —la que està pintada en groc i té dos regions— i a partir d’aquella zona anar-se expandint per tot el mapa.

Una de les moltes solucions al problema

En molts pocs casos ens trobem que hi ha una zona que no podem acolorir perquè fa frontera amb quatre que ja tenen els quatre colors, aleshores cal retrocedir en el procés fins trobar un punt on hem pres la decisió d’acolorir la constel·lació que ens causa el problema posterior i escollir per a ella un color diferent. És un mètode que es pot aplicar fàcilment a mà, només cal portar un registre de l’ordre en el que anem acolorint les zones per poder fer marxa enrere si és necessari.