Per Pili Royo y Esther Barrabés.

Conjectures, innocentades i teoremes

Vet aquí un mapa de les comarques de Catalunya. Per començar, podríem mirar si recordem els noms i situació d’aquestes comarques… Però també podem deixar-ho per ara i entretenir-nos en una activitat més lúdica:

Pintem el mapa

Potser ens agradarà utilitzar molts colors i trobar una combinació que ens agradi. Tanmateix, posarem una condició que pugui  significar un petit repte:  Utilitzar el mínim nombre de colors per tal d’aconseguir que dues comarques que comparteixin una part de frontera tinguin colors diferents.  El graf de la imatge de sota simplifica la tasca, donat que ens permet limitar-nos a donar color als “vèrtexs” situats dins cada comarca, de manera tinguin colors diferents els vèrtexs units per arestes comuns.

Tres colors?; quatre colors?…

Va ser donant colors a un mapa d’Anglaterra quan Francis Guthrie es va plantejar aquesta pregunta, a la que es va intentar donar resposta al llarg dels segles XIX i XX. En un principi, ja es va dir que tot mapa pla necessita, com a màxim, quatre colors per tal que regions amb frontera comú tinguin colors diferents. Però tal resposta no deixava de ser una conjectura que calia demostrar.

Inocentada de Martin Gardner

Així, en 1975 Martin Gardner (gran divulgador de qui hem celebrat el centenari precisament el passat any 2014) va publicar un article el Dia dels Innocents (1 d’abril en el món anglosaxó) presentant el mapa de 110 regions il·lustrat a sota que, segons deia, necessitava de 5 colors, constituint per tant un contraexemple que invalidava la conjectura. Tanmateix, exemples com el presentat a continuació mostren que realment es pot aconseguir amb només 4 colors.

El teorema dels quatre colors

Però no va ser fins l’any 1976 que la conjectura es va poder demostrar. Ho van fer Kenneth Appel y Wolfgang Haken amb l’ajut de l’ordinador. Ara ja podem parlar del “Teorema dels quatre colors”, tot i que no tothom accepta que sigui lícit l’ús de l’ordinador en aquestes demostracions.

…Per acabar

A Gaussianos hi trobem més información i enllaços. A més, ens proposen un joc amb diferents nivells de dificultat, el Flood Fill, en què l’objectiu és precisament utilizar un màxim de quatre colors per acolorir diferents mapes.