backup del Post

Teoremi e probabilità

Siete in pizzeria, e state aspettando che finalmente arrivi la vostra rinforzata doppia con mozzarella di bufala. Tanto per passare il tempo, il vostro amico tira fuori dieci monetine da cinque centesimi e vi dice che in qualunque modo voi disegniate dieci punti sulla tovaglietta di carta lui riuscirà a posizionare le monete in modo da coprire tutti e dieci i punti senza sovrapporre anche parzialmente nessuna moneta. Voi cominciate a pensarci un po’ su. Se disegnate i dieci punti ben distanti tra di loro, l’amico metterà una moneta sopra ogni punto. Se li disegnate troppo vicini, con una moneta riuscirà a coprirli tutti, e poi piazzerà le altre nove come vuole. Bisogna insomma trovare una via di mezzo: ma quale?

Non perdete tempo a cercare di trovare una configurazione di punti: non ne esiste nessuna. Questo problema è stato ideato da Naoki Inaba nel 2008, e ha una dimostrazione molto semplice da seguire, anche se non so a chi possa essere venuta in mente: io non ci sarei mai arrivato. La cosa più strana è che tale dimostrazione è di tipo probabilistico. Ma come? Un teorema è la quintessenza della certezza: come è possibile dimostrarlo usando le probabilità? Beh, il trucco è usarle nel modo corretto… Vediamo dunque come si dimostra il teorema “Dati dieci punti in un piano, è sempre possibile trovare un ricoprimento dei punti con dieci cerchi di raggio 1 che non si sovrappongono nemmeno parzialmente”. Naturalmente il raggio può essere fissato a una misura a piacere: basta ingrandire o rimpicciolire la configurazione dei punti

Per prima cosa cominciamo a ricoprire il piano con un numero infinito di cerchi, posti in un reticolo esagonale come nella figura qui a fianco. È immediato verificare la porzione del piano ricoperta dalle monete è il rapporto tra l’area di un cerchio e quella di un esagono regolare di apotema 1, vale a dire π/(6/√3) che è pari a circa 0,9069. Data ora una qualunque configurazione di dieci punti nel piano, consideriamo un ricoprimento del piano con un reticolo esagonale, come quello appena visto. Per ciascun punto i, consideriamo la variabile aleatoria X_i che vale 1 quando il punto i è ricoperto da un cerchio e 0 altrimenti. Il valore atteso di X_i, cioè la probabilità che il punto sia ricoperto da un cerchio, è E[X_i] = Pr(X_i = 1) ≈ 0,9069. Essendo i punti indipendenti tra loro, il valore atteso per il numero totale di punti ricoperti sarà la somma dei vari E[X_i], cioè circa 9,069. Consideriamo ora tutti i ricoprimenti possibili del piano con un reticolo esagonale di cerchi, come quello che abbiamo visto sopra. Se nessuno di questi ricoprimenti contenesse tutti e dieci i punti, la media di punti ricoperti potrebbe essere al più 9: ma noi sappiamo che è maggiore di 9. Questo significa, come spiega bene il principio dei cassetti, che deve esistere almeno un ricoprimento che contenga tutti i punti. La dimostrazione non è costruttiva, e quindi forse potete in effetti mettere in serie difficoltà il vostro amico, ma matematicamente parlando non lascia adito a dubbi.

La probabilità insomma si usa, ma in un senso per così dire tangenziale. D’altra parte, se rileggiamo il testo dell’affermazione che vogliamo dimostrare, noi non partiamo dal reticolo di cerchi, ma dalla configurazione di punti. Chi non è ancora del tutto convinto della cosa può anche leggere le risposte a questa domanda su Math StackExchange. Tra l’altro, non è noto quale sia il numero massimo di punti N che può essere ricoperto da N cerchi uguali non sovrapposti: l’articolo “Covering Points with Disjoint Unit Disks” dimostra che tale numero è compreso tra 13 e 45, e una forchetta così ampia è indice del fatto che il problema non è esattamente banale: però la dimostrazione di questo caso è così bella che si può perdonare questa pecca.