dissabte, d’abril 27, 2013

Kenneth Appel i el teorema dels 4 colors

No, ni l'enganyo ni em vull quedar amb vostè. És cert que existeix un teorema matemàtic anomenat "el teorema dels quatre colors", i no només existeix sinó que ha estat un dels problemes més insignes de la matemàtica de l'últim segle. Els matemàtics, tot i que no els hi sembli, són gent catxonda també.

La història comença a mitjans del s.XIX quan l'advocat i biòleg Francis Guthrie se n'adona pintant un mapa dels comtats d'Anglaterra que amb 4 colors en tenia prou. No ens preguntem què carai feia pintant un mapa.  Mogut per la curiositat li enuncia la propietat al seu germà, el físic Frederick Guthrie. Aquest optà per traslladar-lo a altes esferes matemàtiques i contactà amb Augustus de Morgan (sí, sí, el de les lleis de Morgan de la lògica). De Morgan no mostrà gaire interès pel problema aquest i s'encarregà de difondre'l a altres matemàtics. Primer li fou proposat a Hamilton, però estava massa ocupat amb els quaternions. També li proposà a William Whewell qui, com a bon filòsof, va dir que això dels 4 colors era un axioma matemàtic i punt. El problema dels 4 colors creua l'Atlàntic i el matemàtic Charles Sanders Peirce diu en un seminari que té una demostració... però no l'arriba a escriure. Imitant Fermat.

De Morgan finalment mor (com tothom) i no pot convéncer ningú per treballar en aquest problema. Però no queda del tot oblidat. Un altre il·lustre de les matemàtiques, Arthur Cailey, l'any 1878 el presenta a la London Mathematical Society. Oficialment el problema queda obert amb l'enunciat "tot mapa pla pot pintar-se amb, com a màxim, quatre colors amb la codició que regions amb frontera comú tinguin colors diferents". Bé, l'enunciat no era així, era en anglès, esclar. L'any 1979 el cantant i matemàtic Alfred Kempe va publicar un demostració del teorema... semblava que el problema estava resolt... però l'any 1890 l'excèntric Percy Heawood trobà una errada a la demostració i el problema tornava a estar obert. 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 gosa publicar una publicació que també resulta errònia, i Lewis Carroll el va fer servir per plantejar puzzles i enigmes matemàtics.

Els intents de demostració no quedaren en debades ja que a causa de la cerca de la demostració en qüestió es provà que per pintar un mapa dibuixat en un tor (donut) fan falta com a màxim 7 colors (Gerhard Ringel i Ted Youngs, 1968)  i que per a pintar un mapa dibuixat en una banda de Mobius o una ampolla de Klein calen sis colors (J.L.Saaty, 1986). També es demostrà que per un mapa pla n'hi havia prou amb 5 colors (Heawood)... però semblava que amb 4 n'hi hauria d'haver prou, no feien falta aquestos 5.

Com ja estem ben entradets en el s.XX es comença a pensar que potser els ordinadors podrien ajudar les matemàtiques en aquesta demostració. El matemàtic i músic alemany Heinrich Heesch fou el pioner fent servir la programació en Algol 60. 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à 1200 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.

Aquest escrit ha vingut a tomb a causa que m'acabo d'assabentar de la mort de Kenneth Appel als 80 anys, el primer demostrador.  

Si el tema us ha interessat podeu consultar més informació a:
-El teorema dels quatre colors a Wikipedia en castellà. L'article en català és molt pobre.
-Excel·lent PDF fet per Marta MAcho sobre la història i la resolució de la conjectura. 
-Apunt molt educatiu i pedagògic de la professora Clara Grima.
-Joc per a pintar mapes. 
-Obituari de Kenneth Appel.
-La demostració d'Appel i Haken: part I i part II.