28 gennaio 2004

Codici correttori
e impacchettamenti di sfere

[ N.B. per chi avesse già letto il mio blog Il problema dei cappelli e i codici correttori del 5 gennaio. Nel blog che segue ci sono alcune (piccole) sovrapposizioni con quello precedente: in particolare il gioco dei tre cappelli e il riquadro su Hamming, inseriti per comodità del lettore. Tutto il resto è nuovo e vorrebbe essere una breve introduzione elementare alla teoria dei codici.]

Conoscete il gioco dei cappelli? Ci sono tre giocatori: Anna, Beppe e Carlo. Essi hanno potuto, prima dell'inizio della partita, concordare con tutta calma una strategia. Inizia il gioco. Sulla testa di ognuno di essi viene messo un cappello, di colore rosso o blu. Il colore è scelto in modo casuale, lanciando una moneta. Ciascuno di loro può vedere il cappello degli altri ma non il proprio. Non possono comunicare in alcun modo. Dopo avere osservato il colore dei cappelli degli amici ed avere meditato abbastanza, Anna, Beppe e Carlo devono scrivere - indipendentemente uno dall'altro - il risultato delle loro riflessioni su di un foglietto: possono solo scrivere quello che ritengono essere il colore del loro cappello oppure la parola 'passo'. I foglietti vengono quindi ritirati. A, B e C vincono solo se non tutti sono passati e se tutti quelli che hanno indicato un colore hanno indicato quello giusto.

Naturalmente è possibile garantirsi la vincita con probabilità 1/2 con la seguente (banale) strategia:

A e B passano. C scrive a caso rosso o blu.

E' possibile però vincere con probabilità 3/4, anche se può sembrare impossibile. Questa è la strategia, uguale per tutti e tre:

Se vedo due colori diversi passo; se vedo lo stesso colore nei due cappelli dei miei amici, scrivo l'altro colore.

Solo in due casi su otto (1/4 dei casi) i tre cappelli avranno lo stesso colore. In questi casi tutti e tre i giocatori sbaglieranno. Nei rimanenti 6 casi (3/4 del totale), ci saranno due cappelli dello stesso colore e uno diverso. I giocatori con il cappello dello stesso colore passeranno, vedendo due colori diversi, mentre il terzo risponderà correttamente!

Questa idea potrebbe essere usata da tre amici per fingere di avere doti telepatiche... Gli ingenui crederanno che si possa vincere in media una volta su due, e pertanto saranno portati a credere che i tre amici abbiano veramente capacità soprannaturali, visto che indovinano il cappello giusto tre volte su quattro!

La strategia indicata può essere estesa (anche se in modo non ovvio) a più giocatori. Per esempio con sette giocatori, il gruppo riesce a vincere ben sette volte su otto!

In realtà dietro il problema dei cappelli c'è molto più di un gioco, la tecnica utilizzata per indovinare il colore del cappello è la stessa che viene impiegata in alcuni codici correttori di errore molto efficaci.

Un codice correttore è un metodo che permette di rivelare la presenza di errori in un messaggio che abbiamo ricevuto, e - entro certi limiti - di correggerli. Anche nella nostra lingua, e in tutti i linguaggi umani, è contenuto un codice di questo tipo. Le parole che usiamo sono un sottoinsieme molto piccolo dell'insieme di tutte le parole che si possono scrivere con le lettere dell'alfabeto. Questo permette di rivelare la presenza di errori. Per esempio se leggo 'vanificu' so che c'è un errore, per il semplice fatto che questa parola non esiste nella lingua italiana. Se non possiedo altre informazioni non posso correggerlo: potrebbe essere sia 'vanifico' che 'vanifica' (supponiamo che ci sia stato un solo errore). Se invece il messaggio è : "Così facendo lei vanificu ogni tentativo di soluzione", so immediatamente vedere l'errore e correggerlo. Osserviamo che il pronome 'lei' è ridondante, potrebbe essere eliminato. Però se il mittente mi avesse spedito "Così facendo vanificu ogni tentativo di soluzione" non avrei saputo (a parte l'uso di altri possibili contesti) se si trattava di una confessione o di una accusa.

Dovrebbe essere chiaro che la possibilità di correggere errori ha un costo. Dobbiamo accettare una minore efficienza di trasmissione, dobbiamo fare ripetizioni, introdurre ridondanza, allungare il messaggio.

Se devo dire a Bob di premere un bottone, tra quattro bottoni numerati 0, 1, 2, 3, e voglio trasmettere solo l'essenziale, voglio cioè avere la massima efficienza possibile, trasmetterò due bit

   0 0 = bottone 0
   0 1 = bottone 1
   1 0 = bottone 2
   1 1 = bottone 3   

Se invece aggiungo un bit di parità

   0 0 0 = bottone 0
   0 1 1 = bottone 1
   1 0 1 = bottone 2
   1 1 0 = bottone 3

Se invece di trasmettere il bit 0 lo ripeto tre volte 000, e allo stesso modo trasmetto 111 al posto di 1, Bob potrà correggere un errore, con la regola della maggioranza

ricevo xyz
dove x, y e z possono essere 0 oppure 1
se ci sono due o tre 0 decodifico xyz come 0
se ci sono due o tre 1 decodifico xyz come 1

Le origini della teoria dei codici correttori risalgono al 1947. In quel periodo Richard W. Hamming lavorava alla Bell Telephone. Allora i computer erano enormi macchine a relè, che scaldavano come stufe e ingoiavano migliaia di schede perforate. Quando la macchina incontrava un errore (cosa che accadeva con una certa frequenza) interrompeva i calcoli e passava al programma seguente nella lista dei lavori. Hamming, un matematico puro con una vena applicativa, si irritava moltissimo quando non trovava i risultati che desiderava, e decise di escogitare un algoritmo che consentisse alla macchina stessa di correggere l'errore incontrato e di proseguire.

Nella foto si vede Richard W. Hamming (1915 - 1996), il fondatore della teoria dei codici correttori d'errore. Ottenne il Ph.D. in Matematica nel 1942 presso l'Università di Urbana-Champain, Illinois. Tra il 1946 ed il 1976 Hamming lavorò alla Bell Telephone, dove collaborò anche con Claude E. Shannon e John W. Tukey. Nel 1950 pubblicò l'articolo "Error Detecting and Error Correcting Codes" che da solo originò un nuovo campo di ricerca. In ogni trasmissione digitale possono avvenire errori. A volte anche l'inversione di un singolo bit di informazione può avvere effetti drammatici, come il blocco dell'intero sistema. In certi casi - come nella ricezione di dati da lontane sonde spaziali o da satelliti in orbita - il canale può essere molto disturbato, ed il segnale molto debole, e gli errori saranno frequenti. In altri - come nella riproduzione di musica o immagini digitali - il supporto fisico stesso può essere danneggiato. Senza metodi efficaci e veloci di correzione degli errori non darebbe possibile ricevere informazioni dallo spazio, usare un lettore di CD o un telefonino! Un graffio di alcuni millimetri sulla superficie di un Compact Disk non pregiudica l'ascolto grazie alla presenza di un codice correttore di Reed - Solomon, in grado di correggere 'raffiche' di errori consecutivi di notevole lunghezza. La teoria dei codici correttori ha applicazioni nei campi più diversi, dalle telecomunicazioni alla biologia molecolare.

La teoria dei codici si basa sull'idea di distanza di Hamming. La distanza di Hamming d(x, y) tra due parole x e y della stessa lunghezza è il numero dei posti nei quali esse differiscono. Per esempio d('rete','sete') = 1, in quanto le due parole differiscono nel primo posto. Invece la distanza tra 'rete' e 'sere' è 2, perché le due parole differiscono nei posti 1 e 3.

Siamo nell'era digitale, tutto è bit. Nessuno si stupirà quindi se abbandoniamo le parole della nostra (amata) lingua italiana, e passiamo alle parole binarie. Una parola binaria è semplicemente una sequenza finita di bit, come 010100101101010.

Qualsiasi trasmissione digitale si può pensare come una trasmissione di parole binarie di una certa lunghezza fissata, semplicemente dividendo in blocchi il flusso di bit.

Per non smarrirci in argomenti troppo generali sviluppiamo la teoria su un esempio particolare, supponendo che i blocchi abbiano tutti lunghezza 7.

Ci sono in tutto 2⁷, ovvero 128, parole binarie di lunghezza 7. Dovrebbe essere chiaro a questo punto che - se vogliamo avere la possibilità di rivelare e correggere errori - dobbiamo selezionare un sottoinsieme piccolo di tutte queste parole, che si chiamerà codice. Rinunciamo all'efficienza in favore della sicurezza. Per meglio dire, rinunciamo ad una parte della efficienza per ottenere una certa sicurezza. Si tratterà sempre di un compromesso. Le due cose sono intrinsecamente opposte.
L'antico adagio "non si può avere la botte piena e la moglie ubriaca" - fonte di infinite meditazioni - rende bene l'idea.

Chiamiamo C il nostro codice, insieme di parole binarie di lnghezza 7. L'idea di Hamming è questa:

Se ogni parola di C ha distanza almeno 3 da ogni altra parola di C
allora siamo in grado di correggere 1 errore

Supponiamo che ogni parola del codice C disti almeno 3 (con la distanza di Hamming) da ogni altra parola del codice. E supponiamo di inviare la parola x appartenente a C, e che Bob riceva y. Se y è uguale ad x, non ci sono problemi. Se è avvenuto un errore, y non sta in C e si trova a distanza 1 da x. Bob potrà correggere l'errore decodificando y come l'unica parola del codice che dista 1 da y. Se esistesse in C una parola z, diversa da x, a distanza 1 da y, si concluderebbe che la distanza tra x e z è strettamente minore di 3. Infatti si potrebbe in un passo passare da z a y, e in un secondo passo da y a x, e quindi la distanza di Hamming tra x e z sarebbe al più 2.

Questo è il primo codice non banale (non di ripetizione) in grado di correggere un errore, scoperto da Hamming

Codice C di Hamming

x0  =     0     0     0     0     0     0     0
x1  =     0     0     0     1     1     1     1
x2  =     0     0     1     0     1     1     0
x3  =     0     0     1     1     0     0     1
x4  =     0     1     0     0     1     0     1
x5  =     0     1     0     1     0     1     0
x6  =     0     1     1     0     0     1     1
x7  =     0     1     1     1     1     0     0
x8  =     1     0     0     0     0     1     1
x9  =     1     0     0     1     1     0     0
x10 =     1     0     1     0     1     0     1
x11 =     1     0     1     1     0     1     0
x12 =     1     1     0     0     1     1     0
x13 =     1     1     0     1     0     0     1
x14 =     1     1     1     0     0     0     0
x15 =     1     1     1     1     1     1     1

Naturalmente la possibilità di correggere un errore si paga con una diminuzione dell'efficienza. Utilizzando le parole di C possiamo inviare soltanto 16 simboli, che corrispondono a 4 bit di informazione. Le nostre parole hanno lunghezza 7. Pertanto 3 bit non portano alcuna informazione: servono solo ad aggiungere ridondanza, a consentire la correzione. Però 4/7 è molto meglio di 1/3, il rapporto fornito dal codice di ripetizione visto prima.

Possiamo arrivare alle medesime conclusioni partendo da un altro punto di vista, quello dell'impaccamento (o impacchettamento) di sfere. Si vedrà poi quanto sia interessante, a volte, un leggero cambiamento di visuale.

Diciamo sfera di centro x e raggio t
l'insieme di tutte le parole binarie che hanno 
da x distanza di Hamming minore o uguale a t

Scriviamo gli elementi della sfera di raggio 1 e centro x₁ = (0 0 0 1 1 1 1)

0     0     0     1     1     1     1
1     0     0     1     1     1     1
0     1     0     1     1     1     1
0     0     1     1     1     1     1
0     0     0     0     1     1     1
0     0     0     1     0     1     1
0     0     0     1     1     0     1
0     0     0     1     1     1     0

Un codice C è in grado di correggere t errori se
le sfere di raggio t con centri nelle parole del codice
sono disgiunte
(cioè non hanno elementi in comune)

Il codice di Hamming che abbiamo studiato esiste perché nell'insieme delle 128 parole binarie di lunghezza 7 ci sono 16 sfere disgiunte di raggio 1: gli elementi di C sono precisamente i centri di queste sfere. Le sfere sono disgiunte proprio perché la distanza minima tra due parole diverse del codice è 3. In generale

le sfere con centri in D e raggio t sono disgiunte 
se la distanza minima tra le parole di D è almeno 2t+1

Naturalmente le sfere di Hamming non somigliano molto agli oggetti sferici del nostro mondo. Esiste però una rappresentazione geometrica dei codici, dovuta a Claude Elwood Shannon.

Claude E. Shannon nacque a Gaylord (Michigan) nel 1916. Nel 1940 ottenne il PhD in Matematica presso il Massachusetts Institute of Technology. Nel 1948 pubblicò un articolo rivoluzionario: "A Mathematical Theory of Communications". In questo lavoro introdusse il concetto di capacità di un canale di trasmissione ed estese, per la prima volta, la definizione di entropia (mutuata dalla meccanica statistica) ad una sorgente di informazione. L'entropia cresce se la ridondanza del messaggio è bassa, se il messaggio è poco prevedibile. Il suo teorema fondamentale dei canali senza rumore dice che se C è la capacità del canale ed H è l'entropia della sorgente, si può trasmettere in media un numero di simboli al secondo vicino quanto si vuole (ma strettamente inferiore) a C/H. Nel teorema sui canali con rumore Shannon dimostra che se H è minore di C, il segnale può essere codificato in modo tale da rendere piccola a piacere la probabilità di errori nella trasmissione! Nel 1949 Shannon pubblicò "Communication in the Presence of Noise". In esso aprì orizzonti inesplorati, mostrò paesaggi mai visti da occhio umano. Diede una rappresentazione geometrica dei segnali, identificandoli con punti di una spazio multidimensionale (in generale con dimensione molto grande) e la utilizzò efficacemente per provare una serie di teoremi profondi e del tutto inaspettati. Per usare le sue parole : "The advantage of this geometrical representation of the signals is that we can use the vocabulary and the results of geometry in the communication problem."

In "Communication in the Presence of Noise" Shannon parte dall'ipotesi che disponiamo di un canale di ampiezza di banda W per un tempo T. Allora il segnale che inviamo può essere identificato con un punto in uno spazio a 2WT dimensioni. E' insomma determinato da un vettore con 2WT componenti reali. Se abbiamo in mano un microfono, connesso ad sistema reale di trasmissione, e parliamo per mezzora, il nostro discorso corrisponde ad un punto in uno spazio di opportuna dimensione (fissata dall'ampiezza di banda e dal tempo). Altro discorso, altro punto. Musica, Mozart, Beatles, è lo stesso, purché si rimanga nella banda e nel tempo: tutti punti del nostro spazio. A partire da questa rappresentazione Shannon dimostra che è possibile trasmettere segnali con probabilità di errore piccola a piacere, a patto che si rimanga nei limiti della capacità del canale, determinata soltanto da W, dalla potenza del segnale che trasmettiamo e dalla potenza del rumore che disturba la connessione. Come dice Shannon stesso, questo è un risultato alquanto sorprendente, poiché ci ci aspetterebbe che ridurre la frequenza degli errori comporti ridurre la velocità di trasmissione, e che questa velocità tenda a zero al tendere a zero della probabilità di errore.

La dimostrazione di questo stupefacente teorema di Shanon si basa su un fatto geometrico poco noto

In una sfera con un grande numero di dimensioni, 
quasi tutto il volume è vicino alla superficie

Diciamo A il volume della mela di raggio R,
e B quello della sfera residua di raggio S.
Allora si ha
A = k R3
B = k S3
dove abbiamo posto k = 4/3 p
Vogliamo che si abbia
1/1000 A = B
sostituendo e semplificando si ottiene
1/1000 R3 = S3
Pertanto S = 1/10 R, e R-S = 9/10 R

Premettiamo che il volume di una sfera a n dimensioni è
k Rn
dove R è il raggio e k è una costante che dipende solo da n.
I raggi R ed S sono legati ora da
1/1000 Rn = Sn
donde
S = R (1/1000)1/n
Quindi
per n = 10,  R-S = 0,4988 R
per n = 100,  R-S = 0.0667 R
per n = 1000,  R-S = 0,0068 R

Ma perché Shannon parla di sfere, i segnali non erano punti di uno spazio n-dimensionale? Le sfere sono generate dal rumore. Il rumore presente nel canale disturba il segnale, e sposta il punto che rappresenta il segnale trasmesso di un certo tratto che dipende dalla potenza del rumore stesso, in una direzione casuale. In fase di ricezione allora il segnale non sarà più lì dove lo abbiamo messo, ma sarà all'interno di una sfera con centro nel segnale. Le sfere devono essere disgiunte, affinché il decoder alla ricezione possa recuperare correttamente il segnale inviato. Tutti i segnali possibili stanno in uno spazio limitato, contenuti in una sfera di centro l'origine e di raggio che dipende dalla potenza di trasmissione. Per sfruttare appieno l'ampiezza della banda e la potenza di trasmissione dobbiamo potere inviare molti segnali distinti. Per riceverli correttamente devono essere abbastanza lontani: siamo di nuovo di fronte al problema del'impaccamento di sfere.

Codici buoni derivano da impaccamenti densi di sfere in spazi n-dimensionali.

Il problema di determinare, per una data dimensione n, l'impaccamento di sfere più denso è molto difficile. Quello che certamente sorprenderà è il fatto che la dimensione 3 (quella in cui ci muoviamo) presenti tanta difficoltà.

Partiamo dalla dimensione 2, siamo nel piano. Prendiamo tante monetine uguali e cerchiamo di accostarle il più possibile, otterremo qualcosa del genere

Ogni moneta tocca altre 6 monete, i centri delle monete formano un reticolo esagonale. Supponiamo, per convenzione, che il raggio delle monete sia 1. Ogni moneta può essere inscritta in un esagono regolare di lato 2/Ö3. La densità dell'impaccamento è data dal rapporto tra lo spazio occupato dalle monete e lo spazio totale. Poiché la figura dell'esagono che contiene la moneta si ripete sempre uguale, la densità cercata è il rapporto tra l'area della moneta e l'area dell'esagono, cioè p/Ö12 = 0,9096. E' stato dimostrato da Axel Thue nel 1890 che questa è la massima densità possibile: qualsiasi altro modo di sistemare le monete sul tavolo lascerà una percentuale di spazio vuoto maggiore. Per esempio se accostiamo le monete in modo tale che i centri formino un reticolo quadrato, ogni moneta toccherà 4 altre monete e sarà circoscritta da un quadrato di lato 2. La densità in questo caso è il rapporto tra l'area della moneta e l'area del quadrato, cioè p/4 = 0,7854

Veniamo alla dimensione 3. Cercando di impacchettare palle di cannone, o più pacificamente delle arance, troveremo immediatamente almeno due modi

A sinistra abbiamo il reticolo che si chiama cubico semplice centrato. Le sfere hanno i centri nei punti dello spazio ordinario con coordinate (x, y z) intere qualsiasi. Hanno raggio 1/2 e volume p/6. Lo spazio si divide in cubi di lato e volume 1, ognuno dei quali contiene una sfera. La densità è pertanto p/6 = 0,5236 (il rapporto tra il volume della sfera e quello del cubo che la contiene). Le sfere riempiono poco più della metà dello spazio!

A destra abbiamo il reticolo che si chiama cubico a facce centrate. Le sfere hanno i centri nei punti dello spazio ordinario con coordinate (x, y z) intere tali che x+y+z sia pari. Hanno raggio Ö2/2 e volume 2p/(3Ö2). Lo spazio si divide in cubi di raggio 2 e volume 8, ognuno dei quali contiene una sfera intera e dodici quarti di sfere (per un volume totale pari a 4 sfere). Pertanto la densità è p/(3Ö2) = 0,7405. Le sfere riempiono quasi i tre quarti dello spazio!

Il reticolo a facce centrate è estremamente naturale, perché possiede una stabilità intrinseca. Le sfere dello strato superiore si adagiano in un incavo generato da corrispondenti sfere nello strato inferiore. In qualunque mercatino vedrete piramidi di arance create con questa tecnica. Esiste un impaccamento più denso di sfere? Questo problema ovviamente si è presentato moltissime volte nella storia. Fu Keplero a porlo in maniera esplicita nel 1611. Siete liberi di pensare che la risposta sia evidente, come fare di meglio? E' voce comune che qualsiasi fisico, interrogato in materia, non esprima alcun dubbio...

La realtà è però estremamente più complessa. Soltanto nel 1998, 387 anni dopo la manifestazione di dubbio di Keplero, si è pervenuti ad una dimostrazione certa. La dimostrazione, del matematico Thomas C. Hales, è lunga e difficile; alcuni profondi teoremi generali riducono il problema all'esame di diverse migliaia di casi particolari, espressi da grafi planari. La validità del teorema è quindi ottenuta dall'analisi, mediante computer, di questi casi, con sofisticate tecniche di programmazione lineare. Qualsiasi persona (in grado di comprendere il procedimento) potrebbe portare a termine la ricerca, eseguendo i calcoli passo passo, ma questo richiederebbe centinaia di anni. Il computer si sostituisce all'umano semplicemente perché fa i conti più velocemente.

La bibbia sull'argomento dell'impacchettamento di sfere in spazi n-dimensionali è il libro di J.H. Conway e N.J.A. Sloane "Sphere Packings, Lattices and Groups", opera superba, degna della grandezza dei due autori. Essi mettono in evidenza l'importanza di questo problema nei campi più diversi: la geometria pura (appare nel famosissimo elenco dei problemi aperti posti da Hilbert nel 1900), i gruppi finiti semplici, la teoria dei numeri (equazioni diofantee e geometria dei numeri), comunicazioni digitali (questo lo abbiamo visto :), calcolo numerico e teoria delle superstringhe.

La densità massima di un impaccamento di sfere in uno spazio n-dimensionale è attualmente sconosciuta per n maggiore di 3: si conoscono soltanto dei limiti superiori e inferiori. Ogni dimensione sembra avere la sua particolarità, e non si vede un metodo che possa funzionare per tutte.

Si è avuto un recentemente un avanzamento notevolissimo, grazie all'articolo di Henry Cohn e Noam Elkies "New upper bounds on sphere packings I", pubblicato nel 2003 sul numero 157 della prestigiosa rivista "Annals of Mathematics". Gli autori utilizzano un metodo derivante dalla programmazione lineare e trovano limiti migliori di quelli noti per le dimensioni da 4 a 36. Sembra vicinissima la soluzione per le dimensioni 8 e 24.

Qualche giorno fa (l'8 gennaio 2004) Noam Elkies ha ricevuto il Conant Prize dell'American Mathematical Society, per il suo articolo (in due parti) "Lattices, Linear Codes, and Invariants", pubblicato sulle "Notices of the AMS, 47, nos. 10-11 (2000)".

L'eclettico Noam Elkies, che è professore ad Harvard, ha anche composto concerti ed è un esperto di scacchi.

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

5 gennaio 2004

Il problema dei cappelli
e i codici correttori

Cominciamo con la versione minimale del problema dei cappelli. Ci sono tre giocatori: Anna, Beppe e Carlo. Essi hanno potuto, prima dell'inizio della partita, concordare con tutta calma una strategia. Inizia il gioco. Sulla testa di ognuno di essi viene messo un cappello, di colore rosso o blu. Il colore è scelto in modo casuale, lanciando una moneta. Ciascuno di loro può vedere il cappello degli altri ma non il proprio. Non possono comunicare in alcun modo. Dopo avere osservato il colore dei cappelli degli amici ed avere meditato abbastanza, Anna, Beppe e Carlo devono scrivere - indipendentemente uno dall'altro - il risultato delle loro riflessioni su di un foglietto: possono solo scrivere quello che ritengono essere il colore del loro cappello oppure la parola 'passo'. I foglietti vengono quindi ritirati. A, B e C vincono solo se non tutti sono passati e se tutti quelli che hanno indicato un colore hanno indicato quello giusto.

Naturalmente è possibile garantirsi la vincita con probabilità 1/2 con la seguente (banale) strategia:

A e B passano. C scrive a caso rosso o blu.

E' possibile però vincere con probabilità 3/4, anche se può sembrare stupefacente. Questa è la strategia, uguale per tutti e tre:

Se vedo due colori diversi passo; se vedo lo stesso colore nei due cappelli dei miei amici, scrivo l'altro colore.

Solo in due casi su otto (1/4 dei casi) i tre cappelli avranno lo stesso colore. In questi casi tutti e tre i giocatori sbaglieranno. Nei rimanenti 6 casi (3/4 del totale), ci saranno due cappelli dello stesso colore e uno diverso. I giocatori con il cappello dello stesso colore passeranno, vedendo due colori diversi, mentre il terzo risponderà correttamente!

Il gioco si può fare con un numero n qualsiasi di giocatori. Le regole sono le stesse, come si può vedere qui sotto.

Incredibilmente, se ci sono 2^k-1 giocatori, con k maggiore di 1, esiste una strategia con la quale si perde in appena 1 caso su 2^k.

Per descrivere questa strategia, occorrono alcune definizioni.

Definizione 1: espressione binaria
Diciamo espressione binaria su k bit di un intero h compreso tra 0 e 2k-1
la stringa B(h,k) = (bk-1, bk-2,..., b0)
dove ogni bj è uguale a zero o a uno e vale l'uguaglianza
å bj 2j = h

Esempio 1
B(5,3) = (1 0 1)
B(5,4) = (0 1 0 1)
B(22,7) = (0 0 1 0 1 1 0)
B(0,7) = (0 0 0 0 0 0 0)
B(127,7) = (1 1 1 1 1 1 1)

Definizione 2: XOR
Diciamo XOR di due stringhe binarie di lunghezza k, u e v, la stringa z così definita:
per ogni i, zi = ui Å vi
dove Å agisce sui singoli bit così:
0 Å 0 = 0
0 Å 1 = 1
1 Å 0 = 1
1 Å 1 = 0

Chiamiamo O la stringa (0 0 0 ... 0), le cui componenti sono tutte nulle.
Se z è lo XOR di u e v scriviamo z = u Å v

Esempio 2
(0 1 1) Å (1 1 1) = (1 0 0)
(0 1 1 1 0 0 1) Å (1 1 0 1 1 1 0) = (1 0 1 0 1 1 1)

a Å b Å c Å ... = g 

Definizione 3: XRV(j)
Supponiamo che ci siano n = 2k-1 giocatori, con k maggiore di 1.
I giocatori sono numerati da 1 a n.
Ad ognuno di essi si assegna la stringa di k bit B(i,k), dove i è il numero del giocatore.
Chiamiamo B(i,k) codice del giocatore i.
Per ipotesi ogni giocatore porta un cappello blu o rosso.
XRV(j) per definizione è lo XOR dei codici dei giocatori con il cappello rosso visti da j.
(Mnemonica: XRV(j) sta per Xor dei Rossi Visti da j)

Esempio 3
Siano k = 2, n = 3, distribuzione di colori = (R R B):
I giocatori 1 e 2 hanno il cappello rosso, 3 ha il cappello blu. Pertanto:
XRV(1) = B(2,2) = (1 0);
XRV(2) = B(1,2) = (0 1);
XRV(3) = B(1,2) Å B(2,2) = (0 1) Å (1 0) = (1 1).

Definizione 4: XTR
Nelle stesse ipotesi della Definizione 3,
diciamo XTR lo XOR dei codici di tutti i giocatori con il cappello rosso.
(Mnemonica : XTR sta per Xor di Tutti i Rossi)

Con i medesimi dati dell'Esempio 3 si ha:
XTR = B(1,2) Å B(2,2) = (0 1) Å (1 0) = (1 1).

Lemma
(1) u Å v = O se e solo se u = v.
(2) v = u Å v se e solo se u = O
(3) Se j è un rosso XTR = XRV(j) Å B(j,k).
(4) Se j è un blu allora XTR = XRV(j).

Strategia ottimale
La strategia è uguale per tutti. Consideriamo il giocatore numero j.
Il giocatore numero j fa lo XOR dei codici dei giocatori che vede con il cappello rosso, 
e ottiene la stringa di k bit XRV(j):
Se XRV(j) = O, j scrive sul suo foglio 'rosso'. 
Se XRV(j) è il suo stesso codice (cioè XRV(j) = B(j,k)), j scrive 'blu'.
In tutti gli altri casi j scrive 'passo'.

Facciamo un esempio con k = 3 (e quindi n = 7).

Supponiamo che la distribuzione dei cappelli sia (B B R B R R R).
In altri termini i giocatori 1, 2 e 4 hanno il cappello blu, 
mentre i giocatori 3, 5, 6, 7 hanno il cappello rosso.
Abbiamo: 
XRV(3) = B(5,3) Å B(6,3) Å B(7,3) = (1 0 1) Å (1 1 0) Å (1 1 1) = (1 0 0)
XRV(5) = B(3,3) Å B(6,3) Å B(7,3) = (0 1 1) Å (1 1 0) Å (1 1 1) = (0 1 0)
XRV(6) = B(3,3) Å B(5,3) Å B(7,3) = (0 1 1) Å (1 0 1) Å (1 1 1) = (0 0 1)
XRV(7) = B(3,3) Å B(5,3) Å B(6,3) = (0 1 1) Å (1 0 1) Å (1 1 0) = (0 0 0)
Nel caso che stiamo considerando XTR = (1 1 1).
Per il Lemma (4) XRV(1) = XRV(2) = XRV(4) = (1 1 1).
Nessun giocatore ha ottenuto un XRV uguale al proprio codice. 
Quindi passeranno tutti tranne 7 che ha ottenuto (0 0 0).
In base alla strategia convenuta, 7 scriverà 'rosso', che è corretto.
Dunque il team vince!

Vediamo ora perché la strategia ottimale vince in (2k-1)/2k casi.

Distinguiamo due casi.

Caso 1, XTR = O

Per ipotesi lo XOR dei codici di tutti i rossi è nullo. 
Tutti i blu hanno XRV = XTR = O e pertanto scriveranno tutti 'rosso'. 
Se j è rosso dal Lemma (3) si ha che XTR = XRV(j) Å B(j,k). 
Cioè, nel caso che stiamo considerando, vale la 
(*) XRV(j) Å B(j,k) = O
Dalla (*) e dal Lemma (1) si ottiene che, per ogni j rosso, XRV(j) = B(j,k). 
Pertanto tutti i rossi ottengono uno XRV uguale al loro stesso codice e scriveranno 'blu'. 
Tutti sbagliano!

Può sembrare una catastrofe, ma è la forza del metodo. 
Quando si sbaglia, si sbaglia tutti insieme.

Poichè XTR - che è una stringa di k bit - può assumere 2k valori,
e poichè tutti sono equiprobabili, data la casualità della scelta dei colori,
il Caso 1 si verificherà, in media, 1 su 2k volte.

Rimane solo da vedere che in tutti gli altri casi il team dei giocatori vince.

Caso 2, XTR non nullo

Poiché XTR non è nullo, è l'espressione binaria di un unico intero compreso tra 1 e 2k-1.
Dunque XTR = B(j,k), per un unico j tra 1 ed n.
Cominciamo a vedere che tutti i giocatori h diversi da j passano.
Supponiamo h compreso tra 1 ed n e diverso da j.
Se h è blu XTR = XRV(h), ovvero XRV(h) = B(j,k).
Poiché h ha un XRV diverso dal suo codice e diverso da O, h passa.
Se h è rosso, sappiamo che XTR = XRV(h) Å B(h,k).
Segue B(j,k) =  XRV(h) Å B(h,k).
Non si può avere XRV(h) = O, altrimenti B(j,k) = B(h,k) e j = h.
Non si può avere XRV(h) = B(h,k), altrimenti per il Lemma (1) B(j,k) sarebbe nullo.
Dunque h passa.
Resta da provare che il giocatore j non passa e scrive il colore giusto.
Ragioniamo esattamente come prima. 
Se j è blu XRV(j) = XTR. Dunque XRV(j) = B(j,k)  e j scrive 'blu'.
Se j è un rosso, XTR = XRV(j) Å B(j,k).
Ovvero B(j,k) = XRV(j) Å B(j,k).
Dunque, per il Lemma (2), XRV(j) è nullo, e j scrive 'rosso'.

Il team supera la prova!

Dovrebbe essere evidente che la strategia descritta è troppo efficiente e al tempo stesso elegante per non provenire da una qualche teoria matematica di più vasta portata. In effetti la soluzione del problema dei cappelli è basata sui codici di Hamming, che sono particolari codici correttori d'errore.

Nella foto si vede Richard W. Hamming (1915 - 1996), il fondatore della teoria dei codici correttori d'errore. Ottenne il Ph.D. in Matematica nel 1942 presso l'Università di Urbana-Champain, Illinois. Tra il 1946 ed il 1976 Hamming lavorò alla Bell Telephone, dove collaborò anche con Claude E. Shannon e John W. Tukey. Nel 1950 pubblicò l'articolo Error Detecting and Error Correcting Codes che da solo originò un nuovo campo di ricerca. In ogni trasmissione digitale possono avvenire errori. A volte anche l'inversione di un singolo bit di informazione può avvere effetti drammatici, come il blocco dell'intero sistema. In certi casi - come nella ricezione di dati da lontane sonde spaziali o da satelliti in orbita - il canale può essere molto disturbato, ed il segnale molto debole, e gli errori saranno frequenti. In altri - come nella riproduzione di musica o immagini digitali - il supporto fisico stesso può essere danneggiato. Senza metodi efficaci e veloci di correzione degli errori non darebbe possibile ricevere informazioni dallo spazio, usare un lettore di CD o un telefonino! Un graffio di alcuni millimetri sulla superficie di un Compact Disk non pregiudica l'ascolto grazie alla presenza di un codice correttore di Reed - Solomon, in grado di correggere 'raffiche' di errori consecutivi di notevole lunghezza. La teoria dei codici correttori ha applicazioni nei campi più diversi, dalle telecomunicazioni alla biologia molecolare.

Introduciamo allora il codice di Hamming di parametro k, Ham(k).

I codici di Hamming
Sia k un intero maggiore di 1. Poniamo n = 2k-1.
Diciamo A(n) l'insieme di tutte le stringhe binarie di lunghezza n.
A(n) possiede 2n elementi.
Ogni elemento di A(n) può essere visto come una distribuzione di colori dei cappelli
dove 0 significa 'blu' e 1 'rosso'.
Ad ogni a in A(n) possiamo allora associare una stringa binaria XTR, di k bit,
data dallo XOR dell'insieme delle espressioni binarie B(i,k)
dove i è un indice tra 1 ed n tale che ai = 1.
Ham(k) è definito come l'insieme degli a in A(n) tali che XTR = O.
Poiché, come è già stato osservato, XTR è nullo una volta su 2k,
Ham(k) contiene 2m elementi, con m = 2k-k-1.

Creiamo una corrispondenza biunivoca T tra l'insieme delle stringhe di m bit e Ham(k).
Dividiamo il messaggio in s blocchi di bit di lunghezza m: b1, b2, ..., bs.
Invece di trasmettere bj, inviamo sul canale T(bj).

Ricevo una stringa di bit x di lunghezza n (stringa codificata).
Calcolo la stringa XTR relativa a x.
Se XTR è nullo, x appartiene a Ham(k) e decodifico x come T-1(x) (un blocco di m bit).
Se XTR non è nullo, sarà uguale a B(j,k) per un unico j.
In base al discorso fatto in precedenza dovrebbe ora essere chiaro che,
se c'è stato un singolo errore, j è la posizione del bit errato!
Cambio il bit j, ottenendo x', elemento di Ham(k).
Decodifico ora x come T-1(x').

Vediamo un esempio.

Esempio di utilizzazione di Ham(3)
Per k = 3, n = 23-1 = 7.
A(7) contiene 27 = 128 stringhe binarie.
Con le notazioni precedenti m = 23-3-1 = 4.
Ham(3) contiene quindi 24 = 16 stringhe.
Precisamente Ham(3) è formato dagli elementi di A(7) che hanno XTR = O.
Ecco l'elenco degli elementi di Ham(3):

     0     0     0     0     0     0     0
     0     0     0     1     1     1     1
     0     0     1     0     1     1     0
     0     0     1     1     0     0     1
     0     1     0     0     1     0     1
     0     1     0     1     0     1     0
     0     1     1     0     0     1     1
     0     1     1     1     1     0     0
     1     0     0     0     0     1     1
     1     0     0     1     1     0     0
     1     0     1     0     1     0     1
     1     0     1     1     0     1     0
     1     1     0     0     1     1     0
     1     1     0     1     0     0     1
     1     1     1     0     0     0     0
     1     1     1     1     1     1     1

Verifichiamo che la terza stringa (0 0 1 0 1 1 0) sta in Ham(3).
I bit 1 (i cappelli rossi) sono nelle posizioni 3, 5, 6.
Dobbiamo calcolare XTR = XOR di B(3,3), B(5,3) e B(6,3):
XTR = B(3,3) Å B(5,3) Å B(6,3) = (0 1 1) Å (1 0 1) Å (1 1 0) = (0 0 0).

La corrispondenza biunivoca T tra l'insieme delle stringhe binarie di lunghezza 4
e Ham(3) è immediata, basta prendere i primi 4 bit di ogni elemento di Ham(3).
Si osserverà che essi sono le espressioni binarie degli interi da 0 a 15 in ordine.
Dalla prima alla sedicesima riga, i primi quatro bit sono, in ordine:
B(0,4), B(1,4), ...., B(15,4).
(Si noti che qualsiasi corrispondenza biunivoca andrebbe bene ugualmente)
I primi 4 bit contengono l'informazione, gli ultimi 3 sono di controllo.
Immaginiamo che mi vogliano comunicare il blocco di informazione (1 0 1 1).
Inviano allora T(1 0 1 1) = (1 0 1 1 0 1 0) = dodicesima riga.
Supponiamo che nella trasmissione ci sia un errore, che colpisce il bit 1.
Io ricevo allora x = (0 0 1 1 0 1 0).
Calcolo XTR relativo a x:
XTR = B(3,3) Å B(4,3) Å B(6,3) = (0 1 1) Å (1 0 0) Å (1 1 0) = (0 0 1).
Poichè (0 0 1) è B(1,3) deduco che è avvenuto un errore al primo posto.
Correggo  e ottengo x' = (1 0 1 1 0 1 0).
Calcolo T-1(1 0 1 1 0 1 0) = (1 0 1 1) e trovo il messaggio inviatomi.

(0 0 0)
(1 1 1)

T(0) = (0 0 0)
T(1) = (1 1 1)

Definiamo efficienza del codice il rapporto m/n, tra il numero m dei bit di informazione contenuti iu un blocco e la lunghezza n del blocco stesso.

Dunque Ham(2) ha efficienza 1/3. Invece Ham(3) ha efficienza 4/7, e Ham(5) 26/31. Con Ham(5) ogni 31 bit inviati ben 26 sono di informazione e appena 5 sono di controllo. Questi codici molto veloci possono essere utilizzati con grande vantaggio tutte le volte che la probabilità p di un errore di trasmissione su un bit sia molto bassa, tanto che diventi trascurabile p², la probabilità che accadano due errori su n bit trasmessi.

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

6 dicembre 2003

Trovato il quarantesimo
numero primo di Mersenne!

Non è difficile provare che un numero M della forma M = 2ⁿ-1 (con n maggiore di 1) può essere primo solo se n è primo. Purtroppo la condizione non è sufficiente. Nella tavola sottostante si può vedere quello che accade in corrispondenza degli esponenti primi da 2 a 31.

2	3	5	7	11	13	17	19	23	29	31
primo	primo	primo	primo	non primo	primo	primo	primo	non primo	non primo	primo

Per esempio 2⁷-1 = 127 è primo, ma 2¹¹-1 = 2047 = 23 89 non è primo. I numeri primi della forma 2^p-1 sono chiamati primi di Mersenne in onore del monaco Marin Mersenne che fece alcune congetture su di essi nel 1644. I primi di Mersenne sono legati indissolubilmente ai numeri pari perfetti.

Un intero N si dice perfetto se è la somma dei suoi divisori, N escluso. 
Per esempio:
6 = 1 + 2 +3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
Sussiste il seguente teorema (Euclide - Eulero):
Un intero pari N è perfetto se e solo se
N = 2p-1 (2p-1) con 2p-1 primo.

Il quarantesimo campione è stato trovato il 17 novembre da Michael Shafer, un ingegnere chimico di 26 anni che partecipa alla GIMPS, la "Great Internet Mersenne Prime Search". GIMPS è un progetto gestito da PrimeNet. PrimeNet è un sistema di calcolo parallelo distribuito in rete a livello mondiale, creato nel 1997 da Scott Kurowski, basato sulla medesima tecnolgia di Entropia, impresa fondata Kurowski stesso. In questo momento il server di PrimeNet connette 49385 computers, che eseguono qualcosa come 9549 gigaflops al secondo, con una potenza di calcolo pari a quella di 170 supercomputer Cry T932. Chiunque può unirsi alla ricerca, è sufficiente scaricare il software necessario, ovviamente gratuito. Il bello è che l'utente non si accorge nemmeno di averlo, perché funziona solo quando la CPU non è impegnata a fare altro. La parte più interessante del software è di George Woltman, che ha implementato in linguaggio macchina un sofisticato algoritmo di Richard Crandall, che consente di eseguire velocemente i calcoli necessari per il test di primalità, con numeri di milioni di cifre. L'algoritmo è descritto - tra mille altri affascinanti risultati - nel bellissimo libro che Crandall ha scritto con Carl Pomerance: "Prime numbers, a computational perspective".

Shaefer racconta che era appena tornato da un colloquio con il suo advisor all'Università statale del Michigan, quando si è accorto di un messaggio sullo schermo del computer: trovato un nuovo primo di Mersenne! Si tratta di un numero primo veramente grande, con più di sei milioni di cifre (per l'esattezza 6320430), uguale a 2^20996011 -1. Ad esso corrisponde un numero perfetto con più di dodici milioni di cifre! Shaefer ha immediatamente avvertito lo staff della GIMPS, e sono state messe in moto due verifiche parallele e indipendenti, una in Spagna e l'altra in California, che hanno confermato la primalità di 2^20996011-1. L'annuncio definitivo è stato dato il 5 dicembre.

Siamo vicini ad un grande record: la scoperta di un numero primo con almeno dieci milioni di cifre. Per questa scoperta la Electronic Frontier Foundation offre un premio di 100000 dollari. Il premio precedente - di 50000 dollari - è stato assegnato nel 2000 a Nayan Hajratwala il quale, partecipando alla GIMPS, trovò nel 1999 il 38-esimo primo di Mersenne (2098960 cifre).

Altri documenti:

Elenco dei primi di Mersenne noti
Perché cercare numeri primi grandi?

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

12 novembre 2003

Il gioco delle tre porte
e Marilyn vos Savant

Nel sito di Mariano Tomatis c'è un elenco di ben 101 enigmi, interessanti, difficili o semplicamente divertenti. Il primo di essi è "Le tre porte". Ecco il testo:

In un gioco a premi, abbiamo davanti tre porte: dietro una di queste c'è un'auto, nelle altre due una capra. Dobbiamo scegliere una porta, e vinceremo quello che troviamo là dietro.
Fatta la scelta, il presentatore ci dice "Ne sei proprio sicuro? Puoi ancora cambiare la scelta: anzi, ti voglio aiutare e riduco le scelte a due. Ecco: dietro questa porta, c'è una capra". Cosi` dicendo, apre una delle porte che noi non abbiamo scelto, mostrando una capra.
Ammesso che vogliamo vincere l'auto, ci conviene cambiare porta, o la cosa è indifferente?
Nota bene:
- il presentatore ci fa la domanda qualunque sia stata la nostra scelta.
- il presentatore apre sempre una porta diversa da quella scelta da noi, e la sceglie in modo che abbia dietro una capra.

Su questo quiz sono stati scritti decine di articoli e centinaia di lettere. Il quesito veniva posto dal presentatore (Mothy Hall) del famoso gioco televisivo "Let's make a deal". Per fissare le idee supponiamo che le porte siano etichettate A,B e C. Supponiamo inoltre che il concorrente (Paolo) abbia scelto la porta A, e che Monthy abbia aperto la porta B (dietro la quale c'è una capra). Il problema è: conviene a Paolo mantenere la sua scelta o passare a C? Alcuni spettatori pensavano: "Perché Mothy dovrebbe aiutarmi a vincere un'auto e intaccare il budget del gioco? Il suo è certamente un tentativo di ingannarmi! Io rimarrei saldamente alla mia prima scelta". Molti altri invece facevano il seguente ragionamento: "Inizialmente la probabilità di vincere era 1/3 (una su tre). Ora so che l'auto è dietro la porta che ho scelto - la porta A - oppure è dietro la porta C. Non ho informazioni, non so dove sia, e la scelta è equiprobabile. Ho probabilità 1/2 (una su due) di vincere. Lancerò una moneta per decidere".

Questo rimase lo stato della questione finché nella sua rubrica domenicale "Ask Marilyn", Marilyn vos Savant espresse il suo punto di vista: "Paolo ha scelto la porta A. La probabilità che l'auto sia lì è 1/3, e quindi si trova con probablità 2/3 dietro B o C. Eliminata B da Monthy, ci sono due possibilità su tre che si trovi dietro C. Ovvero, cambiare scelta raddoppia la probabilità di vincere!"

L'opinione di Marilyn vos Savant non va sottovalutata. La sua rubrica è molto letta e seguita (raggiunge un pubblico potenziale di settanta milioni di lettori), anche perché non si tratta di una persona qualsiasi. E' citata nel Guinness dei primati perché possiede il più alto QI mai registrato (228)! Naturalmente questo dato è per molti fastidioso, se non inquietante, e certamente non le dà il diritto di pontificare su qualsiasi argomento. In ogni modo suscitò un vespaio. A parte ogni altra considerazione, suggeriva una strategia che - se vera e se seguita dai giocatori - avrebbe portato i finanziatori del quiz ad una spesa assai più alta.

Furono in molti a dileggiarla, anche matematici con tanto di Ph.D.; per esempio, dall'Università della Florida le scrissero: "Lei sembra avere difficoltà a cogliere gli aspetti fondamentali della teoria della probabilità... C'è già abbastanza ignoranza matematica nel paese, senza che si metta a creare confusione anche la persona con il più alto QI del mondo!"

Ma Marilyn fu irremovibile, anzi passò all'attacco con il seguente 'esperimento mentale'. Avete dinnanzi un milione di porte e ne scegliete una, per esempio la 100223. Monthy apre tutte le porte (con relative belanti capre) tranne la vostra e la 777777. Cambiate porta o no? Dopo tutto con la prima scelta avevate solo una probabilità su un milione di vincere!

Le risposte si moltiplicarono, e vennero scritti articoli persino sul New York Times e sull' American Mathematical Monthly. Eppure il fatto che la Savant avesse ragione è inconfutabile ed è facilmente dimostrabile. Supponiamo che l'auto sia dietro alla porta A. La strategia del giocatore consiste nello scegliere una porta e nel decidere se cambiare o meno. Dopo di che vince o perde. Quello che può accadere è illustrato nella tabella sottostante:

Chiaro, no?

C'è stata quest'anno una rinascita dell'interesse sul problema delle tre porte. Uno studente ha scritto a Ask Marilyn: "Sto svolgendo in classe un test con una domanda alla quale sono assegnate tre risposte A, B, C, ed una sola di esse è vera. Io non capisco nemmeno il senso della domanda, decido di rispondere a caso e scelgo la risposta A. Prima che consegnamo il professore decide di aiutarci e dice: 'Guardate che la C è proprio sbagliata...'. Mi conviene cambiare, e mettere la crocetta sulla risposta B?"

Ci sono state molte risposte. Alcuni pensano che il problema sia analogo a quello delle tre porte e che convenga cambiare, altri invece ritengono che sia diverso, e che dopo l'informazione del professore sia indifferente scegliere A o B, perché hanno la stessa probabilità (1/2) di essere vere. E voi che ne pensate?

A volte Marilyn pone un problema, come sfida, attende le reazioni dei lettori e poi dà la risposta esatta, nell'ammirazione di tutti quelli che hanno passato notti insonni per risolverlo. Questo è uno degli ultimi, che ha dato filo da torcere a molti.

Siete in una stanza assolutamente buia. Sul tavolo davanti a voi, a portata di mano, c'è un mazzo di carte. Tutte le carte sono voltate verso il basso, tranne dieci - inserite a caso - che sono rivolte dall'altro lato. Il vostro compito è produrre due mucchi di carte che contengano ognuno lo stesso numero di carte girate verso l'alto. Come fate?

Non c'è nessun trucco, la risposta è del tutto razionale. E sembra anche ovvia (una volta che l'avete trovata :).

E' chiaro che tanta intelligenza non sempre è una benedizione, e può dare alla testa, come troppo bourbon. Così è accaduto che la vos Savant scrivesse nel 1995 un libretto invero indegno della sua levatura mentale. Si tratta di "The world's most famous math problem", dedicato all'ultimo teorema di Fermat. In questo lavoro Marilyn si lancia a testa bassa contro la dimostrazione di Wiles, con una violenza pari alla sua assoluta ignoranza matematica. E' vero che dalla bibliografia appare che abbia letto tutte le pubblicazioni rilevanti, ma c'è da chiedersi quanto abbia capito! Nigel Boston e Andrew Granville hanno scritto - all'epoca - una recensione del libro sull'American Mathematical Montly. Nella recensione si può trovare una collezione di 'perle', delle quali mi limito a citare la seguente:

"La radice quadrata di +1 è un numero reale perché +1 x +1 = +1
 però la radice quadrata di -1 è immaginaria perché -1 x -1 = +1"

Pubblico la soluzione di Gaetano Squitieri

credo di esserci arrivato con l'aiuto del commento di mau...
comunque si prendono le prime dieci carte e si rivoltano...
questo e' un mazzo e il resto delle carte e' l'altro...
se nel mazzo piccolo non c'erano carte rivoltate, ora ce ne sono 10 come nell'altro e cosi' via....
complimenti per il sito...
gaetano squitieri

Pubblico la lettera inviata da .mau. Certamente coloro che non credono alla soluzione data al problema delle tre porte, parteciperanno numerosi alla scommessa che .mau. propone!

A suo tempo avevo preparato una simpatica scommessa sul gioco delle tre porte, che sto recuperando e mettendo su http://xmau.com/mate/scommessa.html .

Il problema modificato è appunto modificato. Il professore non sa quale risposta io ho scelto. Quindi in un caso su tre dice quella che ho scelto io (e allora devo cambiare per forza), negli altri due non mi cambia la vita.

Il problema del mazzo di carte è simpatico, perché tutti iniziamo a pensare "come riuscire a fare due mazzetti con cinque carte voltate" senza notare che c'è scritto "lo stesso numero di carte voltate". Non parliamo poi della possibilità di voltare delle carte senza poterle vedere :-)

ciao, .mau.

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

10 ottobre 2003

Il gioco Survivor e l'iterazione del soffitto

Il gioco Survivor è stato inventato da Jim Tanton e Charles Adler, ed è ispirato a un noto gioco televisivo americano. Vi sono N giocatori, numerati da 1 ad N. Ad ogni turno si deve votare se l'ultimo giocatore (quello numerato con N) deve restare o andarsene. Se una percentuale degli N giocatori pari almeno al 50% vota sì, l'N-esimo giocatore rimane e il gioco finisce. Se meno del 50% vota sì, l'N-esimo giocatore deve andarsene e si passa al turno successivo, nel quale si voterà per il giocatore N-1. Quando il gioco finisce le persone rimaste dividono tra di loro in parti uguali un premio di 10 milioni di euro. Si fanno le due seguenti ipotesi:

• Tutti i partecipanti vogliono guadagnare il più possibile
• Tutti i partecipanti giocano razionalmente

Se q = 0, non c'è bisogno nemmeno di un sì e tutti i numeri sono stabili. 
Pertanto per ogni k intero positivo si ha B(0,k) = k.
Supponiamo allora q positivo.  
Il primo numero stabile è sempre 1, quindi B(q,1) = 1 per ogni q.
Siano N un intero maggiore di 1 ed M = B(q,k) 
il più grande numero stabile minore di N.
Poichè M è stabile i giocatori G1, G2,..., GM votano no, 
perchè sanno che comunque rimangono anche se GN se ne va.
Tutti gli altri invece votano sì, perchè - per ipotesi - tra M ed N 
(estremi esclusi) non ci sono numeri stabili: 
essi sanno perciò che la eliminazione di GN 
porterebbe al loro stesso allontanamento nei turni seguenti. 
La percentuale dei favorevoli è pertanto p = (N-M)/N. 
Allora N è il numero stabile B(q,k+1) se:
1) p ³ q
2) N è il più piccolo intero che soddisfa la 1)
equivalentemente N stabile se:
3) N ³ B(q,k)/(1-q)
4) N è il più piccolo intero che soddisfa la 3)
Infine:

5)         B(q,k+1) = soffitto(B(q,k)/(1-q))

dove soffitto(x) è per definizione il più piccolo intero ³ x

Successione B(1/3,k)
1, 2, 3, 5, 8, 12, 18, 27, 41, 62, 93, 140, 210, 315, 473,...

Successione C(1/2,k)
1, 3, 7, 15, 31, 63, 127,..., 2k - 1

6)         C(q,k+1) = soffitto+(C(q,k)/(1-q))
Dove la funzione soffitto+ è così definita:
Se x non è intero soffitto+(x) = soffitto(x),
altrimenti soffitto+(x) = x+1

Le due successioni B(q,k) e C(q,k) differiranno tra di loro
in tutti gli elementi di indice successivo al primo k
tale che B(q,k)/(1-q) è intero.

Dato un numero reale r definiamo la funzione F(r,x):
       F(r,x) = r soffitto(x)
e consideriamo la successione con valore iniziale 1
ottenuta dalla iterazione della F(r,x):
       x1 = 1
       xn = F(r,xn-1)
Allora, posto r = 1/(1-q), B(n,k) differisce da C(n,k)
a partire dal minimo k diverso da 1 per cui xk è intero.

Successione dei B(7/22,k)
1, 2, 3, 5, 8, 12, 18, 27, 40, 59, 87, 128, 188, 276, 405, 594, 872,
1279, 1876, 2752, 4037, 5921, 8685, 12738, 18683, 27402, ...
 
Successione dei C(7/22,k)
1, 2, 3, 5, 8, 12, 18, 27, 40, 59, 87, 128, 188, 276, 405, 595, 873,
1281, 1879, 2756, 4043, 5930, 8698, 12758, 18712, 27445, ...

Successione degli xk = F(22/5,xk-1)
  22  44  22  22  176  88  132  198  176  1298  638  2816  4136  2024
1,--, --, --, --, ---, --, ---, ---, ---, ----, ---, ----, ----, ----, 594
  15  15  5   3   15   5    5    5    3    15    5    15    15    5

Nel loro articolo "Approximate squaring" (pubblicato il 23 settembre), J. C. Lagarias e N. J. A. Sloane hanno formulato - portando a suo favore molti argomenti - questa congettura:

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

16 settembre 2003

La matematica di Google

Il 7 settembre Google ha festeggiato il suo quinto compleanno. Google è nato nel 1998, creato da Sergey Brin e Lawrence Page. Inizialmente era gestito da quattro dipendenti e soddisfaceva, in inglese, 10000 richieste al giorno. Oggi Google supporta 88 lingue, ha 1000 dipendenti e soddisfa 200 milioni di richieste al giorno cercando le informazioni in un database di circa tre miliardi di pagine. Più della metà delle richieste proviene da stati non USA. La risposta avviene in un tempo medio inferiore al mezzo secondo.

Dietro il successo di Google c'è un algoritmo matematico che assegna ad ogni pagina un coefficiente numerico, tra zero ed uno, detto rango. Le pagine che contengono le parole chiave o le frasi immesse dall'utente, vengono listate in ordine di rango. Si ottengono spesso, come risultato di una ricerca, molte centinaia di pagine, che vengono elencate dieci alla volta; difficilmente l'utente ne vede più di una trentina: è quindi chiara l'importanza di apparire ai primi posti. Intuitivamente, come potremmo pensare di attribuire un numero ad ogni pagina web, un numero che rappresenti l'importanza della pagina? Internet è un insieme di pagine che sono connesse da link. E' naturale pensare che una pagina sia tanto più autorevole quanti più link esistono verso di essa. E ovviamente la sua autorevolezza dipende non solo dal numero ma anche dalla autorevolezza delle pagine stesse che si collegano ad essa. Sembra un ragionamento circolare. Proviamo a formalizzarlo.

Supponiamo che nel Web ci siano n pagine: P₁, P₂,...,P_n. Diciamo che P_j punta a P_i se nella pagina P_j c'è un link verso la pagina P_i. Otteniamo così un grafo orientato G. Possiamo anche disegnarlo su un foglio: segnamo con la penna n punti e li numeriamo da 1 ad n in un ordine arbitrario; poi - se P_j punta a P_i - uniamo P_j a P_i con una freccia. Visualizzare un problema è sempre utile, ma ciò che veramente ci serve, in questo caso, è una matrice: la matrice di adiacenza del grafo. Chiamiamola M. M è formata solo di zero e di uno, ed è così definita:

[0]
Mi,j = 1 se Pj punta a Pi
Mi,j = 0 altrimenti

[1]
Ri = l åj Rj
dove la sommatoria è estesa ai j tali che Pj punta a Pi

[2]
Ri = l åj Mi,j Rj
dove nella sommatoria l'indice va da 1 a n

[3]
R = l M R

Un approccio simile è discusso in profondità in un articolo di Jon M. Kleinberg: Authoritative Sources in a Hyperlinked Environment.
Vi sono anche interessanti connessioni con il cosiddetto impact factor, che viene utilizzato per la valutazione delle pubblicazioni scientifiche: un articolo è importante se viene citato in molti articoli importanti...

Torniamo ora a Google: il rango di una pagina viene qui calcolato mediante un algoritmo chiamato "PageRank", dove Page non significa "pagina", ma è il cognome di Lawrence Page.

Brin e Page hanno descritto le basi matematiche del loro progetto nel loro articolo "The Anatomy of a Large-Scale Hypertextual Web Search Engine", che si può trovare su CiteSeer.
PageRank utilizza non solo i link in entrata, ma anche quelli in uscita. Diciamo U_j il numero di link che si trovano nella pagina P_j, ovvero il numero delle pagine P_i cui punta P_j. U_j è precisamente la somma della colonna j-esima della matrice di adiacenza. Formiamo una nuova matrice T dividendo ogni 1 che si trova nella colonna j-esima di M per U_j, e lasciando invariati gli zeri. Pertanto:

[4]
Ti,j = 0 se Mi,j = 0
Ti,j = 1/Uj se Mi,j = 1

[5]
Sia A un utente della rete.
Denotiamo con Q(t) il vettore n-dimensionale, funzione del tempo t,
la cui i-esima componente Qi(t) è la probabilità che 
A si trovi nella pagina Pi al tempo t.
E' data la distribuzione iniziale Q(0).
Allora per ogni t si ha che Q(t+1) = T Q(t).
Equivalentemente, per ogni t ed h si ha Q(t+h) = Th Q(t),
dove Th denota la potenza h-esima di T.

[6]
S = d C + (1-d) T
Q(t+1) = S Q(t)
Q(t+h) = Sh Q(t)

Infine anche ora, come in [3], il vettore rango R è un autovettore, precisamente è l'autovettore normalizzato di S con autovalore 1, dato da:

[7]
R = S R

[8]
(1) Il limite, per h che tende a infinito, della i-esima riga di Sh
     è la riga costante [Ri, Ri,...,Ri]
     dove ogni elemento è uguale alla i-esima componente di R.
(2) Esistono una costante positiva c ed un numero positivo r < 1
     tali che, per ogni i, per ogni j e per ogni n, si ha, posto V = Sn: 
    | Vi,j - Ri | < c rn 

In realtà l'algoritmo effettivamente usato da Google è molto più complesso; quello che abbiamo descritto è solo il suo nucleo essenziale. Vi sono molte varianti. Per esempio, nll'articolo citato, Brin e Page parlano della possibilità di assegnare valori di d variabili a seconda delle pagine, o di gruppi di pagine. Aggiungo che algoritmi simili sono applicabili a molti problemi diversi, al di là dei motori di ricerca.

Buon compleanno Google!

Consideriamo un minuscolo web formato da 6 pagine P₁, P₂,...,P₆, e supponiamo che la matrice di adiacenza M del grafo orientato G che rappresenta i link tra le varie pagine sia questa:

Matrice M
     1     1     0     0     1     1
     1     1     1     0     0     1
     0     0     0     0     1     1
     1     0     0     1     0     0
     1     0     1     1     1     1
     0     0     1     0     1     0

Somme delle colonne di M
U1 = 4
U2 = 2
U3 = 3
U4 = 2
U5 = 4
U6 = 4

Matrice T
    0.2500    0.5000         0         0    0.2500    0.2500
    0.2500    0.5000    0.3333         0         0    0.2500
         0         0         0         0    0.2500    0.2500
    0.2500         0         0    0.5000         0         0
    0.2500         0    0.3333    0.5000    0.2500    0.2500
         0         0    0.3333         0    0.2500         0

In questo caso il vettore rango R è l'autovettore normalizzato di T associato all'autovalore 1, e si trova:

Rango R associato a T
    0.2540
    0.2222
    0.0794
    0.1270
    0.2328
    0.0847

Se all'inzio A e ugualmente attratto dalla pagina 2 e dalla 3, e trascura in prima istanza le altre, la distribuzione iniziale di probabilità sarà:

Distribuzione iniziale I
    0
    0,5
    0.5
    0
    0
    0

    0.2500
    0.4167
         0
         0
    0.1667
    0.1667

    0.3542
    0.3125
    0.0833
    0.0625
    0.1458
    0.0417

    0.2917    0.2791    0.2622    0.2562    0.2534    0.2529    0.2531
    0.2830    0.2461    0.2304    0.2226    0.2205    0.2204    0.2210
    0.0469    0.0647    0.0693    0.0755    0.0780    0.0793    0.0797
    0.1198    0.1328    0.1362    0.1336    0.1309    0.1288    0.1276
    0.1944    0.2131    0.2271    0.2322    0.2341    0.2341    0.2337
    0.0642    0.0642    0.0748    0.0799    0.0832    0.0845    0.0850

   -0.0009
   -0.0012
    0.0003
    0.0006
    0.0009
    0.0003

Potenza sedicesima di T
    0.2540    0.2540    0.2540    0.2539    0.2540    0.2540
    0.2222    0.2222    0.2222    0.2222    0.2222    0.2222
    0.0794    0.0794    0.0794    0.0794    0.0794    0.0794
    0.1270    0.1270    0.1270    0.1270    0.1270    0.1270
    0.2328    0.2328    0.2328    0.2328    0.2328    0.2328
    0.0847    0.0846    0.0847    0.0847    0.0847    0.0847

Infine una breve riflessione su d. L'effetto del passaggio del "coefficiente di distrazione" d da 0 a 1 è quello di spostare via via R dal valore che abbiamo visto alla distibuzione uniforme, nel nostro caso quella che associa ad ogni pagina la probabilità 1/6 = 0.1667.
Ho calcolato la matrice S = d C + (1-d) T per d = 1/7, 2/7,...,1. Nella tabella sottostante si vede il variare del rango R:

Spostamento verso il rango unforme all'aumentare di d
    0.2360    0.2197    0.2053    0.1928    0.1823    0.1735    0.1667
    0.2142    0.2059    0.1978    0.1899    0.1822    0.1745    0.1667
    0.0937    0.1070    0.1195    0.1315    0.1432    0.1549    0.1667
    0.1302    0.1351    0.1411    0.1475    0.1541    0.1605    0.1667
    0.2268    0.2199    0.2119    0.2025    0.1919    0.1799    0.1667
    0.0992    0.1124    0.1245    0.1357    0.1464    0.1567    0.1667