Chi ritiene che il 19 sia un numero stupido, senza grandi pretese, non vada a leggere il nuovo numero del Carnevale della Matematica.

Ultimo aggiornamento: 2009-11-14 17:40

Qualche giorno fa Maxxfi mi ha chiesto cosa ne pensassi delle dimostrazioni matematiche fatte per mezzo del calcolatore. La mia laconica risposta è stata “brutte, ma valide”; provo ad aggiungere qualche considerazione in più.
Innanzitutto, bisogna mettersi d’accordo sui termini: cos’è una dimostrazione matematica al calcolatore? Lascio immediatamente da parte i programmi di intelligenza artificiale che dimostrano semplici teoremi, magari dandone nuove dimostrazioni, oppure se ne escono con nuovi teoremini non pubblicati in precedenza: quelle sono dimostrazioni del computer, e hanno la stessa validità degli esercizi che ci facevano fare nel biennio di matematica (forse un po’ meglio, se il programma è fatto bene e gli sono stati implementati correttamente gli algoritmi.
Esistono poi “dimostrazioni” che non lo sono affatto: prendiamo ad esempio il test di primalità di Miller-Rabin, che permette di verificare molto velocemente se un numero è presumibilmente primo. Un non matematico può pensare che se la probabilità che il numero testato non sia primo sia di 1 su 10¹⁰ ci si potrebbe anche accontentare, e in effetti molti programmi di crittografia usano questi probabili primi accettando il rischio che primi non siano e quindi si possa fare un attacco al testo crittografato; ma un matematico non potrà mai dire “quel numero è primo”.
Resta infine il gruppo di dimostrazioni al computer vere e proprie: quella archetipale è per il teorema dei quattro colori, che afferma che bastano quattro colori per colorare una qualunque mappa in modo che nessuna coppia di regioni confinanti (per un tratto, i singoli punti non contano) abbia lo stesso colore; ma ad esempio c’è stata anche quella della congettura di Keplero, che afferma che il miglior impacchettamento di sfere nello spazio tridimensionale è quello che faremmo tutti, facendo tanti strati a esagono uno sopra l’altro. Queste dimostrazioni, che gli anglofoni definiscono “computer assisted”, hanno una struttura comune. Il teorema è stato inizialmente analizzato e azzannato, e si è arrivati a dire che il caso generale si può ricondurre a un numero finito di sottocasi particolari; nel caso del teorema dei quattro colori si parla di 1476 mappe (grossine) distinte, mentre per la congettura di Keplero sono state ritenute necessarie più di 5000 configurazioni di sfere. In questi casi, il calcolatore serve a verificare che nessuna di queste mappe/configurazioni invalidi il teorema: un lavoro che in linea puramente teorica si potrebbe fare a mano, ma richiederebbe non so quante centinaia d’anni, e si rischierebbe di fare degli errori (tenetevi a mente questa frasetta).
L’atteggiamento dei matematici rispetto a queste dimostrazioni al calcolatore è prettamente filosofico. Alcuni non le considerano valide perché affermano che la dimostrazione deve essere comprensibile a un essere umano, e se non ci si può mettere a verificare tutti i casi allora la dimostrazione in verità non esiste. Altri hanno una preclusione più di principio: come ci si può assicurare che l’algoritmo usato sia corretto, e il programma per computer lo implementi correttamente? Altri ancora, credo la maggioranza, non si fanno di questi problemi e prendono il teorema per dimostrato.
La mia visione personale? Come credo abbiate capito, non ho nessun problema ideologico su una dimostrazione assistita dal computer. Per quanto riguarda la correttezza degli algoritmi, si può ovviare alla cosa implementando indipendentemente più programmi su più architetture diverse – in effetti per il teorema dei quattro colori hanno fatto così – e verificando che l’output sia lo stesso. D’altronde, non è che le dimostrazioni umane siano scevre da errori: proprio il teorema dei quattro colori era stato “dimostrato” nel 1879 salvo poi accorgersi nel 1890 che la dimostrazione era errata. Insomma, la correttezza degli algoritmi e la correttezza delle dimostrazioni sono in fin dei conti la stessa cosa. Nel caso poi degli algoritmi probabilistici di cui sopra, c’è persino chi afferma che se la probabilità che l’algoritmo non ci prenda sia inferiore a quella di un errore hardware della macchina allora si ha la certezza, ma è una linea di pensiero che non mi ispira molto, a meno di pensare anche che tutti gli esseri umani possano venire ipnotizzati contemporaneamente ;-)
Detto tutto questo, resta il mio giudizio lapidario iniziale: il teorema è sì dimostrato, ma la dimostrazione è così brutta che un Vero Matematico se ne fa ben poco, come diceva anche Erdős. Non è detto che esista una dimostrazione “bella” di questi teoremi; visto però che questi teoremi non sono fondamentali nel senso di essere alla base di tanta matematica si può anche decidere di non contarla come dimostrazione dal punto di vista estetico. A voi la scelta!

Ultimo aggiornamento: 2009-11-11 07:00

Ricordate il messaggio di veto su una legge scritto da Arnold Schwarzenegger, le cui prime lettere di ogni riga compitavano “Fuck You”? Istigato da Stefano Bartezzaghi, ho provato a vedere qual era la probabilità di ottenere casualmente una frase di senso compiuto. (Per la cronaca, lo spazio più ampio segnalato da Bartezzaghi alla fine di ogni frase è una caratteristica standard delle regole tipografiche americane, e l'”I” iniziale secondo me non fa parte del presunto messaggio nascosto, visto che tutte le lettere di veto del simpatico ex-culturista iniziano con quelle due righe standard)
Il conto che faccio è molto spannometrico, come spiego in seguito; iniziamo con la parte di stima semplice. Il numero di combinazioni di tre lettere con o senza senso, da aaa a zzz, è 26*26*26 = 17576 mentre quello di combinazioni di quattro lettere è 26*26*26*26 = 456976. Il numero di parole inglesi effettivamente esistenti è molto minore: qui sono riportate 1108 parole di tre lettere e qui il numero di parole di quattro lettere viene stimato essere intorno a 7000. Quindi c’è circa una possibilità su 16 di avere una parola di tre lettere e una su 65 di averne una di quattro, il che dà come probabilità totale 1 su 1000.
Questa è un’analisi molto grossolana, che soffre almeno di tre distorsioni.
– Le due parole devono avere senso messe insieme come frase; questo in una lingua virtualmente posizionale come sta diventando l’inglese non è un grosso problema e non mi preoccupa più di tanto.
– Ho presupposto che le lettere iniziali delle parole inglesi siano tutte equiprobabili, il che è chiaramente falso, ma di brutto. Una distribuzione anisotropa dovrebbe rendere più probabile il riuscire a creare combinazioni, ma non è detto; bisogna anche vedere se una lettera molto frequente come iniziale è anche molto frequente all’interno o alla fine di una parola.
– Bisogna tenere conto che molte delle parole inglesi esistenti sono in realtà arcaiche e non usate, e quindi non verrebbero riconosciute da un cacciatore di acrostici che non sia davvero appassionato alla cosa. Tanto per dire, io mica so che significhi “wog” o “uts”! (beh, no; a dire il vero “uts” è il plurale di “ut”, quindi significa “le arcaiche note do”)
Dare una stima di questi punti è un tipico Problema di Fermi, e bisognerebbe mettersi di buzzo buono a fare delle stime sensate, magari scegliendo a caso un po’ di parole per vedere la loro distribuzione. La mia sensazione è che il primo punto riduce la probabilità di un fattore 3, il secondo la accresce fino a un fattore 10, mentre il terzo è più difficile da valutare visto che l’accorgersi che un insieme di lettere forma una parola dipende dalla cultura di chi sta leggendo quelle lettere; secondo me la probabilità si riduce di un fattore 100 (ricordatevi che qua e nel caso precedente sono due le parole da considerare, e quindi bisogna moltiplicare le probabilità relative)
Qualcuno vuole lanciarsi in stime più accurate?

Ultimo aggiornamento: 2009-11-04 11:42

Il 21 ottobre 1914 nacque a Tulsa, in Oklahoma, un neonato che decise poi di laurearsi in filosofia e fare il giornalista freelance… fino al 1956, quando Scientific American pubblicò un suo articolo sugli esaflexagoni.
Gli amici che amano la matematica hanno indubbiamente capito che sto parlando di Martin Gardner, che alla non certo tenera età di 95 anni continua a lavorare alle edizioni definitive dei suoi libri, dopo aver deliziato almeno tre generazioni di matematici in erba e convinto molti di loro a studiare appunto matematica. Dire che Gardner non si è mai trovato a proprio agio con l’analisi matematica, come potete leggere in questo articolo del NYT… insomma, non buttatevi giù!

Ultimo aggiornamento: 2009-10-21 11:46

Questo mese il Carnevale della Matematica è ospitato da una new entry, Gianluigi Filippelli nel suo Science Backstage. Inutile aggiungere di andare a vedere cosa hanno scritto i soliti noti; meno inutile ricordare che il club non è affatto esclusivo, e chiunque voglia parlare di matematica può partecipare!

Ultimo aggiornamento: 2009-10-14 12:31

Ecco, non riesco mai a capire perché tutti quelli che sono così convinti che nel problema di Monty Hall sia indifferente cambiare porta non accettano mai la mia scommessa. Sono soldi da guadagnare facile, no? E allora perché non accettare questa mia bella scommessina, fatta alla luce del sole e verificabile indipendentemente da chiunque?
Scherzi a parte, mi sa che anche le più granitiche credenze si possano incrinare un poco quando uno debba iniziare a metterci su dei soldi; purtroppo però rimane questa schizofrenia per cui nonostante tutto non si cambia idea. Se ad ogni buon conto non avete davanti a voi un fondamentalista probabilistico, eccovi alcune possibilità per convincerlo che in effetti nel problema di Monty Hall in versione standard conviene cambiare porta.
(1) Ripetere più volte l’esperimento. Come nella scommessa da me proposta, se invece di un singolo evento se ne hanno parecchie decine tra loro indipendenti è facile accorgersi se in media la porta iniziale nasconde un’auto una volta su tre oppure una su due. Il buffo è che la Legge dei Grandi Numeri, per come è recepita dalla gente comune, è assolutamente errata; eppure dà loro molte più sicurezze della logica corretta di questo problema.
(2) Aumentare il numero di porte. Se invece di tre porte ce ne fossero un milione, voi scegliete la numero 1 e Monty apre tutte le altre tranne la 142857, oltre ovviamente alla 1, siete ancora così sicuri che l’auto non tia dietro la porta 142857? Visto che il caso è logicamente identico a quello con tre porte, la risposta dovrebbe essere la stessa.
(3) Mettersi a esplicitare i casi possibili. Per simmetria si può supporre di scegliere la porta numero 1; a questo punto si può clonare la famigerata scelta, enumerando i sei casi possibili in teoria, controllando quali sono i quattro possibili in pratica, e valutando le varie possibilità. Questa è la soluzione più debole, nel senso che è difficile convincere l’interlocutore che sia corretta; immagino che la colpa stia nell’abitudine di considerare tutti i casi come equiprobabili, e non accorgersi che i due sottocasi che si hanno quando l’auto era proprio dietro la porta da lui scelta sono appunto sottocasi e quindi la loro unione sia equivalente alla probabilità degli altri casi.
(4) Calcolare la probabilità a posteriori con il teorema di Bayes. Pur essendo l’unica che dà la certezza che la risposta sia corretta è quella meno preferita; l’evoluzione della razza umana non ha richiesto in effetti di impratichirci con le probabilità a posteriori.
(5) Prima di aprire una porta, Monty dice al concorrente “vuoi confermare la porta scelta, oppure cambiare con entrambe le altre porte? Io in ogni caso poi aprirò una tra due porte che non hai scelto inizialmente.” Se l’interlocutore riesce a convincersi che la formulazione è esattamente equivalente, allora la scelta è immediata.
Ho tralasciato apposta l’argomento “Monty può sempre aprire una porta con dietro una capra, qualunque sia la scelta del concorrente” perché, come vedremo tra poco, può essere fuorviante.
Detto tutto questo, non credo che se qualcuno è convinto di avere ragione gli si possa far cambiare idea; insomma, non perdeteci troppo tempo. In compenso, può essere simpatico vedere qualche scenario in cui tutto quello che ho scritto è falso. Naturalmente il trucco c’è: sto leggermente cambiando le ipotesi iniziali. Suppongo però sempre che la probabilità iniziale che l’auto si trovi dietro una porta sia 1/3 in ogni caso.
(1) Dopo che il concorrente ha scelto una porta e Monty ne ha aperta un’altra, arriva di corsa un’altra persona che conosce come funziona il gioco ma non sa quale sia stata la scelta del concorrente. Per costui le due porte sono assolutamente equivalenti, visto che non ha nessun dato su cui basarsi.
(2) Monty apre una porta davvero a caso tra le due che ha a disposizione, con il rischio di mostrare l’automobile e terminare il gioco con ignominia. In caso contrario, il concorrente può scegliere assolutamente a caso tra le due porte: però bisogna ricordarsi che alcune delle possibilità iniziali non sono più possibili a posteriori, e quindi la situazione è cambiata.
(3) Il concorrente sa che Monty ama la porta numero 3 e la apre sempre, se ne ha la possibilità. Se lui ha scelto la porta 1 e Monty apre la 2, è certo che l’auto stia dietro la 3, e quindi è obbligatorio cambiare scelta. Se invece apre la 3, è indifferente cambiare o no porta.
Qual è la morale di tutto questo? che bisogna sempre verificare molto attentamente le ipotesi, e non bisogna mai fidarsi troppo della propria intuizione!

Ultimo aggiornamento: 2009-10-12 07:00

Il paradosso di Monty Hall è stato uno dei pochissimi argomenti di matematica ad avere l’onore della prima pagina del New York Times, giusto per dare un’idea di quanta fama ha avuto negli anni ’90: probabilmente perché è così controintuitivo che molte persone, anche versate in matematica e probabilità, sbagliano la risposta. Per chi non lo conoscesse, ecco il testo: leggetelo molto attentamente, perché non c’è nessun trucco sotto ma la formulazione deve essere assolutamente precisa.
Sei alla fase finale dello show condotto da Monty Hall. Hai davanti a te tre porte; dietro una di esse c’è una Ferrari, dietro le altre due una capra. Tu scegli una porta, e vincerai quello che ci sta dietro. Dopo che hai fatto la tua scelta, Monty – che sa dov’è nascosta la capra – ti dice “Beh, oggi mi sento buono e ti voglio aiutare: invece che una probabilità su tre di vincere la Ferrari, te ne voglio dare una su due. Guarda: in effetti una delle porte che non hai scelto nascondeva una capra”. Apre una porta e mostra l’ovino belante. Monty prosegue: “Questa è la tua ultima possibilità: preferisci cambiare la tua scelta o rimani sulla porta iniziale?”
Per essere ancora più chiari, ecco alcune precisazioni. Dietro una delle tre porte c’è la Ferrari, e voi volete vincerla; Monty Hall sicuramente apre una porta con dietro una capra, tra le due che non avete scelto; se può scegliere quale porta aprire perché entrambe nascondono una capra, sceglie a caso; voi siete sicuri che vi faccia l’offerta in ogni caso. Ora, molte persone dicono che è indifferente cambiare porta oppure no; la verità è che cambiare porta raddoppia le vostre probabilità di vincita, da 1/3 a 2/3.
In tutti questi anni ho visto moltissime persone che non sono affatto convinti di questa cosa, e non sono mai riuscito a convincerli. La cosa strana è che però nessuno ha mai voluto fare una scommessa multipla al riguardo con me, chissà perché. Riprovo ancora una volta; sono sempre pronto ad accettare la sfida. Ecco la mia versione del gioco per la scommessa; se qualcuno non è d’accordo sul fatto che sia la stessa cosa, parliamone.
Prendiamo un’estrazione futura del lotto, a tua scelta. Ci sono 11 ruote – hanno aggiunto la Nazionale a quelle classiche – e quindi vengono estratti 55 numeri. I numeri da 1 a 30 sono nella classe “1”; quelli da 31 a 60 sono nella classe “2”; quelli da 61 a 90 sono nella classe “X”. Prima dell’estrazione, tu dici a che classe apparterrà ciascun numero; dopo l’estrazione, senza che tu sappia quali numeri sono effetivamente usciti, io ti dirò per ciascun numero una classe (diversa da quella che hai scelto) a cui il numero non appartiene; a questo punto, visto che per te è indifferente cambiare o no, ti propongo di puntare 4 euro su ciascuna tua scelta. Se non avevi indovinato, mi intasco i soldi; se invece avevi indovinato te li ridò assieme a 5 euro miei.
Come per i polli di Trilussa, su 55 giocate ne dovresti in media vincere 27 volte e mezzo, e quindi guadagnare 27,5 euro; se anche sei parecchio sfortunato e vinci solo 25 volte perdendo 30, hai ancora 5 euro di margine. C’è un piccolo problema legato al fatto che i numeri estratti su una ruota non sono statisticamente indipendenti, ma se la cosa ti disturba possiamo prendere i primi estratti di cinque estrazioni consecutive. Facciamo la scommessa? Anzi guarda, per dimostrarti che non c’è trucco né inganno ti posso dire in anticipo quale classe ti dirò essere perdente, a seconda della tua scelta e del numero effettivamente estratto; così puoi calocare direttamente anche tu quanti soldi vincerai…
– Tu hai detto 1, è uscito 2; ti dirò che X è perdente.
– Tu hai detto 1, è uscito X; ti dirò che 2 è perdente.
– Tu hai detto 1, è uscito 1; se il numero estratto è pari, ti dirò che X è perdente, altrimenti ti dirò che 2 è perdente.
– Tu hai detto 2, è uscito 1; ti dirò che X è perdente.
– Tu hai detto 2, è uscito X; ti dirò che 1 è perdente.
– Tu hai detto 2, è uscito 2; se il numero estratto è pari, ti dirò che 1 è perdente, altrimenti ti dirò che X è perdente.
– Tu hai detto X, è uscito 1; ti dirò che 2 è perdente.
– Tu hai detto X, è uscito 2; ti dirò che 1 è perdente.
– Tu hai detto X, è uscito X; se il numero estratto è pari, ti dirò che 2 è perdente, altrimenti ti dirò che 1 è perdente.
Sei pronto? Ti aspetto… (e la prossima settimana racconterò ancora qualcosa a riguardo)

Ultimo aggiornamento: 2009-09-26 22:44

Leggo dalla BBC che in Bulgaria per due volte consecutive sono stati estratti gli stessi sei numeri – anche se non nello stesso ordine – alla locale lotteria; le autorità bulgare, memori forse del tempo in cui stavano nel blocco sovietico e l’espressione “consenso bulgaro” aveva un significato negativo, hanno subito fatto partire un’inchiesta al riguardo. Ma è davvero così improbabile un simile avvenimento?
Non so tra quanti numeri venga estratta la sestina vincente in Bulgaria, quindi non posso calcolare la probabilità di avere per due volte di fila la stessa sestina, che poi è la stessa probabilità di riuscire a indovinare la sestina. Se prendiamo per buono quanto riportato dall’articolo, tale probabilità è una su 4 milioni, il che sembrerebbe davvero incredibile. Persino Terry Pratchett, che ama dire che in letteratura le cose che hanno una probabilità su un milione di funzionare riescono nove volte su dieci, probabilmente scuoterebbe la testa. D’altra parte, come ho già detto più volte, una sestina deve essere estratta, in fin dei conti, e siamo noi a vedere delle correlazioni: facili in questo caso (tutti i numeri uguali ai precedenti), più complicate in altri casi.
Fare delle stime della probabilità “generica” (lasciatemi per il momento passare il termine, ve lo spiego dopo) è un po’ difficile, ma ci provo lo stesso. Immaginiamo che ogni giorno, da una qualunque parte del nostro pianeta, ci siano 100 estrazioni simili al lotto bulgaro, nel senso di numero di distinti risultati possibili. Consideriamo di tutto: ad esempio lotterie con un milione di biglietti estratti dove vengono estratti 10 biglietti e potrebbero essere stati premiati due numeri consecutivi. Anche se fosse capitata una cosa del genere qualcuno avrebbe potuto gridare alla truffa, no? La stima mi pare abbastanza ragionevole; questo darebbe 36000 estrazioni ogni anno – arrotondiamo a 33000. In quindici anni di lotterie avremo raggiunto 500.000 estrazioni; un evento che capiti una volta su 4 milioni non è così improbabile, se facciamo mezzo milione di tentativi.
Avete notato il punto fondamentale del mio ragionamento? Una coincidenza specifica (due estrazioni (1) consecutive, (2) degli stessi numeri, (3) al lotto bulgaro, (4) la scorsa settimana) è molto improbabile; ma una “coincidenza generica” (due estrazioni con una facile relazione tra di loro da qualche parte nel mondo in un qualche momento) è molto più semplice da ottenere, perché non limitiamo anticipatamente il campo in cui vogliamo operare. Fortuna, sì; ma non così incredibile.
P.S.: la cosa più interessante, almeno a mio parere, non è tanto matematica quanto sociologica. Nella prima estrazione nessuno aveva indovinato la sestina; nella seconda ci sono stati ben 18 vincitori , tutta gente che probabilmente è convinta della “memoria dei numeri”. Inoltre i soldi che girano in Bulgaria sono pochi, pochissimi rispetto al nostro superenalotto: i 18 fortunati hanno infatti vinto poco più di 5000 euro a testa, il che significa che il montepremi per la sestina vincente era inferiore ai 100000 euro…

Ultimo aggiornamento: 2009-09-17 15:34