Il grande pennello di noi matematici
Supponiamo che alla prossima tutufest ci si chieda qual e' il numero minimo di asphaltiti da invitare, per fare in modo che almeno tre di essi si conoscano tra loro, oppure che almeno tre di loro non si conoscano.
Se il rapporto di conoscenza e' simmetrico (A conosce B se e solo se B conosce A), qualche disegnino e' sufficiente a capire che ne bastano 6; chi non si fida dei disegni immagini di essere in una stanza con altre 5 persone: e' evidente che ci saranno almeno tre persone che conosce o almeno tre persone che non conosce.
Paul Erdos, di cui ho gia' parlato, si e' messo a studiare problemi di questo tipo, ispirato da un breve papello scritto da Frank Plumpton Ramsey nel 1930 (per quelli a cui interessa si chiama On a problem of formal logic; Ramsey usa in effetti un'idea di teoria dei grafi per un problema di logica "about the decidability of (what is now called) Bernays–Schönfinkel–Ramsey class of first-order logic"), e ha dato il via a quella che e' oggi nota come Teoria di Ramsey.
Ora cerchiamo quattro persone, che si conoscono tutte o in cui nessuno conosce nessun altro: fidatevi se vi dico che le troverete certamente solo quando avrete almeno 18 invitati. Se ne vogliamo di piu', comincia il divertimento: per trovare cinque invitati disgiunti o totalmente congiunti bisogna organizzare una tutufest con non meno di 43 e non piu' di 49 invitati; il valore preciso al momento non e' noto, e per limitare in questo modo il valore esatto sono serviti 20 anni di ricerca (le malelingue dicono che in assenza di Erdos ne sarebbero serviti il doppio). Il numero preciso di invitati necessario a garantire 6 persone digiunte o totalmente congiunte e' anch'esso ignoto: si sa solo che si aggira tra 102 e 165.
La teoria di Ramsey studia, in poche parole, il numero minimo di enti che devono coabitare un sistema in modo tale che, quale che sia il loro "comportamento", un certo pattern si presenti (almeno n palle rosse in una cesta, almeno n mosche bianche in una popolazione, almeno un errore di HAL9000, almeno un azzurro su asphalto). In questa piacevole intercapedine della combinatorica si inserisce il lavoro di R. Graham, "holding the record for the largest number ever used in a serious mathematical proof". Per parlarne pero' serve una generosa cappella introduttiva.
E' credenza antica e comune che per maneggiare un ente astratto sia necessario dargli un nome, e l'aritmetica in quanto scienza esatta non fa eccezione: risale ad Archimede e al suo Arenario l'invenzione di un sistema atto a dare un nome al numero di granelli di sabbia di cui si compone l'Universo. Il pennello di archimede e' gia' grandino, dato che nelle notazioni moderne questa quantita' si esprime come 108 · 1016 (un numero che ha dieci milioni di miliardi di cifre); il numero di elettroni nell'Universo e' stato stimato da Arthur Eddington all'inizio del 1900, in circa 1080 (un numero di ottanta cifre).
La gestione gia' problematica di grossi interi lo e' diventata immensamente di piu' nell'era dei computer; limitandosi all'aritmetica degli interi (in effetti una delle poche che importa agli informatici, ma aspetto smentite focose da parte degli stessi), l'idea geniale che e' venuta a Don Knuth (un tizio famoso soprattutto agli appassionati di tipografia, scientifica e non) e' per sommi capi la seguente.
-Disponiamo di una operazione "addizione ripetuta", la moltiplicazione (3*2 = 2+2+2)
-Disponiamo di una operazione "moltiplicazione ripetuta", l'elevamento a potenza (2^3 = 2*2*2)
-Vorremmo disporre di una operazione "potenza ripetuta", da chiamare, diciamo, "↑↑" (e per estensione "↑" indichera' l'esponenziazione consueta), in modo che 2↑↑3 = 2↑(2↑2), 2↑↑4 = 2↑(2↑↑3) = 2↑(2↑(2↑2)) e cosi' via;
Si ha la possibilita' di generare numeri mastodontici gia' con numeri piccoli: 3↑↑3 = 7625597484987, e 3↑↑4 manda in overflow il kernel di Mathematica su un computer di media potenza. Knuth pero', che aveva numeri davvero grandi in testa, non si e' fermato qui: nulla infatti impedisce al Vero Matematico di chiedersi "perche' non procedere ancora?". L'operazione "m↑↑↑n" prevede ora di ripetere n volte l'operazione "↑↑" su m. In questo modo dunque 3↑↑↑2 = 3↑↑3 = 7625597484987 e 3↑↑↑3 significa ripetere 7625597484987 l'esponenziazione di 3 con se' stesso, ossia significa costruire una torre di 7625597484987 3 innestati.
Bevete un bicchiere d'acqua perche' siamo solo alla base del grattacielo: il numero che Graham e' stato costretto a chiamare in causa e' davvero(davvero↑↑↑davvero) piu' grande, essendo il sessantaquattresimo termine nella sequenza
g_0 = 4;
g_1 = 3↑↑↑↑4 (bisogna innestare 3↑↑↑3 "3");
g_n = 3↑(gn-1)3, intendendo con cio' che si devono mettere tra i due "3" un numero di "↑" pari a gn-1.
Non e' umanamente possibile stimare la grandezza di g_1, tanto esso esula dalle entita' che siamo soliti manipolare quotidianamente: il volume dell'universo osservabile espresso in unita' di Planck e' un numero di sole (circa) 185 cifre; risibile in confronto alla magnitudine di questo bizzarro mostro, e alla velocita' di crescita della successione dove e' inserito.
Divertente? Ora seguite questo. Lo trovo interessante perche' permette di settare quell'errore di parallasse cui accennavo prima, riguardo la distinzione grande-infinito. Un simpatico omino di nome Reuben Goodstein si e' inventato questo gioco (da alcuni chiamato "Achille raggiunto dalla Tartaruga") per scacciare quella operazione "intuitiva" di identificazione grande-infinito.
Diamo per noto che ogni numero intero puo' essere scritto in modo unico una volta fissata una qualche base b maggiore o uguale a 2; per esempio 137 = 128 + 8 + 1 in base 2 = 100 + 20 + 8 in base 10 = ...
Quello che si fa in generale fissata una base b e' scrivere il numero nella forma a0b0 + a1b1 + ... + akbk, dove ognuno degli aj e' strettamente minore di b.
scegliete a caso un numero naturale, diciamo 137. Scrivetelo in base 2, nella forma generale su descritta: in questo caso otterremo
e0 = 137 = 27 + 23 + 1
Ogni volta che compare un esponente maggiore o uguale a due, scriviamo anche quest'ultimo in base 2 nello stesso modo (7 = 4 + 2 + 1 = 2^2 + 2 + 1, 3 = 2 + 1 etc). Otterremo per e_0 la scrittura
e0 = 222+2+1 + 22+1 + 1
Ora sostituiamo ad ogni occorrenza di "2" un "3", e togliamo 1
e1 = 333+3+3 + 33+1 + 1 - 1 = 617673396284027
Scrivete ora 617673396284027 in base 3: scrivete ogni esponente in base 3, e ogni esponente di ogni esponente in base 3. L'operazione che state compiendo la chiamo "scrittura in base ereditaria 3". Sostituite ad ogni occorrenza di un "3" un "4", togliete 1 al risultato: nel nostro caso tale numero e'
13729595320261219429963801598162786434538870600286610|
81878892691837108636679531210424511928132290910995459|
2622782961716074243975999433287625148056582230115328
(vado a capo senno' si spana il layout); scrivete ora questo numero in base ereditaria 4, sostituite ad ogni 4 un 5, togliete 1... Vedete come la successione sembra crescere in fretta.
Dico sembra perche' non e' cosi'; per quanto cio' risulti incredibile si puo' dimostrare che comunque assegnato il valore arbitrario di e0,
esiste un indice N tale che eN=0.
Pazzesco? No: pure se questo teorema e' sufficientemente profondo e tecnico da evitarmi il tentativo di una riduzione scolastica, lo trovo interessante perche' esempio di serendipita': l'enunciato non e' dimostrabile nella consueta aritmetica dei naturali (e quindi se un giorno mi venisse la balzana idea di postare su asphalto un esempio di asserto non dimostrabile in PA credo sceglierei questo), e necessita di strumenti pesanti di induzione sui numeri transfiniti.
Se il rapporto di conoscenza e' simmetrico (A conosce B se e solo se B conosce A), qualche disegnino e' sufficiente a capire che ne bastano 6; chi non si fida dei disegni immagini di essere in una stanza con altre 5 persone: e' evidente che ci saranno almeno tre persone che conosce o almeno tre persone che non conosce.
Paul Erdos, di cui ho gia' parlato, si e' messo a studiare problemi di questo tipo, ispirato da un breve papello scritto da Frank Plumpton Ramsey nel 1930 (per quelli a cui interessa si chiama On a problem of formal logic; Ramsey usa in effetti un'idea di teoria dei grafi per un problema di logica "about the decidability of (what is now called) Bernays–Schönfinkel–Ramsey class of first-order logic"), e ha dato il via a quella che e' oggi nota come Teoria di Ramsey.
Ora cerchiamo quattro persone, che si conoscono tutte o in cui nessuno conosce nessun altro: fidatevi se vi dico che le troverete certamente solo quando avrete almeno 18 invitati. Se ne vogliamo di piu', comincia il divertimento: per trovare cinque invitati disgiunti o totalmente congiunti bisogna organizzare una tutufest con non meno di 43 e non piu' di 49 invitati; il valore preciso al momento non e' noto, e per limitare in questo modo il valore esatto sono serviti 20 anni di ricerca (le malelingue dicono che in assenza di Erdos ne sarebbero serviti il doppio). Il numero preciso di invitati necessario a garantire 6 persone digiunte o totalmente congiunte e' anch'esso ignoto: si sa solo che si aggira tra 102 e 165.
La teoria di Ramsey studia, in poche parole, il numero minimo di enti che devono coabitare un sistema in modo tale che, quale che sia il loro "comportamento", un certo pattern si presenti (almeno n palle rosse in una cesta, almeno n mosche bianche in una popolazione, almeno un errore di HAL9000, almeno un azzurro su asphalto). In questa piacevole intercapedine della combinatorica si inserisce il lavoro di R. Graham, "holding the record for the largest number ever used in a serious mathematical proof". Per parlarne pero' serve una generosa cappella introduttiva.
E' credenza antica e comune che per maneggiare un ente astratto sia necessario dargli un nome, e l'aritmetica in quanto scienza esatta non fa eccezione: risale ad Archimede e al suo Arenario l'invenzione di un sistema atto a dare un nome al numero di granelli di sabbia di cui si compone l'Universo. Il pennello di archimede e' gia' grandino, dato che nelle notazioni moderne questa quantita' si esprime come 108 · 1016 (un numero che ha dieci milioni di miliardi di cifre); il numero di elettroni nell'Universo e' stato stimato da Arthur Eddington all'inizio del 1900, in circa 1080 (un numero di ottanta cifre).
La gestione gia' problematica di grossi interi lo e' diventata immensamente di piu' nell'era dei computer; limitandosi all'aritmetica degli interi (in effetti una delle poche che importa agli informatici, ma aspetto smentite focose da parte degli stessi), l'idea geniale che e' venuta a Don Knuth (un tizio famoso soprattutto agli appassionati di tipografia, scientifica e non) e' per sommi capi la seguente.
-Disponiamo di una operazione "addizione ripetuta", la moltiplicazione (3*2 = 2+2+2)
-Disponiamo di una operazione "moltiplicazione ripetuta", l'elevamento a potenza (2^3 = 2*2*2)
-Vorremmo disporre di una operazione "potenza ripetuta", da chiamare, diciamo, "↑↑" (e per estensione "↑" indichera' l'esponenziazione consueta), in modo che 2↑↑3 = 2↑(2↑2), 2↑↑4 = 2↑(2↑↑3) = 2↑(2↑(2↑2)) e cosi' via;
Si ha la possibilita' di generare numeri mastodontici gia' con numeri piccoli: 3↑↑3 = 7625597484987, e 3↑↑4 manda in overflow il kernel di Mathematica su un computer di media potenza. Knuth pero', che aveva numeri davvero grandi in testa, non si e' fermato qui: nulla infatti impedisce al Vero Matematico di chiedersi "perche' non procedere ancora?". L'operazione "m↑↑↑n" prevede ora di ripetere n volte l'operazione "↑↑" su m. In questo modo dunque 3↑↑↑2 = 3↑↑3 = 7625597484987 e 3↑↑↑3 significa ripetere 7625597484987 l'esponenziazione di 3 con se' stesso, ossia significa costruire una torre di 7625597484987 3 innestati.
Bevete un bicchiere d'acqua perche' siamo solo alla base del grattacielo: il numero che Graham e' stato costretto a chiamare in causa e' davvero(davvero↑↑↑davvero) piu' grande, essendo il sessantaquattresimo termine nella sequenza
g_0 = 4;
g_1 = 3↑↑↑↑4 (bisogna innestare 3↑↑↑3 "3");
g_n = 3↑(gn-1)3, intendendo con cio' che si devono mettere tra i due "3" un numero di "↑" pari a gn-1.
Non e' umanamente possibile stimare la grandezza di g_1, tanto esso esula dalle entita' che siamo soliti manipolare quotidianamente: il volume dell'universo osservabile espresso in unita' di Planck e' un numero di sole (circa) 185 cifre; risibile in confronto alla magnitudine di questo bizzarro mostro, e alla velocita' di crescita della successione dove e' inserito.
Divertente? Ora seguite questo. Lo trovo interessante perche' permette di settare quell'errore di parallasse cui accennavo prima, riguardo la distinzione grande-infinito. Un simpatico omino di nome Reuben Goodstein si e' inventato questo gioco (da alcuni chiamato "Achille raggiunto dalla Tartaruga") per scacciare quella operazione "intuitiva" di identificazione grande-infinito.
Diamo per noto che ogni numero intero puo' essere scritto in modo unico una volta fissata una qualche base b maggiore o uguale a 2; per esempio 137 = 128 + 8 + 1 in base 2 = 100 + 20 + 8 in base 10 = ...
Quello che si fa in generale fissata una base b e' scrivere il numero nella forma a0b0 + a1b1 + ... + akbk, dove ognuno degli aj e' strettamente minore di b.
scegliete a caso un numero naturale, diciamo 137. Scrivetelo in base 2, nella forma generale su descritta: in questo caso otterremo
e0 = 137 = 27 + 23 + 1
Ogni volta che compare un esponente maggiore o uguale a due, scriviamo anche quest'ultimo in base 2 nello stesso modo (7 = 4 + 2 + 1 = 2^2 + 2 + 1, 3 = 2 + 1 etc). Otterremo per e_0 la scrittura
e0 = 222+2+1 + 22+1 + 1
Ora sostituiamo ad ogni occorrenza di "2" un "3", e togliamo 1
e1 = 333+3+3 + 33+1 + 1 - 1 = 617673396284027
Scrivete ora 617673396284027 in base 3: scrivete ogni esponente in base 3, e ogni esponente di ogni esponente in base 3. L'operazione che state compiendo la chiamo "scrittura in base ereditaria 3". Sostituite ad ogni occorrenza di un "3" un "4", togliete 1 al risultato: nel nostro caso tale numero e'
13729595320261219429963801598162786434538870600286610|
81878892691837108636679531210424511928132290910995459|
2622782961716074243975999433287625148056582230115328
(vado a capo senno' si spana il layout); scrivete ora questo numero in base ereditaria 4, sostituite ad ogni 4 un 5, togliete 1... Vedete come la successione sembra crescere in fretta.
Dico sembra perche' non e' cosi'; per quanto cio' risulti incredibile si puo' dimostrare che comunque assegnato il valore arbitrario di e0,
esiste un indice N tale che eN=0.
Pazzesco? No: pure se questo teorema e' sufficientemente profondo e tecnico da evitarmi il tentativo di una riduzione scolastica, lo trovo interessante perche' esempio di serendipita': l'enunciato non e' dimostrabile nella consueta aritmetica dei naturali (e quindi se un giorno mi venisse la balzana idea di postare su asphalto un esempio di asserto non dimostrabile in PA credo sceglierei questo), e necessita di strumenti pesanti di induzione sui numeri transfiniti.
Taggata:
Commenti
-
lamentatevi poi che non c'è figa su asphalto
-
ti sbagli maskone, 10^8 · 10^16 è infatti il numero minimo di puttane che bisognerà invitare alla festa per trovarne una disposta a prendere i soldi di eotvos
-
non ho capito niente, ma moddup per un asphalto piu' colto.
-
Nulla è matematicamente comparabile al numero di graham, neanche il numero di skewes. bisogna solo inchinarsi.
[Eötvös::post]
Ora cerchiamo quattro persone, che si conoscono tutte o in cui nessuno conosce nessun altro: fidatevi se vi dico che le troverete certamente solo quando avrete almeno 18 invitati.
Io ricordavo un esempio basato sulla presenza di n persone e la probabilità P che almeno due di n abbiano lo stesso compleanno (e già con n>=23 P >0,5). Se interessa posso andarlo a ricercare. -
[Marco::post]non ho capito niente, ma moddup per un asphalto piu' colto.
Appena ho punti, garantito. -
come, prego?
-
Non ho capito niente. Ma ho uppato.
Solo che, a questo punto, se si devono aprire topic così capzioni ed elitari, mi cimento pure io e vi sbatto una bella sugya dal Talmud e poi vediamo chi ci capisce qualcosa…[Eötvös::post]Knuth
-
[Rabbi Acher::post]mi cimento pure io e vi sbatto una bella sugya dal Talmud e poi vediamo chi ci capisce qualcosa…
1. Il capothread ha un intento comunque divulgativo;
2. La matematica è esteticamente più soddisfacente degli ebrei.
Trai le tue conclusioni. -
pigio chiudi tutto!
-
[escape_from_la_palma::post]la probabilità P che almeno due di n abbiano lo stesso compleanno
(364)₂₂/365²² = 0,49 e rotti (probabilità che 23 pisquani scelti a caso abbiano 23 compleanni diversi). ((364)₂₂ sarebbe una roba tipo 364 x 363 x 362 x ... x 343)[Eötvös::post]La gestione gia' problematica di grossi interi
io il mio grosso intero l'ìho sempre gestito benissimo
(le azzurrate a base di sfinteri sono in conflitto con lo spirito pasquale) -
[dulcamara::post]
non è difficile.
come, prego?
ipotizza uno stanzone contenente un gruppo di 366 persone.
converrai che almeno due tra esse saranno nate lo stesso giorno. (anzi, facciamo 367 includendo anche il 29 febbraio degli anni bisestili).
se il gruppo è formato da 2 persone, una volta stabilito il compleanno della prima, ci sono 365/366 modi in cui la seconda può avere un compleanno diverso.
p = probabilità che almeno 2 persone in un gruppo di n non abbiano lo stesso compleanno = 367 - 2 / 365 = 0,99726776
quindi 1 - p = probabilità che almeno 2 persone in un gruppo di n abbiano lo stesso compleanno = 0,0027322 (un po' meno del 3 per mille)
allora aumentiamo il gruppo di un elemento
367 - 3 / 365 = 0,99453551
p = 0,99726776 * 0,99453551 = 0,99181818
1 - p = 0,00818182 (e già siamo saliti all'8x1000, quindi quasi il triplo delle probabilità di prima, aggiungendo al gruppo una sola persona in più)
ovviamente puoi andare avanti calcolando il gruppo con 4 (p = 365/366 * 364/366 * 363/366 ), con 5 (p = 365/366 * 364/366 * 363/366 * 362/366) e con n (ultimo termine = 367 - n/366) e vedrai che quando arrivi ad n = 23 la probabilità negativa 1 - n è di pochissimo superiore a 0,5 (quindi maggiore del 50%).
-
[Rabbi Acher::post]vi sbatto una bella sugya dal Talmud e poi vediamo chi ci capisce qualcosa…
Fai, c'erano cose che non capivo anche quando compravo audioreview a 17 anni (come riconoscere i bassi setosi, per esempio).
Col tempo le ho imparate.
Cio' non significa che mi faro' circoncidere, ma magari imparero' una cosa in piu'. -
[Rabbi Acher::post]vi sbatto una bella sugya dal Talmud
VAI! (ho la famiglia in vacanza, quindi posso tranquillamente farmi le seghe su matematica e talmud, invece di dover mantenere questa facciata di onorabilità mascolina in cui sono costretto a far finta che la figa mi piaccia) -
Rabbi, parlaci di ghematria.
-
[gonzokampf::post]
2. La matematica è esteticamente più soddisfacente degli ebrei.
Trai le tue conclusioni (sono frocio)
-
[escape_from_la_palma::post]ovviamente puoi andare avanti calcolando il gruppo con 4 (p = 365/366 * 364/366 * 363/366 ), con 5 (p = 365/366 * 364/366 * 363/366 * 362/366) e con n (ultimo termine = 367 - n/366) e vedrai che quando arrivi ad n = 23 la probabilità negativa 1 - n è di pochissimo superiore a 0,5 (quindi maggiore del 50%).
tutto ció é molto figo e un po' paradossale, moddup virtuale -
In realtà tutte queste gabole di numeri sono inutili se non vengono poste al servizio del fine più alto dell’uomo: vincere soldi. Una variante truffaldina ricavata dal problema dei compleanni e già largamente praticata nella mezzaluna fertile è la seguente.
State facendo un lungo viaggio in macchina o in pullman con un vostro amico un po’ tonto, e gli dite: anziché romperci le palle, perché non facciamo una scommessina? Ci segniamo le ultime due cifre della targa di ogni auto che incrociamo; se nelle prime venti ce ne sono almeno due uguali vinco io e tu mi dai una rupia, se sono tutte diverse vinci tu e io ti do una rupia. Il giochino poi si può ripetere ad lib.
Se siete particolarmente figli di buona donna potete anche convincerlo che, dato che le combinazioni diverse sono cento e voi vi siete presi solo venti possibilità, avete una probabilità su cinque di vincere, per cui giocando alla pari gli state concedendo un bel vantaggione. In realtà le probabilità che le venti targhe siano diverse sono più o meno tredici su cento.
(potete inviarmi il 5% delle vincite)
-
[danci::post]
In realtà tutte queste gabole di numeri sono inutili se non vengono poste al servizio del fine più alto dell’uomo: vincere soldi. Una variante truffaldina ricavata dal problema dei compleanni e già largamente praticata nella mezzaluna fertile è la seguente.
State facendo un lungo viaggio in macchina o in pullman con un vostro amico un po’ tonto, e gli dite: anziché romperci le palle, perché non facciamo una scommessina? Ci segniamo le ultime due cifre della targa di ogni auto che incrociamo; se nelle prime venti ce ne sono almeno due uguali vinco io e tu mi dai una rupia, se sono tutte diverse vinci tu e io ti do una rupia. Il giochino poi si può ripetere ad lib.
Se siete particolarmente figli di buona donna potete anche convincerlo che, dato che le combinazioni diverse sono cento e voi vi siete presi solo venti possibilità, avete una probabilità su cinque di vincere, per cui giocando alla pari gli state concedendo un bel vantaggione. In realtà le probabilità che le venti targhe siano diverse sono più o meno tredici su cento.
(potete inviarmi il 5% delle vincite)
http://youtu.be/qB1_v67OnqU -
ahahah
-
ai ragione ha ridere c'è del fail nell'aria
-
e non di/da poco
-
la matematica è più facile da capire della figa.
-
modup
-
siete una manica di invertiti, ecco cosa
-
ahah me li vedo sti 4 disgraziati nel cercare un dialogo con la figa
-
ROGER THIS, ROGER THAT
PRONTO, PROONTO, PROOOOOOONTO?
MAH... NON CAPISCO -
MA CAZZO! volete forse dire che con la figa non bisogna parlarci???? e che cosa bisognerebbe farne, di grazia?