Mappe da colorare 1 (2)
Il Teorema dei Quattro Colori afferma che 4 colori bastano a colorare una mappa disegnata sul piano (o su una sfera) in modo tale che due regioni confinanti abbiano colori diversi. (Una "regione" non puo' essere formata da piu' parti disconnesse).
Questa proprieta' fu congetturata per la prima volta nel 1852 da un tal Francis Guthrie. (Contrariamente a quanto si potrebbe immaginare, pare che i cartografi non avessero notato questa proprieta', forse perche' poco interessati a ridurre a 4 i colori adottati in mappe e mappamondi.)
La dimostrazione di questo teorema e' stata ottenuta solo nel 1976, ad opera di due matematici americani, K.Appel e W.Haken. I due ridussero il problema generale ad un numero finito di sottocasi che analizzarono con un programma. Maggiori dettagli su questa dimostrazione che fece scalpore li potete trovare su Wikipedia o su Mathworld.
Il teorema e' valido e 4 colori bastano se conosciamo la mappa nella sua interezza. Ma cosa succede se un "avversario" ci mostra la mappa una regione alla volta e dobbiamo colorare la nuova regione senza poter cambiare il colore di quelle gia' colorate?
Se siamo molto ma molto fortunati potremmo scegliere il colore a caso e attribuire ad ogni nuova regione proprio quel colore che conduce ad una 4-colorazione globale. Ma immaginiamo un approccio piu' razionale, ovvero di colorare ogni nuova regione con il "primo" colore compatibile con i vicini (assumendo di avere in qualche modo ordinato i colori).
Quanto possono andar male le cose in questo caso, ovvero di quanti colori possiamo aver bisogno? 5? 6 o 7? Di piu'?
E' facile vedere che quattro colori non bastano piu':
Infatti, nell'esempio qui sopra siamo partiti da una regione verde. Poi ne vengono aggiunte due che non si toccano e che possiamo colorare di giallo. Poi un quarto esagono, per il quale abbiamo bisogno di un terzo colore, il rosso. E poi altre due regioni, le quali toccano tutti i colori precedentemente usati e portano il conteggio dei colori a cinque.
Non e' difficile, giocando un po' con le mappe, convincersi che se la mappa ha abbastanza regioni il nostro avversario puo' forzarci ad impiegare un numero arbitrario di colori. Qui di seguito mostro una costruzione che obbliga ad usare 6 colori e puo' essere facilmente generalizzata ad un numero qualunque di colori.
Cominciamo con 16 regioni disconnesse, per le quali abbiamo bisogno di un unico colore (la disconnessione e' in questo caso un puro fatto estestico):
Le regioni che aggiungiamo sono contigue alle prime: secondo colore.
Le regioni in rosso necessitano appunto di un terzo colore.
Aggiungiamo le regioni azzurre...
Quella verdina...
E infine un sesto colore imprecisato.
Partendo da sedici regioni e aggiungendone altre 8+4+2+1+1 = 16, abbiamo costruito una mappa con 32 regioni che necessita di 6 colori per essere colorata incrementalmente. Sarei potuto anche partire da un unica linea arancione, per poi aggiungere regioni solo sopra o sotto la linea:
E' curioso notare che le mappe con questa struttura si possono colorare con appena due colori.
Generalizzando questo semplice esempio (partendo quindi con 64, 128, 256,... regioni arancioni per forzare 7, 8, 9,... colori), e' facile mostrare che per qualunque numero k esiste una mappa con 2^(k-1) regioni che necessita di k colori.
La domanda successiva, della quale mi piacerebbe conoscere la risposta, e' quante regioni sono necessarie per forzare l'uso di un determinato numero k di colori? Infatti e' chiaro che questa classe di esempi e' piuttosto sprecona. E' facile vedere che per forzare 6 o 7 colori non c'e' bisogno di 2^5=32 o 2^6=64 regioni, ma ne bastano molte meno ... Quante? La risposta, se non la trovate, nella prossima pagina.