La matematica del distanziamento

Alla ripresa delle lezioni scolastiche le regole sul distanziamento interpersonale porteranno con sé l'importante questione della capienza della aule. Come cambierà la capienza massima di un'aula scolastica se tutti gli studenti e l'insegnante dovranno sempre trovarsi a non meno di 2 metri di distanza l'uno dall'altro? E come dovranno essere disposti i banchi e la cattedra del docente per rispettare le distanze e al tempo stesso permettere agevolmente le lezioni? Queste domande danno luogo a un problema matematico estremamente interessante: il problema dell'impacchettamento dei dischi. È estremamente interessante perché nella sua forma generale non è ancora stato risolto, pur avendo affascinato fra le migliori menti matematiche della storia. D'altra parte, in alcuni casi la soluzione esiste e combina in maniera molto intelligente ed elegante nozioni di base di geometria e trigonometria che sono note agli studenti del triennio delle scuole superiori.

Descrizione matematica

Immaginiamo un'aula come una regione R₀ del piano: qui ci interessa la pianta dell'aula, la sua forma bidimensionale, non la sua altezza o altre proprietà tridimensionali. Inoltre rappresentiamo ciascuno studente e l'insegnante con un punto. Le domande matematiche che ci poniamo allora sono:

Qual è il numero massimo di punti che posso selezionare in R₀ in maniera tale che ogni punto selezionato sia a distanza di almeno 2 metri da tutti gli altri punti selezionati?
Come sono fatte sono le possibili configurazioni di punti che soddisfano i vincoli di cui sopra? Ovvero, come devono essere disposti i punti selezionati in maniera tale da raggiungere la loro massima numerosità?

Rispondere a queste domande è equivalente a risolvere il seguente problema geometrico: data una regione R del piano e tanti dischi rigidi di raggio 1 (da questo momento dimentichiamoci dell'unità di misura, che sarà sempre il metro), qual è il numero massimo di dischi che R può contenere, in maniera tale che nessun disco ne intersechi altri? Come sono fatte le configurazioni che raggiungono il numero massimo di dischi in R? Possiamo pensare a queste configurazioni come efficaci "impacchettamenti" di dischi in R. Per mostrare l'equivalenza fra i due problemi, partiamo dalla regione iniziale R₀ e definiamo l'insieme R come l'unione di R₀con tutti i punti che hanno distanza minore o uguale a 1 da R₀. In altre parole, aggiungiamo ad R₀una "corona" di larghezza 1 attorno al suo bordo di R₀ (si veda Fig. 1).

Figura 1: il distanziamento dei punti di R₀ corrisponde al problema dell'impacchettamento in R.

Ora, due punti P e Q si trovano a distanza maggiore di 2 se, e solo se, il disco di centro P e raggio 1 non interseca il disco di centro Q e raggio 1. Inoltre, un punto P appartiene a R₀ se, e solo se, il disco di centro P e raggio 1 è interamente contenuto in R. Questo mostra che le configurazioni di punti che si trovano in R₀con distanze minori o uguali a 2 fra loro sono anche le configurazioni dei centri di dischi contenuti in R che non si intersecano fra loro (Fig. 1).

Impacchettamento nel piano

Risolvere un problema di impacchettamento di dischi in una regione R è in generale molto difficile. È però possibile trovare una soluzione completa nel caso in cui R sia l'intero piano. Cosa significa risolvere un problema di impacchettamento di dischi di raggio 1 nel piano? Certamente non si tratta di trovare il massimo numero di dischi contenuti nel piano, perché quel numero e ovviamente infinito. Si tratta invece di determinare le configurazioni di (infiniti) dischi nel piano che siano meglio impacchettate, ovvero che minimizzino gli spazi vuoti fra un disco e l'altro. Matematicamente parlando, vogliamo trovare le configurazioni di dischi che realizzino la massima densità, che definiamo come la proporzione fra l'area coperta dai dischi e l'area totale (1). Le domande che ci poniamo ora sono quindi:

Qual è la massima densità di impacchettamento di dischi nel piano?
Come sono fatte le configurazioni che realizzano la massima densità?

Questo è un problema classico di quella branca della matematica che si chiama geometria computazionale. La soluzione fu data dal matematico Joseph-Louis Lagrange (2) nel 1773: c'è un'unica configurazione di massimo impacchettamento, quella illustrata in Fig. 2. Calcoliamo la densità con l'aiuto della figura. Consideriamo l'esagono evidenziato: i suoi lati hanno lunghezza 2, mentre la lunghezza dell'apotema è √3. La sua area è quindi 12√3/2=6√3. All'interno dell'esagono troviamo un intero disco più 6 settori circolari che corrispondono a 1/3 di disco ciascuno. L'area totale coperta dai dischi all'interno dell'esagono è allora 3 volte l'area di un disco di raggio 1, ovvero 3π. La densità dei dischi dentro l'esagono è quindi

Visto che possiamo ricoprire l'intero piano con esagoni come quello mostrato in figura, risulta chiaro che la densità di questo impacchettamento è proprio la d appena calcolata. Per questo motivo questo impacchettamento viene chiamato impacchettamento esagonale.

Questa soluzione è piuttosto intuitiva e corrisponde alle nostre esperienze quotidiane (immaginiamo di dover disporre uno strato di arance in una cassetta della frutta), ma dimostrare in maniera matematica che nessun impacchettamento del piano può raggiungere densità maggiori di d non è cosa immediata. Lagrange mostrò che questa configurazione è la migliore fra tutte le configurazioni reticolari, ovvero tutte quelle configurazioni che risultano uguali a se stesse per opportune traslazioni del piano (3) ma si dovette attendere fino al 1940 per avere una dimostrazione che la densità d è la massima fra tutte le possibili configurazioni di dischi di raggio 1. Dobbiamo questo risultato al matematico ungherese Làszlò Fejes Tòth (1915-2005) (4). Esporremo più avanti una versione semplificata di questa dimostrazione (nel pdf al fondo dell'articolo)

Impacchettamento di un rettangolo

Il risultato sulla massima densità di impacchettamento di dischi nel piano ci dà un'idea di come possiamo iniziare a ragionare per risolvere il problema della disposizione ottimale di studenti in un'aula. Avendo dimostrato sopra che questo corrisponde a trovare il migliore, o i migliori, impacchettamenti di dischi in una regione R del piano (quella ottenuta "allargando di un metro" la regione R₀ che rappresenta l'aula), possiamo cercare di disporre quanti più dischi possibile nella configurazione esagonale vista sopra. Sebbene questa procedura ci porti a soluzioni quasi ottimali, cioè di densità vicina alla massima, per regioni R grandi, essa non dà necessariamente la soluzione ottimale nel caso di una regione finita. Il motivo è presto spiegato con un esempio. Prendiamo un rettangolo di dimensioni 6 × (2 + 2√3) ≈ 6 × 5,46: questo è stato costruito apposta per contenere al filo 8 dischi in configurazione esagonale, come nell'immagine di sinistra in Fig. 3. Tale configurazione è chiaramente ottimale. Ora però immaginiamo di restringere un poco il lato corto del rettangolo: se dovessimo insistere nel mantenere una configurazione esagonale, dovremmo eliminare una fila da 3 dischi e concluderemmo che, per esempio, in un rettangolo 6 × 5,40 si possono infilare al massimo 5 dischi di raggio 1. Ma questo è sbagliato: il numero corretto è 7, come si vede nell'immagine di sinistra della Fig. 3.

Figura 3: impacchettamenti ottimali in rettangoli leggermente diversi.

Potremmo pensare che la densità d dell'impacchettamento esagonale rappresenti un limite superiore per gli impacchettamenti in regioni limitate del piano, cioè, se R è una regione limitata, la densità di impacchettamento in R è minore o uguale a d. Purtroppo nemmeno questa affermazione è vera (vedi esercizio alla fine della dimostrazione del teorema). Ci sono solo dei no, dunque? Tutte le nostre intuizioni vengono smentite e il risultato di Lagrange sull'impacchettamento esagonale non serve a nulla nelle applicazioni pratiche? Per fortuna non è così. Si può dimostrare che d è una stima dall'alto in tutti i casi in cui R è un rettangolo. In realtà si sa molto di più: si conoscono gli impacchettamenti ottimali (e quindi la loro densità) per un'ampia famiglia di rettangoli, tutti quelli che contengono un numero di dischi non troppo grande. La brutta notizia – che però è fonte di grandissima curiosità per un matematico – è che non si conosce una formula o un algoritmo generale per determinare l'impacchettamento ottimale per un determinato rettangolo R. Questi problemi si risolvono (quando è possibile farlo) per tentativi, spesso con l'ausilio del computer. A mo' di esempio presento una tabella che dà il massimo numero di dischi di raggio 1 che si possono infilare in una famiglia di rettangoli in cui il rapporto fra lunghezza e larghezza è 0,7. La tabella è stata elaborata sulla base di dati forniti dal sito www.packomania.com (5).

Il problema dell'aula

Proviamo ora ad applicare quanto abbiamo visto al nostro problema iniziale, quello del massimo numero di studenti in un'aula. Avevamo schematizzato ciascuno studente con un punto. Questa è un'approssimazione troppo forte: anche volendo considerare solo la testa dello studente, che è la parte del corpo che va maggiormente protetta dalle goccioline potenzialmente virulente emesse dai compagni, approssimare una testa con un punto è certamente scorretto. Quella testa, inoltre, non starà sempre ferma, nemmeno nella situazione standard di studente seduto al suo banco: ruoterà, si muoverà un po'. Allora ha senso, per ogni studente, individuare una zona di sicurezza, in maniera che in qualunque posizione si trovi la testa di ciascuno studente nella sua zona, tutte le teste di tutti gli studenti si trovino comunque almeno a 2 metri di distanza l'una dall'altra. Questa zona di sicurezza potrebbe essere, ad esempio, un cerchio di raggio 25 cm (e quindi di mezzo metro di diametro). Dobbiamo quindi risolvere un problema completamente diverso da quanto abbiamo visto finora? No, perché è facile vedere che garantiremo che tutte le zone di sicurezza rimangano a non meno di 2 m le une dalle altre se, e solo se, risolveremo il problema dell'impacchettamento in R per dischi di raggio r = 1,25 (si veda Fig. 4.). Ma se sappiamo risolvere il problema dell'impacchettamento con dischi di raggio 1 in un rettangolo di dimensioni l × h, allora sappiamo risolvere il problema dell'impacchettamento con dischi di raggio r in un rettangolo di dimensioni lr × hr, poiché basta ingrandire tutto di un fattore r. Quindi la tabella data sopra può essere usata semplicemente moltiplicando tutte le lunghezze per r.

Figura 4: Zone di sicurezza (dischi pieni) e impacchettamento con dischi di raggio r = 1,25 in un'aula R₀.

Aggiungiamo un'altro elemento di realismo. All'interno dell'aula non possiamo considerare l'insegnante alla stregua di uno studente: l'insegnante dovrà avere a disposizione uno spazio maggiore, per essere meglio visibile dagli studenti, per scrivere alla lavagna, ecc. Diciamo allora che assegniamo al docente lo spazio di due dischi di raggio 1,25. Usando i dati precedenti, siamo quindi pronti per stilare una tabella piuttosto precisa per il numero massimo di studenti che possono essere sistemati in un'aula rettangolare la cui lunghezza sia circa 0,7 volte la larghezza. Prima di presentare la tabella ricordiamo che risolvere un problema di impacchettamento in un rettangolo R equivale a risolvere un problema di sistemazione di studenti in un'aula R₀, che nel nostro caso è un rettangolo i cui lati sono 2 metri più corti di quelli di R (si veda Fig. 4). La tabella che segue va usata così: data un'aula rettangolare le cui dimensioni sono più o meno in rapporto di 0,7 fra di loro, si trovi nella tabella la riga più in basso fra quelle per cui sia la larghezza che la lunghezza dell'aula sono maggiori o uguali, rispettivamente, alla larghezza e lunghezza minime indicate. Nella colonna di destra si leggerà il numero massimo di studenti (insegnante escluso) che possono essere sistemati in quell'aula. Per esempio, se si ha un'aula di 11,5 × 8 m, la riga più in basso per cui vale

è l'ottava riga, che corrisponde ad una capienza di 18 studenti più l'insegnante.

Scarica il pdf della Dimostrazione teorema Lagrange-Thue-Fejes Tòth

Note 1 Questa definizione non è del tutto corretta, dal punto di vista matematico, visto che stiamo parlando del rapporto di due aree infinite. Si può tuttavia rendere rigorosa tramite un processo di limite: prendiamo una regione S molto grande, estesa in tutte le direzioni, e calcoliamo la densità dei dischi in S, ovvero l'area coperta dai dischi dentro S diviso l'area di S. Poi facciamo il limite per S che diventa sempre più grande e tende a ricoprire l'intero piano. 2 Non tutti sanno che questo grande scienziato era in realtà italiano. Nacque a Torino nel 1736 con il nome di Giuseppe Luigi Lagrangia e morì a Parigi nel 1813. 3 Anche questa definizione è, evidentemente, vaga. Soprassiederò qui sulla definizione precisa. 4 In realtà il teorema fu annunciato un paio di volte, a cavallo del 1900, dal matematico norvegese Axel Thue (1863-1922), ma nessuna delle sue dimostrazioni viene considerata del tutto rigorosa. 5 Questo interessante sito contiene moltissimi dati e figure per gli impacchettamenti ottimali in rettangoli di varie forme, quadrati, cerchi, triangoli e molto altro. Le conclusioni che traiamo in questo articolo possono quindi essere tratte per varie altre forme.

-- Marco Lenci è Professore Ordinario di Fisica Matematica presso il Dipartimento di Matematica all'Università di Bologna Immagine box: airunique via Pixabay