scienza deliri :: 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.
Dice qui che alcuni studiosi ritengono che Beethoven fosse negro. (Lucy Van Pelt)

[fork()]

[supermaz::post] [brullo nulla::post]
"quante persone devo invitare perchè ce ne possano essere 3 che non si conoscono o 3 che si conoscono?"

aspe aspe, la premessa è invitare persone A CASO, quindi non essere sicuro di conoscerle


ah ma allora non le stai invitando, perchè di norma inviti persone che conosci e quindi puoi fare una selezione.

quello che vuoi dire quindi è : "dato un insieme casuale di persone, qual è il numero minimo che fa sì che, di sicuro, che ne siano almeno 3 che non si conoscono fra loro o almeno 3 che si conoscono fra loro".

SAD PROTEINA - AUTOMATIC CLOWN

[vincibile::post]Ah! Voi generazione corrotta dite "tortura" perché foste allevati nel lassismo, la crapula e la gozzoviglia, dite "regime" perché sol conosceste l'anarchia e d'ogni licenza vi fate vanto, dite "graphic novel" ma son comunque fumetti. Giorno verrà ove Colui che è stato chiamato per giudicare la vostra schiatta, viziosa e sibarita, ridarà all'umana favella del vero il giusto significante.

[cotard::post]le manate vanno bene solo quando hai ragione, per sottolineare la possenza delle proprie argomentazioni.
[muffa::post]quando guardo i porni spero sempre che alla fine si sposino

[fork()]

comunque la teoria non vale per i negri (e per i calabresi), che si conoscono tutti (sempre)

[fork()]

[brullo nulla::post]
quello che vuoi dire quindi è : "dato un insieme casuale di persone, qual è il numero minimo che fa sì che, di sicuro, che ne siano almeno 3 che non si conoscono fra loro o almeno 3 che si conoscono fra loro".
esatto
supermaz è l'uomo giusto per qualsiasi persona che abbia dei gusti raffinati ed un cuore grande. (muffa)
una donna può campare ancora oggi facendo ciò che faceva la sua antenata del tremila avanti cristo, cioè la puttana o la sguattera o entrambe, mentre l'uomo purtroppo non può più vivere di guerra e di caccia, nè farsi giustizia con arco e frecce (scotto)
rebis è la ragazza della porta 80 accanto(}-{aiku)

Asphalto ChillEx | Vieni a giocare a L4D2!

[fork()]

quanti calzini devi pescare al buio se vuoi esser sicuro di pescarne due dello stesso colore? e se uno è bucato? ma le mutande le hai cambiate?

[fork()]

[Morella::post]quanti calzini devi pescare al buio se vuoi esser sicuro di pescarne due dello stesso colore? e se uno è bucato?
metà + 2
supermaz è l'uomo giusto per qualsiasi persona che abbia dei gusti raffinati ed un cuore grande. (muffa)
una donna può campare ancora oggi facendo ciò che faceva la sua antenata del tremila avanti cristo, cioè la puttana o la sguattera o entrambe, mentre l'uomo purtroppo non può più vivere di guerra e di caccia, nè farsi giustizia con arco e frecce (scotto)
rebis è la ragazza della porta 80 accanto(}-{aiku)

Asphalto ChillEx | Vieni a giocare a L4D2!

[fork()]

azpetta... non è più semplice dire "quante monete devi tirare per essere certo che 3 siano uguali o 3 siano diverse?"
perchè se la seconda è uguale alla prima, la terza potrà essere uguale o diversa, mentre la quarta dovrà essere uguale o diversa, etc, fino a 6.
(no, ne bastano 5, è diverso, anche perchè è impossibile che ce ne siano 3 diverse. si potrebbe però dire "che ci siano 3 cambiamenti (da testa a croce o viceversa) o 3 volte nessun cambiamento" e sarebbe uguale, no?
essi, perchè le transizioni in tutto sono 5 e quindi o ci sono tre cambiamenti di stato o se ce ne sono solo 2 allora ci sono almeno 3 noncambiamenti di stato)

[fork()]

[Morella::post]quanti calzini devi pescare al buio se vuoi esser sicuro di pescarne due dello stesso colore? e se uno è bucato? ma le mutande le hai cambiate?

il quesito completo è: nel cassetto ci sono 24 calzini, di cui 12 blu e 12 rossi, quanti ne devi pescare se sei al buio e vuoi essere sicuro che almeno due siano dello stesso colore?
la risposta è talmente una cagata che


niente, vedo che supermaz ci è cascato, ciao

[fork()]

[lilith::post]il quesito completo è: nel cassetto ci sono 24 calzini, di cui 12 blu e 12 rossi, quanti ne devi pescare se sei al buio e vuoi essere sicuro che almeno due siano dello stesso colore?
la risposta è tanto sei al buio cazzo ti fotte se sono spaiati

la morale, la storia, la geometria, la pace e la guerra non sono che fuffa - prikedelik

[fork()]

[lilith::post]
il quesito completo è: nel cassetto ci sono 24 calzini, di cui 12 blu e 12 rossi, quanti ne devi pescare se sei al buio e vuoi essere sicuro che almeno due siano dello stesso colore?
questo quesito è diverso da quello sopra
supermaz è l'uomo giusto per qualsiasi persona che abbia dei gusti raffinati ed un cuore grande. (muffa)
una donna può campare ancora oggi facendo ciò che faceva la sua antenata del tremila avanti cristo, cioè la puttana o la sguattera o entrambe, mentre l'uomo purtroppo non può più vivere di guerra e di caccia, nè farsi giustizia con arco e frecce (scotto)
rebis è la ragazza della porta 80 accanto(}-{aiku)

Asphalto ChillEx | Vieni a giocare a L4D2!

[fork()]

altro chiarimento:
per dire "4 persone si conoscono" nella formulazione del problema, nel caso in cui si conoscano A e B tra loro, e separatamente C e D tra loro, si considera siano "4 persone che si conoscono" (ovvero, nell'insieme esistono 4 elementi che hanno una relazione di conoscenza con un altro elemento dell'insieme)? oppure si intende un grafo connesso?

SAD PROTEINA - AUTOMATIC CLOWN

[vincibile::post]Ah! Voi generazione corrotta dite "tortura" perché foste allevati nel lassismo, la crapula e la gozzoviglia, dite "regime" perché sol conosceste l'anarchia e d'ogni licenza vi fate vanto, dite "graphic novel" ma son comunque fumetti. Giorno verrà ove Colui che è stato chiamato per giudicare la vostra schiatta, viziosa e sibarita, ridarà all'umana favella del vero il giusto significante.

[cotard::post]le manate vanno bene solo quando hai ragione, per sottolineare la possenza delle proprie argomentazioni.
[muffa::post]quando guardo i porni spero sempre che alla fine si sposino

[fork()]

lilith leggi e impara
[Morella::post]quanti calzini devi pescare al buio se vuoi esser sicuro di pescarne due dello stesso colore?
metà + 1
[lilith::post] nel cassetto ci sono 24 calzini, di cui 12 blu e 12 rossi, quanti ne devi pescare se sei al buio e vuoi essere sicuro che almeno due siano dello stesso colore?
3
supermaz è l'uomo giusto per qualsiasi persona che abbia dei gusti raffinati ed un cuore grande. (muffa)
una donna può campare ancora oggi facendo ciò che faceva la sua antenata del tremila avanti cristo, cioè la puttana o la sguattera o entrambe, mentre l'uomo purtroppo non può più vivere di guerra e di caccia, nè farsi giustizia con arco e frecce (scotto)
rebis è la ragazza della porta 80 accanto(}-{aiku)

Asphalto ChillEx | Vieni a giocare a L4D2!

[fork()]

[supermaz::post]questo quesIto è una zeppa
tentato suicidio, milano 199xUN TALE (guardando la sua macchina bruciata): «Lei che ne dice?»
IO: «Secondo me ha preso fuoco.»

[fork()]

[supermaz::post]metà + 1

prima avevi scritto metà +2

e poi non si poteva rispondere al quesito di morella, non avendo esplicitato di che colore fossero, potrebbero essere stati tutti di colore diverso

[fork()]

metà + 2 contemplava il contrattempo del calzino bucato
[lilith::post]potrebbero essere stati tutti di colore diverso
in quei casi si calcola per il worst case scenario che assumerebbe, in un mondo normale, che siano tutte coppie di calzini di colore non per forza uguale
supermaz è l'uomo giusto per qualsiasi persona che abbia dei gusti raffinati ed un cuore grande. (muffa)
una donna può campare ancora oggi facendo ciò che faceva la sua antenata del tremila avanti cristo, cioè la puttana o la sguattera o entrambe, mentre l'uomo purtroppo non può più vivere di guerra e di caccia, nè farsi giustizia con arco e frecce (scotto)
rebis è la ragazza della porta 80 accanto(}-{aiku)

Asphalto ChillEx | Vieni a giocare a L4D2!

[fork()]

nel qual caso bastava estrarli tutti più 1

[fork()]

non stiamo parlando dei cazzi stipati nel culo di tua madre
supermaz è l'uomo giusto per qualsiasi persona che abbia dei gusti raffinati ed un cuore grande. (muffa)
una donna può campare ancora oggi facendo ciò che faceva la sua antenata del tremila avanti cristo, cioè la puttana o la sguattera o entrambe, mentre l'uomo purtroppo non può più vivere di guerra e di caccia, nè farsi giustizia con arco e frecce (scotto)
rebis è la ragazza della porta 80 accanto(}-{aiku)

Asphalto ChillEx | Vieni a giocare a L4D2!

[fork()]

lol

vabbè comunque se volete la figa su asphalto dovete imparare a darle ragione

[fork()]

suppamaz sei solo invidioso che siamo più bravi di te con la settimana enigmistica

[fork()]

[lilith::post]se volete la figa su asphalto dovete imparare a darle ragione


lilizia, la figa in sè non è sufficiente, deve essere una figa intelligente. Almeno a livello di saper fare una rassegna stampa
ho troppa paura della solitudine per mettermi con una donna

[dulcamara::post]
PANCREAS AL POPOLO!!!!

[fork()]

ahahh questo thread ha preso una inaspettata deriva lollosa, resa ancora piú lollosa dal fatto che la deriva é iniziata da brullo
"L'asphalto diverte perché ospita discussioni simili a quelle che potrebbero avere dei semianalfabeti con degli aborigeni sulla letteratura americana del novecento, e il divertimento è assicurato sia dalla lontananza abissale dalla verità che ne esce fuori, sia dal fatto che i semianalfabeti si sentano hemingway in confronto agli aborigeni"
il pomeriggio dell'esistenza

[fork()]

[lilith::post]
vabbè comunque se volete la figa su asphalto dovete imparare a darle ragione
no, mi rifiuto di trattare le donne come esseri inferiori!
supermaz è l'uomo giusto per qualsiasi persona che abbia dei gusti raffinati ed un cuore grande. (muffa)
una donna può campare ancora oggi facendo ciò che faceva la sua antenata del tremila avanti cristo, cioè la puttana o la sguattera o entrambe, mentre l'uomo purtroppo non può più vivere di guerra e di caccia, nè farsi giustizia con arco e frecce (scotto)
rebis è la ragazza della porta 80 accanto(}-{aiku)

Asphalto ChillEx | Vieni a giocare a L4D2!

[fork()]

[BaLoR::post]questo thread ha preso una inaspettata deriva lollosa
sì guarda a tratti esilarante
no dico, che fatica però


[fork()]

sono un animo semplice
"L'asphalto diverte perché ospita discussioni simili a quelle che potrebbero avere dei semianalfabeti con degli aborigeni sulla letteratura americana del novecento, e il divertimento è assicurato sia dalla lontananza abissale dalla verità che ne esce fuori, sia dal fatto che i semianalfabeti si sentano hemingway in confronto agli aborigeni"
il pomeriggio dell'esistenza

[fork()]

Mezzo calzino modduppato 2 volte

[fork()]

[BaLoR::post]ahahh questo thread ha preso una inaspettata deriva lollosa, resa ancora piú lollosa dal fatto che la deriva é iniziata da brullo


del tutto inconsapevolmente, sigh, io volevo solo dei chiarimenti sulle assunzioni del problema.
SAD PROTEINA - AUTOMATIC CLOWN

[vincibile::post]Ah! Voi generazione corrotta dite "tortura" perché foste allevati nel lassismo, la crapula e la gozzoviglia, dite "regime" perché sol conosceste l'anarchia e d'ogni licenza vi fate vanto, dite "graphic novel" ma son comunque fumetti. Giorno verrà ove Colui che è stato chiamato per giudicare la vostra schiatta, viziosa e sibarita, ridarà all'umana favella del vero il giusto significante.

[cotard::post]le manate vanno bene solo quando hai ragione, per sottolineare la possenza delle proprie argomentazioni.
[muffa::post]quando guardo i porni spero sempre che alla fine si sposino

[fork()]

Brullo,
[brullo nulla::post] si intende un grafo connesso

forse l'ho spiegato male. Per la prima perplessita' ti hanno gia' risposto (confermo l'infelicita' del verbo invitare).
Dice qui che alcuni studiosi ritengono che Beethoven fosse negro. (Lucy Van Pelt)

asphalto FAQ
categorie Espandi/contrai