dijous, de gener 26, 2017

El teorema dels 4 colors


Si vostè té canalla en algun moment li haurà tocat pintar el mapa de les comarques catalanes. Quants colors diferents necessita per pintar-lo? Amb un no en tindrà prou, ni amb dos tampoc. I amb tres colors? Per exemple si pintem el Pla d’Urgell de verd, la Noguera i les Garrigues les podem pintar de groc i el Segrià i l’Urgell de blau, amb tres colors en tindríem prou. I el Pla de l’Estany? Si el pintem de groc, la Garrotxa i el Gironès les hem de pintar de colors diferents perquè limiten totes entre elles, per tant ja necessitem tres colors. I quan pintem l’Alt Empordà necessitarem un altre color perquè té frontera amb les tres comarques anteriors. Necessitem quatre colors. Però en tindríem prou amb quatre colors per a pintar qualsevol mapa per recargolat que sigui? Això es preguntà fa 150 anys Francis Guthrie pintant un mapa dels comtats d’Anglaterra. Mogut per la curiositat ho comentà al seu germà, el físic Frederick Guthrie qui ho traslladà al seu profe de matemàtiques, Augustus de Morgan. Aquest no mostrà gaire interès i s’encarregà de difondre-ho a Hamilton, un altre matemàtic, i al filòsof William Whewell. El problema dels colors creuà l’Atlàntic i Charles Sanders Peirce digué que tenia una demostració... però no l’arribà a escriure.
Un altre il·lustre de les matemàtiques, Arthur Cailey, l’any 1878 el presenta a la London Mathematical Society. El problema queda obert amb l’enunciat “tot mapa pla pot pintar-se amb, com a màxim, quatre colors amb la condició que regions amb frontera comuna tinguin colors diferents”. L’any 1879 Arthur Kempe va publicar una demostració... semblava que el problema estava resolt... però l’any 1890 Percy Heawood hi trobà una errada. El problema es començà a fer molt famós i cap matemàtic aconseguia donar-ne una demostració vàlida. Fins i tot l’arquebisbe de Canterbury Frederick Temple amb il·luminació divina gosà publicar una demostració que també resultà errònia, i Lewis Carroll l’usava per plantejar enigmes matemàtics.
Al segle XX es comença a pensar en els ordinadors per trobar aquesta demostració. El matemàtic alemany Heinrich Heesch fou el pioner fent servir la programació en Algol 60. Finalment, l’any 1976 Kenneth Appel i Wolfgang Haken van anunciar oficialment que “amb 4 colors n’hi ha prou”. La demostració es feu en un ordinador IBM 360 i ocupà 1.200 hores de processament de dades (50 dies!). Tot i que hi havia molt escepticisme entre la comunitat matemàtica en el fet que una demostració no es podia fer per ordinador, cal afirmar que aquesta fou la primera prova de la conjectura. A partir d'aquí n'han sorgit més: Robertson, Sanders, Seymour i Thomas (1996), Ashay Dharwadker (2000), Werner i Gonthier (2004), Ibrahim Cahit (2006).

Fixin-se com a partir d'un problema teòricament simple com és pintar un mapa va haver 100 anys de matemàtica i matemàtics treballant en això. Però vostè es preguntarà si tot això ha servit per alguna cosa més... i tant! Gràcies a això s'ha desenvolupat l'anomenada teoria de grafs, gràcies a la qual pot llegir aquest article, té llum i gas a casa i pot fer cerques per Google.

(Article publicat al Segre Lectura el 22 de gener de 2017)