lunedì 15 dicembre 2014

Complesse rotazioni

“Ma quindi come si risolveva il problema del tesoro nascosto? Cosa c'entrano i numeri complessi?”.

“Eh, coi numeri complessi si può risolvere il gioco in modo molto elegante”.

“Ma perché proprio i numeri complessi? Mi sembra un problema di geometria”.

“Certo, e proprio per questo i numeri complessi sono utili”.

“Ma se non c'entrano niente con la geometria!”.

“Qui ti sbagli, c'entrano eccome. Per capire il perché bisogna fare un passo indietro, ai numeri negativi”.

“Tipo −1, −2, −3?”.

“Sì. A dir la verità, ci basta −1. ”.

“Boh, continuo a non capire cosa c'entri la geometria”.

“Prendi un numero qualsiasi, positivo. Per esempio 3”.

“Va bene. Che ci faccio?”.

“Rappresentalo su una retta”.

“E fin qua è facile”.

“Ora moltiplicalo per −1”.

“Diventa −3”.

“Bene, ora ti faccio un disegno”.



“Bè? Cosa vuoi dire? Che c'entra la geometria perché moltiplicando per −1 hai spostato un punto da una parte a quell'altra? Mi sembra banale”.

“Diciamo, più precisamente, che ho ruotato il segmento che va da 0 a 3 e l'ho sovrapposto a quello che va da 0 a −3”.

“Possiamo dire che moltiplicare per −1 è come fare una rotazione di 180 gradi?”.

“In senso antiorario, sì”.

“Volendo anche in senso orario, se giri dall'altra parte ottieni sempre −3”.

“Certo. Siccome dobbiamo decidere un verso, diciamo che scegliamo quello antiorario”.

“Perché dobbiamo decidere?”.

“Perché tra un po' dovremo essere più precisi”.

“Va bene. Ancora non vedo numeri complessi, però”.

“Adesso arrivano, porta pazienza. Fino ad ora abbiamo trasformato una moltiplicazione per un numero particolare in una rotazione”.

“Sì, −1 fa ruotare di 180 gradi”.

“Bene. Ora ci chiediamo: quale numero produrrà una rotazione di 90 gradi?”.

“Cioè metà dell'angolo generato da −1. Mi sembra facile, −1/2”.

“Troppo facile, infatti. Ricordati che l'operazione che ha prodotto la rotazione è una moltiplicazione, e tieni presente che ci piacerebbe mantenere tutte le proprietà delle operazioni. Quindi, se moltiplicare per −1/2 potesse tradursi in una rotazione di 90 gradi, vorrebbe dire che moltiplicare per due volte per −1/2 ci dovrebbe portare a una rotazione di 180 gradi. Ma non è così”.

“Non è così perché moltiplicare due volte per −1/2 significa moltiplicare per 1/4, vero?”.

“Certo”.

“Ma allora dovremmo trovare un numero che moltiplicato per sé stesso due volte sia uguale a −1. Ma non esiste!”.

“Eh”.

“E poi, ora che ci penso, una rotazione di 90 gradi non avrebbe nemmeno senso! Non c'è niente a metà via, se ruoti solo di 90 gradi non ruoti il segmento in modo da sovrapporlo alla retta dei numeri”.

“Molto bene, questo è un altro problema, che in realtà ci fa fare un passo avanti verso la soluzione”.

“Quindi stiamo cercando un numero che non esiste che produce una rotazione di un segmento che rappresenta un numero in una zona in cui non ci sono numeri”.

“Perfetto”.

“Vabbé, mi piacerebbe sapere come i Veri Matematici possano aver risolto questo problema non risolubile”.

“Fanno come il capitano Kirk (l'unico, quello vero) con il test Kobayashi Maru: cambiano le regole”.

“Rimango senza parole”.

“Il numero che moltiplicato per sé stesso due volte dà come risultato −1 non c'è? Bene, lo inventiamo (o lo scopriamo, c'è sempre stato ma non ce ne siamo ancora accorti)”.

“Secondo te c'è sempre stato, naturalmente”.

“Naturalmente”.

“E come se la cavano i Veri Matematici col fatto che ruotando di 90 gradi si arriva in una zona senza numeri?”.

“Semplice: riempiono anche quella zona di numeri”.

“Ovvio, come ho fatto a non pensarci prima?”.

“Definiamo quindi un nuovo numero che chiamiamo i e che ha questa proprietà: ruota i segmenti di 90 gradi in senso antiorario. O, se vogliamo stare fuori dalla geometria, tale che il suo quadrato sia uguale a −1”.

“Un numero che non esiste”.

“Se vuoi. Adesso comunque esiste”.

“E perché proprio i?”.

“Iniziale di immaginario”.

“Mi prendi in giro?”.

“No, no, è proprio così che lo chiamano i Veri Matematici. Questo i è l'unità immaginaria”.

“Come unità? Vuoi dire che ce ne sono altri?”.

“Ovviamente. Cosa ci impedisce di fare + i?”.

“Che farebbe 2i?”.

“Già. O anche + 1”.

“E quanto fa?”.

+ 1”.

“Continuo a pensare che tu mi stia prendendo in giro”.

“No, le cose stanno davvero così. Se ammettiamo l'esistenza di i, e se vogliamo continuare a servirci delle proprietà di cui godono di solito i numeri, dobbiamo anche ammettere l'esistenza di un'infinità di nuovi numeri, formati sommando i vecchi numeri reali con i nuovi numeri immaginari. Qualcosa del tipo + ib, con a e b reali”.

“Bleah. E come li chiamiamo, questi numeri?”.

“Numeri complessi”.

“Ma dai”.

“Non è uno scherzo, si chiamano proprio così. E possiamo anche rappresentarli su un piano in maniera molto facile: il numero + ib corrisponde al punto di coordinate (a,b). Ti faccio notare che in questo modo risolviamo anche il problema di non avere numeri al di fuori della retta: adesso ci possiamo riempire un intero piano. Ma non stiamo a fare la solita trattazione che si fa a scuola e che tu conosci già”.

“Certo, no, non facciamola, so già tutto”.

“Bene”.

“STAVO SCHERZANDO”.

“Ah, eh, ecco. Ma va bene lo stesso, non ci interessa davvero ora ripercorrere tutta la storia. Vorrei concentrarmi su un aspetto, quello delle rotazioni. Usando i numeri complessi possiamo riempire tutto il piano, e possiamo anche definire l'unità immaginaria i in modo alternativo, cioè non come si fa di solito a scuola. Possiamo dire che ogni numero complesso, oltre a essere associato a un punto del piano di coordinate (a,b), è anche associato a un vettore che parte dall'origine e arriva in (a,b)”.

“Fin qua posso essere d'accordo, invece di disegnare un punto posso disegnare tranquillamente una freccia”.



“Bene, quindi hai capito che punti del piano, numeri complessi e vettori sono tre aspetti dello stesso ente”.

“Diciamo di sì”.

“Perfetto, allora i sarebbe quell'unico numero che moltiplicato per un vettore lo fa ruotare di 90 gradi in senso antiorario”.

“Ma come fa un numero a fare ruotare un vettore?”.

“Lo fa così come il numero −1 fa ruotare di 180 gradi un numero reale, cioè un vettore orizzontale”.

“Ma il numero −1 fa ruotare i vettori perché è così che funzionano le operazioni!”.

“Benissimo, e qui noi facciamo il contrario. Definiamo le operazioni tra i numeri complessi in modo tale che funzionino come le rotazioni, e siamo a posto”.

“Ma… ma… ma si può? Ma non è come barare? Davvero i Veri Matematici fanno così?”.

“I Veri Matematici fanno un po' quello che vogliono. Se scoprono che le cose funzionano, sono felici e pubblicano i loro risultati, dopo averli ripuliti e circondati da un'aura di mistero. Se invece le cose non funzionano, buttano via tutto e non dicono niente a nessuno. Storicamente i numeri complessi non sono nati così come ti sto raccontando: hanno avuto un'altra origine. È una storia nota: provando a risolvere le equazioni di terzo grado si è visto che se si usavano questi numeri di cui nessuno conosceva il significato (e di cui molti dubitavano pure l'esistenza), le cose funzionavano meglio. Poi è successo che studiando le operazioni tra i vettori nello spazio altri Veri Matematici hanno scoperto altri numeri, che sono poi stati chiamati quaternioni, che rappresentavano molto bene i rapporti tra vettori nello spazio. Prendere un vettore e moltiplicarlo per un quaternione significa allungarlo o accorciarlo e ruotarlo nello spazio. La cosa meravigliosa è che poi, se si studiano le stesse operazioni tra vettori nel piano, i quaternioni in un certo senso si semplificano e diventano i numeri complessi. E allora, volendo, i numeri complessi si potrebbero ridefinire non seguendo la strada classica, ma come quozienti tra vettori nel piano. In generale, quindi, moltiplicare un vettore per un numero complesso significa allungarlo (o accorciarlo, o anche lasciarlo così com'è, naturalmente) e ruotarlo”.

“Che roba. Ho capito una parola ogni dieci, ma mi sembra di intuire che ci siano due modi diversi per vedere le stesse cose, e questo ti fa andare in brodo di giuggiole, vero?”.

“Sì, lo confesso. Aver studiato i numeri complessi a scuola, dove i era la famosa radice di meno uno, e aver rivisto tutta la loro costruzione a partire dal rapporto tra due vettori, mi ha entusiasmato”.

“Mah. E questi numeri complessi servono poi per risolvere il problema del tesoro?”.

“Anche, sì. Ma prima di farlo, se ti interessa questo modo alternativo di definire i numeri complessi, e se vuoi anche sapere qualcosa anche sui quaternioni, ti consiglio di dare un'occhiata a uno dei libri di Giorgio Goldoni. Fa parte della collana Il professor Apotema insegna…, e si intitola proprio I numeri complessi del piano e dello spazio”.




“Ah, un altro libro della collana, bello!”.

“Sì. La prossima volta parliamo poi del problema del tesoro”.

giovedì 11 dicembre 2014

Il problema del tesoro nascosto di Gamow risolto senza parole

Una vecchia pergamena, che descriveva il posto in cui era sepolto un tesoro di pirati su un'isola deserta, dava le seguenti istruzioni. Sull'isola ci sono solo due alberi, A e B, e i resti di una forca.

Partendo dalla forca contate il numero di passi necessari per raggiungere l'albero A camminando in linea retta. Arrivati all'albero, giratevi di 90 gradi a sinistra e procedete per lo stesso numero di passi. Nel punto in cui vi siete fermati piantate un bastone nel terreno.

Tornate ora alla forca e camminate in linea retta fino all'albero B contando i passi. Raggiunto l'albero, voltatevi di 90 gradi verso destra e procedete per lo stesso numero di passi, piantando un altro bastone nel punto in cui vi fermate. Scavate nel punto che si trova esattamente a metà strada tra i due bastoni e troverete il tesoro.

Un giovane, trovata la pergamena con queste istruzioni, affittò una barca e navigò fino all'isola. Non ebbe difficoltà a trovare i due alberi, ma con suo grande disappunto la forca era scomparsa e il tempo ne aveva fatto sparire ogni traccia. Non conoscendo la posizione della forca, non riuscì a trovare alcun modo per individuare il tesoro e se ne tornò a mani vuote.

Ah, se fosse stato un po' più pratico nel calcolo con i numeri complessi, sarebbe tornato a casa ricco!



(Poi vediamo anche le parole che servono per risolvere, eh)
(Se cliccate sulla forca, potete muoverla)

mercoledì 12 novembre 2014

Matematica e gioco d'azzardo

Ebbene, sono diventato enciclopedico ho scritto, assieme a Spartaco Mencaroni — medico e personaggio più serio del sottoscritto — un e-book dal titolo Matematica e gioco d'azzardo.

L'intento è serio: abbiamo raccontato cosa succede in chi si fa prendere così tanto dal gioco da perdere la testa e trasformare il divertimento in malattia.

La matematica ci fa capire dove siano nascosti gli inganni che ci fanno credere di poter vincere anche quando le probabilità sono nettamente contro di noi. Perché, come diceva un saggio, non esistono cose come i pasti gratis, e nessun ente che gestisce il gioco d'azzardo ha mai proposto una scommessa equa.


Il libro fa parte della collana Altramatematica di 40k unofficial, e costa 1.99 euro. Guardatelo, via.

martedì 4 novembre 2014

Perché il triangolo di Tartaglia funziona

“Tutti quanti abbiamo imparato a sviluppare il binomio di Newton col triangolo di Tartaglia, alle superiori…”.

“…”.

“Cosa c'è?”.

“Ma tutti quanti chi? Se mai l'abbiamo imparato, l'abbiamo dimenticato il giorno dopo”.

“Uff”.

“Che poi non serve a niente”.

“Ma cosa c'entra? Da quando in qua in matematica ci mettiamo a fare cose che servono? Noi facciamo cose che ci piacciono, se poi servono sarà un problema dei fisici, degli ingegneri, di quella gente là insomma”.

“Va bene, va bene, non proseguiamo con questo discorso, mi hai già spiegato varie volte il punto di vista dei Veri Matematici. Cos'è questo binomio di Newton? Perché io l'ho dimenticato davvero, eh”.

“Ah, immagino. Il binomio di Newton sarebbe questa espressione qua: (+ b)n”.

“Tutto qua? E a cosa serve perché ne parliamo?”.

“Bé, ne parliamo perché il suo calcolo ci consente di sviluppare una tecnica che poi sarà utile…”.

“Ah-ha! Allora serve a qualcosa!”.

“La matematica è come il maiale, non si butta via niente: qualcuno studia una cosa perché gli interessa, e nel farlo può scoprire un sacco di altre cose interessanti. Oggi però mi interessava farti vedere perché una cosa che in prima superiore ci è stata presentata senza motivazioni chiare funziona”.

“Ammetto che sapere perché una cosa funziona è bello, sì”.

“Oh, bene. Allora, facciamo finta di non sapere niente e proviamo a calcolare lo sviluppo di quel binomio elevato a una generica potenza n”.

“Benissimo, fare finta di non sapere niente mi riesce molto facile”.

“Se uno dovesse calcolarsi tutta l'espressione, dovrebbe tradurla in questo modo: (+ b)(+ b)(+ b)…(+ b), che è un prodotto in cui la parentesi (+ b) compare n volte”.

“E fin qua mi sembra chiaro. Ma se il numero di parentesi è generico, come facciamo a fare i calcoli?”.

“Proprio questo è il punto. Allora, quel prodotto è composto di termini ottenuti scegliendo, per ogni parentesi, una delle due lettere a oppure b”.

“Mh. In che senso scegliendo?”.

“Quando fai il calcolo davvero, devi scrivere tutti i possibili prodotti che potresti ottenere prendendo a oppure b in ogni parentesi. Meglio se ti faccio vedere un esempio: quando devi calcolare (a  b)3, facendo finta di non ricordarti la regola…”.

“Come dicevo, questo mi riesce facilissimo”.

“Ecco, appunto. Allora è come se tu dovessi svolgere questo calcolo: (+ b)(+ b)(+ b). E come lo fai?”.

“E come lo faccio? Boh, moltiplico le prime due parentesi?”.

“Scegli l'ordine che vuoi, sono tutte uguali”.

“Ah, già. Bene, se moltiplico le prime due parentesi devo moltiplicare a per a, poi a per b, poi b per a, poi b per b”.

“Esattamente: ottieni tutti i possibili monomi composti da una lettera scelta nella prima parentesi, e una nella seconda. Cioè a2, ab, ba, b2”.

“Ma ab e ba sono uguali, no?”.

“Sì, e infatti il risultato è a+ 2ab + b2”.

“Però devo ancora moltiplicare tutto per la terza parentesi (+ b)”.

“Sì, e per farlo devi moltiplicare tutto quello che hai ottenuto poco fa prima per a e poi per b, in modo da avere:”.

  • a3 — ottenuto scegliendo a in tutte e tre le parentesi
  • a2b — ottenuto scegliendo a in due parentesi e b in una
  • ab2 — ottenuto scegliendo a in una parentesi e b in due
  • b3 — ottenuto scegliendo b in tutte e tre le parentesi

“Ok, comincio a capire. Però di termini a3 ne ho uno solo, mentre di termini a2b ne ho di più. Devo fare i conti?”.

“Non adesso: vorrei farli nel caso generale, quando hai n parentesi”.

“E come fai a fare il calcolo se non sai quanto vale n? Già con = 3 mi sembra complicato…”.

“Tutto si basa su questa idea: devi scegliere una lettera tra a oppure b in ognuna delle parentesi. Quali combinazioni puoi avere? Quante sono quelle che si ripetono?”.

“Continua a sembrarmi difficile”.

“Vediamo il problema da un altro punto di vista: abbiamo detto che devi fare, per n volte, una scelta tra due”.

“Questo è chiaro, devo scegliere a oppure b”.

“Traduciamo questa idea in un problema diverso: devi muoverti in un labirinto, in cui ogni stanza ha due porte, una con un cartello che indica a e l'altra con un cartello che indica b”.

“Mh. E come è fatto questo labirinto?”.

“Così:”.



“Una scacchiera girata?”.

“E potenzialmente infinita. Naturalmente noi non andremo avanti all'infinito, ma ci fermeremo dopo n stanze. Si parte dall'alto e si può andare solo verso il basso. Diciamo che se scendi verso sinistra hai scelto la porta a, mentre se scendi verso destra hai scelto la porta b”.

“Ah, ok. E quindi cosa devo fare?”.

“Conti. Quante strade puoi scegliere per andare dalla casella in alto a quella con l'asterisco? Strade minime, eh, cioè senza andare avanti e indietro: puoi solo muoverti verso il basso”.



“Una sola”.

“Ok, quindi scriviamo un 1 in quella casella, per indicare che una sola strada porta lì. Metto un uno anche in quella simmetrica dall'altra parte, ok?”.

“Ok. Mi sembra tutto molto ovvio, ma vai avanti, sono sicuro che complicherai le cose molto velocemente”.



“Eh, adesso si tratta di andare avanti. Quante strade ti portano ora nella casella indicata con l'asterisco?”.

“Mi pare una, no? Devo sempre scendere scegliendo la sinistra, ho un solo modo per farlo”.

“Perfetto. E quanti modi invece per arrivare nella casella centrale, quella con la faccina?”.

“Ecco, boh? Cioè, sono due, ma mi chiedo come fare per calcolarlo quando scenderemo nelle righe di sotto”.

“Sì, il problema è scoprire il come, non il quanto. Ma non è difficile: nella casella in questione ci puoi solo arrivare dalle due caselle superiori, no?”.

“Certo, posso solo scendere andando dalla casella di sinistra verso destra, o da quella di destra verso sinistra”.



“E allora il numero di percorsi che puoi scegliere per arrivare in quella casella dipende solo dal numero di percorsi che potevi scegliere per arrivare nelle due caselle superiori”.

“Avevo un solo modo per arrivare nella casella che sta sopra a destra, un solo modo per arrivare in quella che sta sopra a sinistra, quindi adesso ho due modi!”.

“Semplicemente la somma dei modi per arrivare nelle due caselle superiori”.



“Ma allora è facile riempire le righe! Sotto avrò un solo modo per arrivare nella casella all'estrema sinistra…”.

“…che corrisponde alla scelta di a per tre volte”.

“Esatto. E anche nella casella simmetrica a destra posso mettere un 1, perché corrisponde alla scelta di tre volte b. Del resto queste caselle hanno solo una casella sopra di loro, quindi non devo sommare niente”.

“Molto bene. E per le altre due invece?”.

“Ci sono 3 modi per entrambe, dato che le caselle che stanno sopra di loro contengono un 1 e un 2”.



“Benissimo. Hai problemi a riempire le prossime righe?”.

“Direi proprio di no, eccone un po'”.



“Ottimo. Ora non dimentichiamo quello che stiamo facendo: ci stiamo muovendo in un labirinto e stiamo calcolando in quanti modi possiamo arrivare in ciascuna stanza, e però contemporaneamente stiamo anche risolvendo un problema algebrico, che è quello di contare quanti monomi del tipo arbs abbiamo nello sviluppo del binomio (+ b)n”.

“È vero, me lo stavo già dimenticando”.

“Ecco, appunto. Quindi la risposta è questa: il numero dei monomi che otterrai sarà dato dai coefficienti di un'opportuna riga di questa tabella”.

“Quale riga?”.

“Quella giusta!”.

“Ehm”.

“Quella che corrisponde alla potenza che stai calcolando, tenendo presente che la prima riga, quella con una sola casella, corrisponde a non scegliere niente, cioè alla potenza zero”.

“Ah, giusto, la prima scelta comincio a farla quando decido come scendere dalla prima alla seconda riga”.

“Esattamente. Quindi diciamo che numeriamo le righe di questa tabella a partire da 0, non da 1. E, per finire, mettiamo una cifra 1 anche nella casella più in alto, quella di partenza. Corrisponde alla potenza 0, che se evitiamo casi strani ci dà come risultato 1, appunto”.



“Oh, finalmente la tabella completa”.

“L'ultima riga che hai scritto, ad esempio, ci dice che ci sarà un solo monomio del tipo a5, mentre ce ne saranno 5 del tipo a4b,

“Quel 5 corrisponde ad aver scelto per 4 volte a e per una sola volta b, giusto. Ho capito!”.

“Molto bene. Andando avanti, avrai ancora 10 monomi del tipo a3b2, ancora 10 del tipo a2b3, 5 del tipo ab4, e infine uno solo del tipo b5”.

“Questa tabella avrà un nome, suppongo?”.

“Certo, per noi italiani è il triangolo di Tartaglia, per il resto del mondo è il triangolo di Pascal, tranne che per i cinesi, che lo conoscono come triangolo di Yanghui”.

“Che era un cinese che ha scoperto questo triangolo prima degli altri, immagino”.

“Già”.

“Come per gli spaghetti, insomma”.

“Come per gli spaghetti”.




Grazie a eslr, che sul socialino dell'amore mi ha aiutato un sacco a costruire le immagini. Se le avessi fatte a mano colorando pixel per pixel forse ci avrei messo meno tempo, ma volete mettere?

giovedì 16 ottobre 2014

Ada Lovelace Day

Arrivo con un giorno di ritardo, ma ieri è stato l'Ada Lovelace Day, giornata dedicata alla celebrazione dei successi delle donne nei campi della scienza, della tecnologia, dell'ingegneria e della matematica.

Ricordiamo Ada, la prima programmatrice di computer, con un semplice saluto — ovviamente scritto in Ada.

giovedì 9 ottobre 2014

Il teorema dei quattro cinque colori — la dimostrazione

Dimostriamo il teorema dei cinque colori per induzione. Ovvero: supponiamo che sia possibile colorare come si deve un grafo avente un certo numero di vertici, e facciamo vedere che è possibile colorare anche un grafo avente un vertice in più. Da qui, come in una catena di domino in cui ogni tessera che cade mette in moto una nuova tessera, si deduce che il teorema è vero per ogni grafo.

Quindi: sappiamo che in un qualunque grafo ci deve essere un vertice avente al massimo cinque spigoli che escono da esso. Troviamolo.



Ok, concentriamoci sul vertice blu, immaginiamo che il grafo possa proseguire a partire dai vertici rossi come vuole. Anche se i vertici rossi in questo disegno sono tutti connessi con meno di cinque spigoli, in realtà potrebbero averne molti di più.

Il vertice blu è collegato a meno di cinque vertici, in questo caso quattro.

Bene, se noi rimuoviamo dal grafo il vertice blu, otteniamo un grafo che ha un vertice in meno e, quindi, per ipotesi induttiva, è colorabile con cinque colori. Se aggiungiamo il vertice blu, non ci sono problemi a colorare il tutto: dato che è connesso con solo quattro altri vertici, non sono certamente stati usati tutti i cinque colori. Quindi prendiamo un colore che non abbiamo usato e siamo a posto.

Passiamo al caso difficile: il vertice sul quale abbiamo posto l'attenzione è effettivamente collegato con cinque altri vertici, e abbiamo già usato tutti i cinque colori disponibili.



Scegliamo due colori, per esempio il giallo e il viola, e consideriamo solo i nodi colorati con quei colori, e solo gli spigoli che connettono quei nodi. Può succedere, come in questa figura, che il sottografo contenente solo i due colori sia formato da due o più componenti connesse, separate tra di loro. Ecco qua:


Se le cose stanno così, è facile colorare il grafo con cinque colori: basta invertire i colori di una delle due componenti connesse, e si riesce a liberare un colore da assegnare al vertice nero. Per esempio, se invertiamo i colori della componente in alto, otteniamo questa figura:


Abbiamo liberato il colore viola, che possiamo assegnare al vertice nero, ed ecco fatto.

E se il sottografo che contiene i due colori che abbiamo scelto fosse composto da un'unica componente connessa? Come potremmo fare in questo caso? Vediamo un disegnino:


Se le cose fossero così, dovremmo scegliere altri due colori e ripetere il ragionamento fatto sopra. Domanda: siamo sicuri di trovare una coppia di colori che forma almeno due sottografi sconnessi, come prima? Potrebbe verificarsi il caso in cui ogni coppia di colori che noi scegliamo genera un sottografo avente un'unica componente connessa?

La risposta è no, ma se cercate su internet trovate delle spiegazioni poco convincenti e troppo sbrigative. Dice per esempio wikipedia che se scegliamo altri due colori, per esempio il verde e il blu, allora il sottografo formato solo dai nodi avente quei colori e dagli spigoli che li collegano non può essere composto da un'unica componente connessa, perché si intreccerebbe con il sottografo giallo-viola. Ma non è mica vero, non è difficile immaginare un percorso verde-blu non intrecciato col giallo-viola.

Il fatto è che non è possibile che, comunque noi scegliamo due colori, il sottografo che li contiene sia composto da un'unica componente connessa.

Per dire, se aggiungo un po' di collegamenti posso arrivare a una figura del genere, dove ancora le componenti bicolorate sono tutte connesse:

Posso andare avanti ancora? Posso immaginare che blu e rosso siano collegati tra loro da un'unico cammino bicolorato? Sì, è possibile, ma questo cammino dovrà contenere il nodo verde, oppure tutti gli altri. Se contiene il verde, per esempio, può succedere una cosa del genere:


A questo punto un cammino verde-giallo non potrebbe più essere connesso, perché il verde è all'interno del circuito rosso-blu, mentre il giallo è all'esterno (e questo, attenzione, è il risultato di uno di quei teoremi aventi il rapporto chiarezza enunciato/facilità di dimostrazione elevatissimo: si tratta del teorema della curva di Jordan, che dice che ogni curva chiusa del piano non intrecciata divide il piano stesso in due regioni, una interna e una esterna. Sembra una scemata, ma non è banale per niente).

Quindi, anche in questo caso si riesce a colorare il vertice nero con uno dei cinque colori.

Conclusione: l'induzione funziona, le carte geografiche si possono colorare tutte utilizzando cinque colori al massimo.

Per dimostrare che di colori ne servono quattro servono un computer, tanto tempo a disposizione, e una predisposizione filosofica a fidarsi dell'operato di un programma.

mercoledì 8 ottobre 2014

Il teorema dei quattro cinque colori — un errorino nella dimostrazione

Dicevamo che la seconda più bella formula della matematica afferma che Facce più Vertici uguale a Spigoli più 2. Usando le formule: F + V = S + 2.

Ogni faccia di un grafo planare come quelli di cui ci stiamo occupando (cioè quelli che modellizzano una carta geografica, in cui ogni vertice è collegato al più a uno spigolo) è circondata da almeno 3 spigoli. Insomma, non ci occupiamo di grafi di questo tipo:


Siccome le facce sono almeno triangolari, cioè circondate da almeno tre spigoli, allora 3F sarà minore o uguale al numero totale di spigoli presenti nel grafo, moltiplicato per 2 (questo perché ogni spigolo confina con due facce, quindi viene contato due volte). In formule: 3F ≤ 2S.

Facciamo un po' di passaggi banali, come dicono i Veri Matematici.

F + V = S + 2 (formula di Eulero)
3F + 3V = 3S + 6 (moltiplico tutto per 3)
3S = 3F + 3V − 6 (ricavo 3S)
3S ≤ 2S + 3V − 6 (per quanto detto sopra, 3F ≤ 2S)
S ≤ 3V − 6 (sottraggo 2S a destra e a sinistra)
2S ≤ 6V − 12 (moltiplico tutto per 2).

Risultato: il doppio del numero di spigoli nel grafo è minore o uguale di 6V − 12.

Domanda: è possibile che ogni vertice sia connesso a almeno altri sei vertici? Se così fosse, il totale degli spigoli moltiplicati per 2 dovrebbe essere uguale a almeno 6V. Dato che 6V − 12 non può essere uguale a 6V, la risposta alla domanda è no.

Quindi esiste almeno un vertice connesso con altri cinque vertici al massimo.

Nel 1879 il matematico Alfred Kempe annunciò di aver dimostrato il teorema dei quattro colori. Solo undici anni dopo, nel 1890, Percy Heawood si accorse di un errore nella dimostrazione di Kempe. Nel farlo, notò il particolare di cui abbiamo discusso ora (e cioè che deve esistere almeno un vertice dal quale escono al più cinque spigoli) che aprì le porte alla dimostrazione del teorema dei cinque colori. Ovvero: cinque colori sono sufficienti per colorare una carta geografica.

Per dimostrarlo non servono né computer né pagine e pagine di dimostrazioni.