Mappe, pittori poveri e il problema dei quattro colori

ricerca fisica scienze tecnologie chimica
history 3 minuti di lettura

Un pittore povero è un pittore che non si può permettere di acquistare tanti colori, e Percy Heawood era molto povero, per cui cinque colori differenti gli sarebbero dovuti bastare per eseguire il compito che un ricco signore gli aveva commissionato: colorare una mappa geografica in modo tale che due regioni confinanti non avessero lo stesso colore. Ma Heawood era tranquillo, perché aveva dimostrato, usando la Teoria dei grafi, che questa cosa sarebbe stata sempre possibile, qualsiasi fosse la mappa [1], usando solo cinque colori.

Nel 1890 Heawood era riuscito a dimostrare questo teorema correggendo una dimostrazione fatta da un altro matematico, Kempe, che era erroneamente ritenuta esatta, addirittura per quattro soli colori: Heawood dimostrò il teorema correttamente, alzando però il limite a cinque. Per molti anni i matematici si lambiccarono il cervello per trovare una soluzione al problema dei quattro colori, perché Kempe li aveva fatti innamorare dell’idea di usarne solo quattro. E Heawood stesso provò a dimostrarlo con soli quattro colori, senza però riuscirci.
La dimostrazione usata da Kempe e poi migliorata da Heawood faceva uso di alcune tecniche di teoria dei grafi che permettevano di ridurre la complessità di una mappa qualsiasi in una con, al massimo, cinque zone, per cui la dimostrazione era anche abbastanza semplice. Ma di scendere a quattro colori proprio non gli riuscì.
E non riuscì neanche a tutti i matematici che provarono a dimostrare la congettura di Kempe [2]: fino al 1976, quando intervennero due informatici appassionati di matematica, Kenneth Appel e Wolfgang Haken, che usarono, per la prima volta nella storia della matematica, un software per la dimostrazione della sufficienza di quattro colori.

Si potrebbero riempire intere enciclopedie per spiegare come i matematici ragionano e se è lecito usare strumenti differenti dalla mente umana per realizzare una dimostrazione: basti pensare al fatto che un software non è nient’altro che l’implementazione di un algoritmo (cioè la sua realizzazione), che è a tutti gli effetti una dimostrazione, per tranquillizzarci sulla liceità di questa affermazione. Gödel, nei suoi Teoremi di incompletezza, ci ha insegnato che l’uso di tecniche (che tra l’altro poteva solo immaginare nel 1931, perché non esistevano ancora) meccanicodeterministiche per la soluzione di un problema è l’unico corretto, e nonostante questo esistono anche delle affermazioni vere ma non dimostrabili.

Stiano pur tranquilli i pittori poveri: bastano 4 colori per colorare una mappa senza che due regioni adiacenti siano colorate con lo stesso colore! È un po’ più difficile la dimostrazione di Appel e Haken, visto che l’infinità di mappe viene prima ridotta a 1936, poi 1476, configurazioni diverse: un numero alto ma pur sempre finito, per cui il metodo è valido! La stampa di tutte le possibili configurazioni occupa più di 500 pagine, che sono state puntualmente controllate una ad una da uno stuolo di matematici.
Adesso esistono dei programmi scritti in Prolog di poche decine di istruzioni che permettono di colorare una mappa con soli quattro colori: se ne trovano a iosa sul web. L’importante è sapere che quattro colori sono sufficienti! Ah, se Heawood avesse avuto la possibilità di usare le tecniche di Intelligenza Artificiale che usiamo oggi, chissà cosa avrebbe saputo dimostrare!
Enrico Cirillo

[1] I matematici usano delle parole tremende e definitive: “qualsiasi mappa” significa proprio “tutte le mappe, nessuna
esclusa”: quindi anche mappe immaginate, complicate a piacimento. L’importante è che la mappa da colorare sia
rappresentabile come una mappa, cioè su un foglio a due dimensioni senza zone sovrapposte né sconnesse.
[2] La congettura è un’affermazione matematica che è verosimile, ma per la quale non esistono dimostrazioni. Una
volta dimostrata, la congettura diventa teorema. L’esempio più famoso è la congettura nota come “Ultimo Teorema
di Fermat”, che era chiamato erroneamente Teorema fino alla sua dimostrazione definitiva fatta nel 1994 da Wiles

newsletter mentinfugaIscriviti alla newsletter

-----------------------------

Se sei giunto fin qui vuol dire che l'articolo potrebbe esserti piacuto.
Usiamo i social in maniera costruttiva.
Condivi l'articolo.
Condivi la cultura.
Grazie

Temi relativi all’articolo: