1. Homepage
  2. Laboratorio di informatica
  3. Quattro colori, un computer e un pesce d'aprile

Quattro colori, un computer e un pesce d'aprile

Quattro colori, un computer e un pesce d'aprile

Una mattina di aprile del 1975 i lettori di Scientific American si trovarono davanti una notizia straordinaria. Martin Gardner, matematico e divulgatore di fama, autore della storica rubrica Mathematical games, firmava un articolo intitolato Sei sensazionali scoperte per diversi motivi sfuggite all'attenzione del pubblico. Tra le sensazionali scoperte figurava nientemeno che un controesempio - o almeno, così sembrava - della congettura dei quattro colori, problema aperto da oltre un secolo. Nel giro di un altro anno la stessa congettura avrebbe spaccato la comunità dei matematici in un dibattito accesissimo sul concetto stesso di dimostrazione, ma quel giorno Gardner, in mezza paginetta, infrangeva i loro sogni affermando che era, semplicemente, falsa.L’enunciato è facile quanto la dimostrazione è difficile. Immaginate di dover colorare una cartina politica, una qualunque: la vostra regione divisa in province, l’Italia in regioni, la Germania in land, il planisfero in stati. Ma anche, più semplicemente, di voler dipingere una tovaglia a fiori o qualsiasi disegno su un piano. Avete una sola regola: due aree adiacenti1 non devono mai avere lo stesso colore. Con quanti colori sarete sicuri che, qualunque sia la mappa, potrete colorarla tutta? Quattro, diceva la congettura: con quattro colori potrete colorare qualsiasi mappa.

Al momento della pubblicazione dell’articolo di Gardner era già stato dimostrato che tre colori non sempre sono sufficienti (questo è facile) e cinque sì (difficile): mancava l’ultimo passaggio (difficilissimo). E invece ecco che Gardner, come se niente fosse, riportava una complicata mappa costruita dal teorico dei grafi William McGregor che - scriveva - richiedeva necessariamente cinque colori. Se la maggior parte dei lettori di Scientific American avrà probabilmente reagito con moderata curiosità, per i matematici che quel mattino sfogliarono la rivista possiamo immaginare un bel numero di caffè andati di traverso. Alla sfida irrisolta dei quattro colori avevano partecipato con più o meno successo matematici di grande spessore. Nonostante una dimostrazione ancora non esistesse, quasi tutti gli esperti ritenevano che la congettura dovesse essere vera. Quel controesempio, che così innocentemente Gardner esponeva tra altre notizie, faceva crollare ogni tentativo. Chi aveva ragione?

Il problema dei quattro colori emerse per la prima volta nel 1852. Il matematico Francis Guthrie, realizzando una cartina dell’Inghilterra, si rese conto che, volendo usare colori diversi per contee vicine, i colori necessari erano quattro: non più, non meno.Ma perché? Lo chiese a suo fratello Frederick, allora studente allo University College di Londra, che a sua volta ne parlò con il suo professore Augustus De Morgan, celebre logico e matematico, il quale rese pubblico il quesito nel 1860. Da allora fino al giorno dell’articoletto di Gardner, il contributo più importante alla soluzione del problema si deve al matematico britannico Alfred Kempe, che nel 1879 propose una dimostrazione completa del problema che resse per 11 anni: poi saltò fuori che il suo ragionamento conteneva un errore. Gran parte della strategia si salvava, ma quell’errore non si riusciva ad aggirare. Il mattino in cui Scientific American spezzò il cuore dei suoi lettori matematici, pochi passi avanti erano stati fatti rispetto ai tempi di Kempe. Per fortuna la delusione durò poco: giusto il tempo di rendersi conto che era il 1° aprile. La notizia era uno scherzo che Martin Gardner, reo confesso, si era divertito a escogitare con la complicità di William McGregor. Quattro colori infatti bastavano anche per la sua cervellotica mappa: quella di Gardner fu insomma una boutade, ma la congettura dei quattro colori - era ancora solo una congettura - di lì a poco sarebbe diventata famosa per motivi profondi. 

Quella di Kempe era una dimostrazione per assurdo: supponiamo che esista una mappa che richiede almeno cinque colori e troviamo una contraddizione. Tutto ciò funzionava per certi tipi di mappe, ma non per tutte le mappe possibili. Le ipotetiche mappe che richiedessero cinque colori erano semplicemente troppe perché si potesse controllarle una per una e giungere a una contraddizione. All’inizio degli anni Settanta Kenneth Appel e Wolfgang Haken dell’università dell’Illinois iniziarono a immaginare che questa gigantesca mole di lavoro potesse diventare affrontabile grazie all’uso di un computer. Fu un cammino lungo e pieno di ostacoli: non si trattava di dare in pasto alla macchina poche semplici istruzioni, ma di elaborare un immenso impianto teorico e poi sfruttare la potenza di calcolo del computer anche solo per capire quali domande fargli. Dopo sei anni di lavoro e oltre mille ore di calcolo con tre dei computer dell’università dell’Illinois, Appel e Haken riuscirono prima a stilare una lista completa delle 1482 possibili configurazioni di una (ipotetica) mappa che richiedesse cinque colori, e poi a escludere che ognuna di queste 1482 configurazioni potesse dare effettivamente luogo a una tale mappa. La congettura dei quattro colori dunque era vera: non più una congettura, ma un teorema.Molti matematici però accolsero con freddezza il lavoro di Appel e Haken. Se siamo certi che un’affermazione è vera, significa che l’abbiamo dimostrata? Questo è precisamente il nodo della questione. Non solo quella dimostrazione non era verificabile da un essere umano, ma il fatto di dover controllare tutti i 1482 casi con la “forza bruta” - cioè uno per uno, senza un ragionamento unificante - era come sapere che la congettura era vera senza sapere, in fondo, perché. Oggi molte cose sono cambiate e l’uso dei computer nella matematica è all’ordine del giorno in modi che negli anni Settanta non si sarebbero nemmeno potuti immaginare: per esempio si usano per controllare la correttezza formale di dimostrazioni troppo complesse perché una persona in carne e ossa possa padroneggiarle. Ma ogni matematico continua ad avere una sua idea della bellezza di una dimostrazione: avremo mai una dimostrazione “bella” del teorema dei quattro colori?

La strategia di Alfred Kempe

  1. Supponiamo che esista una mappa M che richiede almeno 5 colori. Chiamiamo normale una mappa in cui nessuna regione è del tutto contenuta in un’altra e non ci sono punti in cui si incontrano più di 3 regioni.
  2. Se esiste una mappa M che richiede almeno 5 colori, allora esiste anche una mappa normale che richiede almeno 5 colori. Possiamo dunque supporre che M sia normale.
  3. Scegliamo M in modo che sia anche minimale, cioè contenga il minor numero di regioni per cui servano 5 colori.
  4. In ogni mappa normale c’è almeno una regione R che è adiacente a non più di 5 regioni.
  5. Scegliamo R nella nostra mappa M normale e minimale. Supponiamo che R confini:
    ● con 2, 3 o 4 regioni → si dimostra che M non è minimale → contraddizione → per colorare M non servono 5 colori
    ● con 5 regioni → ERRORE


    La strategia di Kenneth Appel e Wolfgang Haken

  6. Ogni possibile mappa in cui R confini con 5 regioni appartiene a una di 1482 possibili configurazioni.
  7. per ognuna di quelle configurazioni M non è minimale → contraddizione → per colorare M non servono 5 colori → il teorema dei quattro colori è dimostrato.

Note


1 Che abbiano in comune un tratto di confine. Il teorema non vale se consideriamo adiacenti aree che si incontrano soltanto in punti isolati e se esistono regioni non connesse, cioè aree che pur composte di più parti disgiunte (come l’Alaska e il resto degli Stati Uniti) devono avere lo stesso colore.Fonti*

Come si fa una presentazione
Guida ai podcast
Come fare un'escape room didattica