I rompicapi di Alice: Mappe a colori

Non ci è dato sapere l'anno in cui Lewis Carroll concepì il seguente giochino, giunto fino a noi grazie al suo biografo, Stewart Dodgson Collingwood. Il gioco, per due giocatori, è abbastanza semplice: disegnare la mappa di una regione inesistente suddivisa in provincie; colora (o segna nel suo territorio il nome del colore) utilizzando il minor numero possibile di colori, ricordandosi di rispettare la regola che due regioni confinanti non possono avere lo stesso colore. L'obiettivo di ciascun giocatore è costringere l'altro a utilizzare più colori possibile. La domanda allora è: quanti colori il primo giocatore può obbligare il secondo a utilizzare?
Il gioco di Carroll, forse ideato nella prima metà dei 1880, è molto probabilmente ispirato alla storia del teorema dei quattro colori, che iniziò giusto un paio di decenni prima della pubblicazione di Alice nel Paese delle Mervagilie.

Una nazione a... pezze!

Nel 1852 Francis Guthrie, laureando allo University College di Londra, scrisse una lettera al fratello Frederick per proporgli un problema apparentemente semplice. Aveva sotto le mani una mappa in bianco e nero con indicate tutte le contee d'Inghilterra e, evidentemente per passare il tempo, iniziò a colorarla avendo l'accortezza di non colorare due regioni adiacenti con lo stesso colore. Aveva scoperto di essere in grado di colorare la mappa utilizzando solo quattro colori. A questo punto, come diceva qualcuno migliore di me qualche decennio fa, la domanda sorse spontanea:

E' possibile colorare qualsiasi mappa disegnata su un piano con quattro colori (o meno) in modo tale che due regioni con un confine comune non abbiano ma lo sesso colore?⁽⁵⁾

Il motivo per cui il buon Francis decise di inviare al fratello questa curiosa domanda era abbastanza semplice: Frederick era uno degli studenti di Augustus De Morgan, rinomato matematico dell'epoca, famoso in particolare per le leggi di De Morgan, un gruppo di regole fondamentali per la logica booleana.
Ad ogni buon conto neanche De Morgan fu in grado di fornire una dimostrazione al quesito, così decise di inoltrarlo con apposita lettera al suo ancora più famoso collega William Rowan Hamilton, noto in particolare per la meccanica hamiltoniana e il suo studio sui quaternioni. Il problema, però, non sembrò catturare l'attenzione di Hamilton, così nel 1854 uno dei due fratelli Guthrie, firmandosi semplicemente come F.G., inviò il quesito alla rivista The Athenaeum che lo pubblicò sul numero di giugno di quell'anno. Il quesito venne riproposto, sempre sulla stessa rivista, da De Morgan nel 1860 e ottenne lo status di teorema nel 1879 grazie ad Arthur Cayley che sulle pagine dei Proceedings of the Royal Geographical Society and Monthly Record of Geography gettò le prime basi formali al quesito, dichiarandosi però sconfitto nel suo tentativo di dimostrarlo⁽¹⁾.

Sempre nel 1879 l'avvocato Alfred Kempe, grande appassionato di matematica, disciplina in cui disponeva di un buon talento, pubblicò la prima dimostrazione del teorema⁽²⁾. La storia sembrava essersi conclusa con un lieto fine, ma l'imprevisto era dietro l'angolo: nel 1890 Percy Heawood scoprì un caso in cui le regole sviluppate da Kempe per dimostrare il teorema non funzionavano sempre⁽⁴⁾.
L'idea di Kempe, che proverò a illustrarvi, era abbastanza semplice. Partiamo da una regione particolare della mappa che dobbiamo colorare: una con tre vicini. Allora in questa sottomappa è possibile contrarre la regione scelta fino a coincidere con un punto. Le tre regioni "sopravvissute" possono essere colorate con 3 colori differenti, mentre a quella contratta, una volta riportata la regione alle sue dimensioni di partenza, si può assegnare un colore differente rispetto ai tre di partenza. Con procedimenti più complessi rispetto a quello della regione a tre vicini, Kempe riesce a ridurre anche le regioni con 4 e 5 vicini. A questo punto Kempe riesce a ridurre una mappa qualsiasi fino a una mappa con sole 3 regioni, che è quadri-colorabile e poi, con procedimento inverso, si ripristinano le regioni contratte colorandole secondo la regola di partenza che nessuna regione può avere lo stesso colore di un suo vicino. In tutto questo discorso di contrazioni e ripristini, Heawood scoprì che era proprio la contrazione di una regione con 5 vicini a generare problemi nella fase di ripristino. Questo, però, renderva la dimostrazione di Kempe utile per affermare che bastavano cinque colori per colorare una mappa, ma non si riusciva a dimostrare il passo successivo dei quattro colori.
L'anno successivo sembrò che Peter Guthrie Tait fosse riuscito a compiere quest'ultimo passo, ma ancora una volta un matematico trovò un errore nella nuova dimostrazione: era il danese Julius Petersen. Nel frattempo, sempre Tait, aveva dimostrato nel 1880 che il teorema dei quattro colori era equivalente a un particolare grafo, che oggi chiamiamo snark, che deve essere non-planare⁽³⁾. E proprio lo snark ci fa tornare, anche solo momentaneamente per una semplice pausa, alla partenza di questo Rompicapo, visto che lo snark è il nome che Carroll diede a un famigerato mostro protagonista del famoso poema The hunting of the Snark. Reso in italiano come snaulo, dello snark si conosce solo un inquietante artiglio, mostrato nell'illustrazione conclusiva di Henry Holiday per la prima edizione del 1876. In quel caso lo snark viene definito uno boojum. E' interessante notare come questo termine, inventato da Carroll, venga successivamente adottato nel campo della superfluidità. Entrambi i nomi di snark e boojum vennero adottati come termini tecnici a partire dal 1976.

Arrivano i calcolatori

La svolta nella caccia alla dimostrazione arriva nel 1922 grazie a Philip Franklin, che dimostrò che tutte le mappe con 26 regioni o meno possono essere colorate utilizzando solo 4 colori. Il punto forte del lavolo di Franklin, quello per cui può essere indicato come un prezioso avanzamento nella caccia alla dimostrazione, è nell'aver introdotto il concetto di cofigurazione riducibile. Una configurazione è un qualunque insieme connesso di regioni della mappa insieme con le informazioni sulle regioni confinanti. Un esempio di configurazione è la regione con tre vicini di Kempe. E questa è anche una configurazione riducibile, essendo quadri-colorabile. Questo vuol dire che tutte le configurazioni riducibili a questa configurazione sono a loro volta riducibili, ovvero (semplificando) quadri-colorabili. Il problema nel quale incappò Kempe è che non tutte le regioni con cinque vicini sono riducibili. Ad ogni buon conto il lavoro di Franklin permise di spostare la ricerca della dimostrazione su un'ottica diversa: quella di determinare le configurazioni riducibili.
Da un calcolo a spanne, però, l'impresa sembrava improba: Heinrich Heesch nel 1950 aveva calcolato che un insieme inevitabile di configurazioni riducibili che avrebbero permesso di dimostrare il teorema dei quattro colori era costituito da ben 10000 configurazioni di questo genere. Urgeva, allora, un metodo per rendere più rapida e agevole tale ricerca.
Fu lo stesso Heesch che diede il via ai primi tentativi di utilizzo dei nascenti calcolatori elettronici, ma con il miglioramento della tecnologia, anche le possibilità di calcolo migliorarono, ma non così tanto da risolvere il problema in un tempo umano: con i calcolatori in uso negli anni Settanta del XX secolo ci sarebbe voluto all'incirca un secolo. Questo spinse Wolfgang Haken e il suo collaboratore Kenneth Appel a ridurre l'insieme inevitabile, arrivando a 2000 elementi. Alla fine furono proprio loro due a portare a conclusione la dimostrazione del teorema dei quattro colori utilizzando i computer: era il 1976 e, a parte tutta la storia successiva sulle verifiche della dimostrazione, non è ancora stata trovata una dimostrazione formale del teorema⁽⁵⁾.

---

1. Cayley, P. (1879, April). On the colouring of maps. In Proceedings of the Royal Geographical Society and Monthly Record of Geography (Vol. 1, No. 4, pp. 259-261). Blackwell Publishing; The Royal Geographical Society (with the Institute of British Geographers). doi:10.2307/1799998 ↩
2. Kempe, A. B. (1879). On the geographical problem of the four colours. American Journal of Mathematics, 2(3), 193-200. doi:10.2307/2369235 (archive.org) ↩
3. Tait, P. G. (1880), Remarks on the colourings of maps, Proc. R. Soc. Edinburgh, 10: 729, doi:10.1017/S0370164600044643 ↩
4. Heawood, P. J. (1890), Map-Colour Theorem, Quarterly Journal of Mathematics, Oxford, 24, pp. 332–338 ↩
5. Ian Stewart, La piccola bottega delle curiosità matematiche del professor Stewart, La biblioteca delle Scienze, 2010, trad. Daniele A. Gewurz ↩↩