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.

martedì 7 ottobre 2014

Il teorema dei quattro cinque colori — grafi planari

Il teorema dei quattro colori è famoso, facile da enunciare, difficilissimo da dimostrare (tant'è che qualcuno ancora discute sulla validità della sua dimostrazione). Dice che sono sufficienti quattro colori per colorare una qualsiasi carta geografica in modo tale che due territori confinanti non siano colorati con lo stesso colore.

Naturalmente i Veri Matematici non dicono così: non parlano di carte geografiche (per le quali sicuramente si riuscirebbe a trovare qualche strana configurazione che nemmeno i cartografi più assatanati avrebbero mai immaginato di vedere), ma parlano di grafi planari.

I grafi planari sono molto semplici da descrivere: sono costituiti da un po' di oggetti (vertici) collegati da un po' di segmenti, anche curvilinei (detti spigoli, o archi). Cose così, insomma:



Alcuni grafi possono essere rappresentati senza intersezioni tra gli spigoli, altri no. Per esempio il grafo completo (cioè con tutti i possibili collegamenti) con 4 elementi è fatto così:


e basta poco per capire che si può evitare l'intersezione tra i due spigoli interni riarrangiando un pochino il disegno:


(si può fare anche lasciando la configurazione dei vertici un pochino più simmetrica, ma il programma che sto usando non lo fa in automatico e non so come fare per fargli fare quello che voglio io, quindi pazienza)

Esistono grafi non planari, cioè che non possono in nessun modo essere rappresentati sul piano senza intersezioni tra gli spigoli. Un teorema importante di teoria dei grafi (teorema di Kuratowski) afferma che se un grafo contiene almeno un sottografo omeomorfo (cioè avente la stessa forma) a uno dei due disegnati qua sotto, allora non è planare.


Questo qui sopra è il grafo completo con 5 vertici (per gli amici, K5).


E quest'altro è il famoso grafo relativo al giochino delle tre case che devono essere raggiunte dai tre fornitori di servizi (acqua, luce e gas, per esempio). Sono entrambi non planari, naturalmente.

Quindi, riassumendo, le carte geografiche di cui si occupa il teorema dei quattro colori sono grafi
  • planari, 
  • connessi (una carta geografica potrebbe avere due continenti disconnessi, separati da un oceano, ma questo non ci dà fastidio: il nostro problema è colorare un continente alla volta), 
  • semplici, cioè tali che due vertici sono connessi da al massimo un solo spigolo (non ha senso dire che i due stati A e B confinano due o più volte, insomma).


E per questo tipo di grafi è valida la seconda più bella formula della matematica, ovvero Facce più Vertici = Spigoli più 2. Dove con facce intendiamo le regioni delimitate dai bordi, compresa quella esterna che ha estensione infinita.

Dopo tutte queste belle definizioni, e grazie anche a Eulero, dimostrare il teorema dei quattro colori dovrebbe essere molto facile.

lunedì 15 settembre 2014

Una serie di fortunati eventi

Sei anni fa lui aveva 11 anni e io stavo leggendo La Strada. Dopo pochi giorni commentavo: "non ho mica ancora capito se mi è piaciuto o no".

Pochi giorni fa lui ha compiuto 18 anni e io ho assistito a una conferenza di Massimo Recalcati al festival della filosofia di Modena, dal titolo Il modello paterno.

Recalcati ha iniziato parlando dell'evaporazione del concetto di padre, così come lo si intendeva una volta. E fin qua ok. Ha poi aggiunto che la figura del padre è comunque ancora oggi necessaria perché è solo attraverso l'incontro con l'esperienza del limite che si può fare esperienza del desiderio. E qui i padri già cominciano a drizzare le orecchie per provare a capire il loro nuovo ruolo.

Poi è arrivato a parlare di Telemaco, che è il figlio che sa fare esistere il padre (al contrario di Edipo), come Cristo che salva Dio (citando Lacan che, io, ho sentito nominare per la prima volta in quel momento). Per me Cristo che salva Dio è un concetto molto illuminante, uno di quei pensieri sotto traccia che ti girano per la testa senza che tu te ne renda conto.

Poi, Recalcati ha paragonato questo capovolgimento teologico a quello che succede nella storia raccontata da La Strada, in cui la vita del bambino senza nome in un mondo senza Dio rende ancora possibile l'esistenza di Dio.

In quella storia è il figlio che salva il padre.

E questa frase, il figlio che salva il padre, dopo tutto quello che ti è successo da quando lui aveva 11 anni e tu leggevi La Strada, e vedevi proprio lui nel bambino senza nome, questa frase ha evitato tutti i filtri vulcaniani che ti eri fabbricato nel corso della vita, è andata diretta alla pancia, ti ha colpito come mai ti saresti aspettato, e ti ha commosso oltre ogni misura (e dignità di uomo adulto in piedi in mezzo a piazza Grande, ma vabbé).

Dunque buon compleanno, salame che non sei altro. Benvenuto nella maggiore età. E grazie.

domenica 7 settembre 2014

Ma chi l'ha detto che meno per meno fa più?

Eh, la famosa regola del prodotto (e della divisione) dei segni dice che meno per meno fa più, ma perché è così? Perché il prodotto di due numeri negativi deve essere positivo? Perché non negativo al quadrato, per dire? (No, ok, vabbé).

Emma Castelnuovo suggeriva una presentazione, ai fanciulli alle prese per la prima volta con questa domanda, fatta utilizzando un cartoncino colorato con due colori diversi sui due lati. Facciamo blu e rosso.

Interpretiamo la moltiplicazione 2×3 come il calcolo dell'area del suddetto cartoncino rettangolare: se la base è lunga 2 e l'altezza 3, allora l'area sarà 6, e fin qua è facile. Il cartoncino ha la faccia blu verso l'alto, e diciamo che blu = positivo. Mettiamolo su un riferimento cartesiano.



Adesso immaginiamo di sostituire 2 con −2. Cosa significa, dal punto di vista geometrico?

Significa che dobbiamo girare il cartoncino, tenendo fissa l'altezza, in modo che la base ora si estenda lungo la parte negativa dell'asse delle ascisse. Il cartoncino si è capovolto, e ora presenta l'altra faccia. Rosso = negativo. Quindi −2×3 = −6, meno per più fa meno.




Ovviamente se giriamo il cartoncino lungo l'altra direzione, tenendo quindi fissa la base, otteniamo il risultato di 2×(−3), che fa ancora −6, e la proprietà commutativa è assicurata.

Infine, cosa succede se ruotiamo il cartoncino due volte, una tenendo fisso l'asse orizzontale e l'altra tenendo fisso quello verticale? Facile, il cartoncino ruota due volte, andrà a finire nel terzo quadrante, e presenterà però nuovamente la faccia blu. Ecco la magia: −2×(−3)=6, meno per meno fa più.



Ok, questo per i fanciulli. Così si capisce, e probabilmente non si dimentica. Ma un Vero Matematico cosa dice? Mica si mette a giocare coi cartoncini, no? Dov'è il rigore? E poi cosa c'entra la geometria?

Ebbene, i Veri Matematici utilizzano un principio fondamentale, quello che dice la matematica è come il maiale: non si butta via niente (in realtà loro lo chiamano principio di permanenza, o principio di Henkel (questo l'ho scoperto ieri)).

In pratica funziona così: da bambini impariamo a contare, da grandi definiamo l'insieme dei numeri naturali (in pratica rifacciamo la stessa cosa in modo complicato), poi scopriamo delle belle proprietà, ci affezioniamo e vogliamo che esse continuino a essere valide anche quando allarghiamo le nostre definizioni. Definisco i numeri negativi? Bene, però attenzione, per essi devono valere le stesse proprietà che valevano prima, eh. Anzi, se definisco cose nuove devo stare bene attento a non introdurre eccezioni alle regole che già conoscevo prima. In matematica non esiste l'eccezione che conferma la regola, proprio no.

E quindi ora consideriamo la proprietà distributiva del prodotto rispetto alla somma, quella che dice che per calcolare 2×(3 + 4) si può calcolare 2×7 oppure 2×3 + 2×4. In formule:

a×(b + c) = a×b + a×c.

Questa proprietà vale nell'insieme dei numeri naturali, e quando introduciamo i numeri interi desideriamo che essa sia ancora valida. Anzi, estendiamo le regole per questi numeri in modo che sia valida: lo facciamo proprio volontariamente, con questo scopo. E ora applichiamo la proprietà distributiva a questa espressione:

a×(− b) [immaginamo per comodità a e b positivi, senza segni nascosti]

Conosciamo naturalmente già il risultato: sarà 0, dato che − b fa 0. Cosa succede però se applichiamo la proprietà distributiva? Vediamo:

0 = a×(− b) = a×b + a×(−b).

Ma allora a×b e a×(−b) devono essere opposti, dato che il risultato è nullo. Quindi, siccome sappiamo già che a×b è positivo (questi sono i vecchi numeri naturali), allora a×(−b) deve essere negativo. Più per meno deve fare meno.

Infine, consideriamo quest'altra operazione:

a×(− b).

Anche questa deve fare 0, e anche in questo caso, applicando la proprietà distributiva, abbiamo

0 = −a×(bb) = −a×b + (−a)×(−b). Dato che i due termini finali sono opposti, e dato che sappiamo già che −a×b è negativo, è necessario che (−a)×(−b) sia positivo. E così tutto funziona bene, non si può fare altrimenti.

(Poi non dite che i numeri sono creazione della mente umana, eh)

martedì 5 agosto 2014

Codici PIN di quattro cifre che potreste voler utilizzare

0042

Lo sapete tutti, è la risposta alla Domanda Fondamentale sulla Vita, sull'Universo e Tutto quanto.

"Quarantadue!" urlò Loonquawl. "Questo è tutto ciò che sai dire dopo un lavoro di sette milioni e mezzo di anni?"
"Ho controllato molto approfonditamente," disse il computer, "e questa è sicuramente la risposta. Ad essere sinceri, penso che il problema sia che voi non abbiate mai saputo veramente qual è la domanda."


1138

È il numero preferito da Lucas. Da quando esiste Jar Jar Binks, però, non so quanti possano seriamente desiderare di utilizzare questo numero.


1337

Nella codifica leet, si legge leet.


1701

NCC-1701 è il numero di matricola della nave stellare Enteprise, classe Constitution.


1969

Questo è l'unico numero naturale n minore di 4000000 per il quale la funzione standard di Ackermann modulo n non si stabilizza.

Ma è anche l'anno in cui l'uomo ha messo piede sulla luna, eh.


3435

È l'unico numero per il quale la somma delle sue cifre elevate a un esponente uguale a loro stesse è uguale al numero stesso. Si fa prima a scrivere la formula:

33 + 44 + 33 + 55 = 3435.

(No, non è vero, non è l'unico numero di questo tipo, l'altro è 1, ma vabbé. Comunque si chiamano numeri di Münchhausen, perché si elevano da soli, come l'omonimo barone)


5141

Questo è l'unico numero che, rovesciato e letto in esadecimale, rimane uguale a sé stesso.

514110 = 141516.


6174

È la costante di Kaprekar. Funziona così:

  1. prendete un numero qualsiasi di quattro cifre, usando almeno due cifre diverse,
  2. ordinate le cifre in ordine decrescente e in ordine crescente, ottenendo (altri) due numeri
  3. sottraete il più piccolo dal più grande
  4. ripetete i passi 2 e 3

Dopo al massimo sette passi si arriva a 6174, e da lì non ci si muove più.


(Via Facebook)