Antoni Liz / Ciutadella – Quants colors són necessaris per pintar un mapa de manera que no hi ha dues regions amb frontera comuna del mateix color?
El 1840 Möbius proposava el problema nombre 1. (Per pensar-hi una estona)
Si provam de pintar alguns mapes podrem trobar mapes de es poden pintar amb 2, 3, o 4 colors. Podrien ser necessaris 5 colors per algun mapa?
CONJECTURA
Es va proposar que 4 colors podrien bastar per pintar qualsevol mapa de manera que dues regions amb frontera comuna tinguin diferent color.
Una frontera ha de ser una línia, no pot ser un punt.
Una regió no pot estar dividida en dues zones inconexes.
Una regió no pot englobar una o més regions.
S’enten que açò és un mapa «normal».
Es tractava de demostrar que aquesta conjectura és certa o de trobar un contraexemple de mapa que necesita 5 colors.
Només podrem veure alguns detalls d’aquest problema.
La història de la demostració es pot resumir així:
1852: Francis Guthrie planteja el problema al seu germà Frederick i aquest a Augustus de Morgan.
1878: Arthur Cayley publica l’enunciat de la conjectura.
1879: Sir Alfred Bray Kempe publica una «demostració».
1890: Percy Heawood descubreix una errada en la demostració de Kempe.
1913: George Birkhoff introdueix la noció de configuració reduïble.
1960: S’introduce l’anomenat métode de descàrrega.
1969: Heinrich Heesch aplica reduccions i obté 1936 configuracions.
1976: Ken Appel y Wolfgang Haken redueixen les configuracions a 1.482 i amb ordinador compreven que 4 colors són suficients.
1996: N. Robertson, D.P. Sanders, P. Seymour y R. Thomas redueixen les configuracions a 633 i milloren la comprovació.
2004: Benjamin Werner i Georges Gonthier verifiquen la prova de 1996 amb un altre programa Coq 7.3.1.
Moltes regions poden coincidir en un punt però no tenen línia de frontera.
Aquesta figura mostra que cada regió està en contacte amb altres 3 però s’ha de pintar amb 4 colors.
De Morgan va demostrar que no és possible que 5 regions tenguin cada una d’elles 4 veïnes i va pensar que açò ja demostrava la conjectura però no és així. Cada regió podria tenir només 4 veïnes però necessitar 5 colors per pintar-les.
La demostració de Kempe tenia moltes etapes correctes i només una errada en aquest sentit.
Kempe va aplicar als mapes la fórmula d’Euler dels poliedres.
Cares + Vèrtex = Aristes + 2
C + V = A + 2
Per a mapes la fórmula quedava
Regions + Punts = Fronteres + 2
6 + 8 = 12 +2
Aquest exemple seria un mapa originat a partir d’un cub. Al nombre de regions hem de comptar la regió exterior. Cub de 6 cares = Mapa de 6 regions (5 + exterior).
Kempe va demostrar correctament que en qualsevol mapa trobariem una d’aquestes 4 figures.
Heawood va trobar que quan es presentava la darrera figura (amb un pentàgon) la demostració de Kempe fallava.
De cada mapa es treu la configuració en forma de «graf».
El 1976 Appel i Haken van reduïr les configuracions a 1482 i amb ordinador van comprovar que les múltiples maneres de colorejar cada una de les configuracions només requerien 4 colors. L’article va sortir a «Investigación y Ciencia» n. 15. de desembre de 1977.
Després s’han fet altres reduccions i millores en la demostració però podem dir que el 1976 es va demostrar la conjectura. (més de 100 anys d’estudis i emprant ordinador!).
Ha resultat que açò de pintar mapes no és «només» cosa de fillets.
