backup del Post

Il principio dei cassetti

La matematica è difficile? Dipende probabilmente da cosa intendete per “matematica” e da chi siete. Come per ogni attività, c’è chi la trova tanto astrusa da non sapere da dove iniziare e chi invece la sente come una cosa istintiva… a meno naturalmente che non si metta a leggere la dimostrazione dell’Ultimo Teorema di Fermat. Su questo blog il livello matematico è di base, almeno secondo me; immagino che per chi non mi legge sia comunque troppo alto. Ma in matematica non c’è il concetto “one size fits all”!

Detto questo, esistono alcune proprietà matematiche che, almeno nel loro enunciato, sono riconosciute come semplici da praticamente chiunque, ma che portano comunque a conseguenze non banali, che a prima vista possono sembrare complicate da risolvere e fanno quasi paura a chi non è “matematico dentro”. Oggi parlo di una di queste, sperando di mostrarvi come in fin dei conti non esisterà una via regia alla matematica, ma se si prende la strada giusta non si è costretti a scalare una parete di sesto grado. Il teorema, almeno in Italia, è noto come principio dei cassetti.

Innanzitutto enuncio il teorema, nella forma che ho imparato io.

Se abbiamo N+1 oggetti da mettere in N cassetti, allora possiamo essere certi che alla fine ci sarà almeno un cassetto che avrà almeno due oggetti al suo interno.

Qui stiamo facendo matematica, anche se di livello basilare, e pertanto le parole sono importanti, soprattutto quei due “almeno”. Potremmo per esempio avere due cassetti con due oggetti, oppure avere tutti gli oggetti in un unico cassetto: quello che conta è che non riusciremo mai, in qualunque modo facciamo la suddivisione, a fare in modo che ciascun cassetto abbia un solo oggetto, oppure non ne abbia nessuno. Vi serve la dimostrazione? Eccovela qua: notate che in un certo senso, anche se è per assurdo, è costruttiva e pertanto istruttiva. Prendiamo i primi N oggetti: ogni volta dobbiamo cercare un cassetto vuoto per inserirli, altrimenti avremmo un cassetto con due oggetti. Il guaio è che ce ne rimane in mano ancora uno, e da qualche parte dobbiamo pur metterlo!

Esiste anche una formulazione un po’ diversa del principio, enunciata da E. W. Dijkstra – non esattamente l’ultimo arrivato nel campo.

Dato un qualunque insieme non-vuoto di numeri reali, il valore massimo tra essi è almeno pari alla media dei valori.

(io aggiungerei una postilla “e può essere uguale se e solo se tutti i valori sono uguali”, ma all’atto pratico ce ne facciamo poco, quindi è inutile appesantire l’affermazione).

Prima di mostrare alcune delle svariate applicazioni del principio dei cassetti – applicazioni rubate da Mind Your Decisions, per la cronaca – vi lascio con un po’ di storia. Sembra che il principio sia stato esplicitato per la prima volta nel 1834 da Dirichlet, che lo battezzò col nome tedesco di Schubfachprinzip, per l’appunto “principio del cassetto”. Gli inglesi però preferiscono chiamarlo “pigeonhole principle”: ma il pigeonhole non è la piccionaia! Magari lo era nel 1577, data di prima attestazione del lemma: ma nel diciannovesimo secolo il termine era già usato nel senso di “cassetta per la posta”, nemmeno poi troppo diverso dalla cassettiera dirichletiana. Solo che si sa, le traduzioni sono sempre un po’ pericolose…

Ed ecco a voi dieci applicazioni del principio! D’accordo, molte non saranno il massimo dell’utilità, ma possono comunque servire in una serata da amici…

1. A Milano ci sono due persone che hanno lo stesso numero di capelli.
Il numero di capelli di un essere umano è sicuramente inferiore a 500.000. Poiché a Milano risiede più di un milione di persone, anche eliminando i calvi, ne consegue che ce ne devono essere almeno due con lo stesso numero di capelli. Anzi, si può dire di più: considerando la seconda forma del principio dei cassetti, si può affermare che esiste almeno un gruppo di tre persone con lo stesso numero di capelli.

2. Negli USA, tra i tacchini consumati il giorno del Ringraziamento ce ne sono due il cui peso è lo stesso al milligrammo.
Un tacchino pesa in media 7 chili, e il più grande tacchino mai visto sfiorava i 17 kg. Ci possono essere dunque al più 17 milioni di pesi diversi, calcolati al milligrammo, per i tacchini: ma si stima che negli USA si consumino 46 milioni di tacchini nel giorno del Ringraziamento, quindi sicuramente se ne troveranno due dello stesso peso. (Poi possiamo discutere se ha senso misurare il peso di un tacchino al milligrammo…)

3. Alla prima della Scala ci saranno almeno due persone con le stesse iniziali.
Ci sono ventisei lettere possibili per il nome e il cognome di una persona, per un totale di 26 × 26 = 676 possibilità complessive. La capienza della Scala è di 2013 posti, e alla prima si può immaginare che ci sia il tutto esaurito: sicuramente due persone avranno pertanto le stesse iniziali. (Notate come non sia possibile essere certi che ci siano quattro persone con le stesse iniziali, perché 2013/676 è leggermente minore di 3. Certo è improbabile pensare a frotte di Xavier Jacobelli e nomi simili, e io scommetterei senza problemi sull’esistenza di un quartetto, e se per questo anche di un quintetto, di persone con le stesse iniziali: ma un conto è una probabilità altissima, un conto la certezza.)

4. Scegliendo a caso cinque carte da un mazzo di 52, almeno due devono essere dello stesso seme.
I semi sono quattro…

5. Se in un cassetto :-) ci sono 10 calzini neri e 20 blu, e li si prende a caso, ne basta prendere tre per averne due dello stesso colore.
Gli insiemi da considerare sono i calzini neri e quelli blu, quindi due. Una volta arrivati al terzo calzino, entra in gioco il principio dei cassetti.

6. Scegliendo sei numeri tra 1 e 10, se ne potrà sempre trovare due la cui somma è 11.
Accoppiamo 1 e 10, 2 e 9, 3 e 8, 4 e 7, 5 e 6. Abbiamo cinque gruppi: se scegliamo sei numeri siamo sicuri che ci sarà almeno un gruppo di cui verranno scelti entrambi gli elementi. Ma visto che in ciascun gruppo la somma dei due elementi è 11, siamo a posto.

7. Scegliendo a caso cinque punti sulla superficie terrestre, possiamo dividere il pianeta a metà in modo che quattro dei punti siano sullo stesso emisfero (Un punto sulla linea di taglio si suppone far parte di entrambi gli emisferi)
Due punti sulla superficie della sfera determinano un cerchio massimo (occhei, se sono antipodali ci sono infiniti cerchi massimi che passano per essi: prendetene uno qualunque). Facendo un taglio che passi per quel cerchio massimo, rimangono altri tre punti. Sicuramente almeno due devono stare su una delle metà: aggiungendo i due punti sul cerchio massimo, quella mezza Terra avrà i quattro punti richiesti.

8. In una festa con almeno due persone, ci devono essere almeno due persone che hanno lo stesso numero di amici. (Supponiamo che la relazione “essere amico di” sia simmetrica: se A è amico di B, allora B è amico di A.)
Immaginiamo che ci siano n partecipanti alla festa. Ognuno di essi può essere amico di un numero di persone variabile tra 0 e n-1 (no, non si è amici di sé stessi!). Iniziamo a supporre che ciascuno abbia almeno un amico, e associamogli il numero di amici che ha: ci sono allora n persone a cui sono associati i numeri da 1 a n−1, e per il principio dei cassetti due di loro devono avere lo stesso numero. Cosa succede se c’è un imbucato, cioè uno senza amici? Beh, nessuno degli altri allora può avere n−1 amici, visto che non conosce l’imbucato; pertanto alle n persone si associano i numeri da 0 a n−2, che guarda caso sono di nuovo n−1.

9. Sempre con l’ipotesi di “simmetria della conoscenza”, in un gruppo di sei persone o ci sono tre persone ciascuna delle quali conosce entrambe le altre, oppure tre persone nessuna delle quali conosce le altre.
Il problema può essere definito geometricamente nel modo seguente: immaginiamo di avere sei punti e tracciare tutti i possibili segmenti che collegano due punti, colorandoli di rosso (conoscenza) o di blu (estraneità). Allora o c’è un triangolo coi tre lati rossi, oppure uno coi tre lati blu.
Partendo da un punto qualunque, consideriamo i cinque segmenti che partono da lui. Per il principio dei cassetti, ce ne devono essere almeno tre di uno stesso colore: senza perdita di generalità, possiamo supporre che questo colore sia il rosso. Prendiamo ora questi tre estremi, e consideriamo il triangolo formato da questi tre punti. Se uno dei lati è rosso, abbiamo un triangolo rosso con il punto iniziale; altrimenti abbiamo trovato un triangolo blu.

10. È impossibile inventare un algoritmo di compressione dati senza perdita di informazioni (“lossless”) che funzioni sempre, cioè a partire da un qualunque file in ingresso ne produca uno in uscita più corto.
Consideriamo i file di lunghezza k bit. Il loro numero è per definizione 2^k: ma i file di lunghezza tra 1 e k−1 sono solo 2^k−1, e pertanto dobbiamo avere due file che vengono “compressi” nello stesso file. Come facciamo allora a decomprimere il file compresso e scegliere il risultato corretto? (Lo stesso ragionamento spiega perché quando si crea una funzione hash occorre considerare la possibilità di collisioni, cioè di due elementi con la stessa chiave. Naturalmente una compressione “lossy”, cioè con perdita di informazione, è possibile; e – forse un po’ meno naturalmente – i file che usiamo di solito sono una parte così piccola del numero totale di file possibili che non è strano che zipparli funzioni nella pratica.)

Dopo tutte queste applicazioni teoriche, vi lascio con la storia dell’albergatore che riuscì a mettere otto persone in sette stanze, lasciandone una per stanza. L’albergatore iniziò a mettere temporaneamente le prime due persone nella stanza 1, proseguendo con la terza nella stanza 2, la quarta nella stanza 3, la quinta nella stanza 4, la sesta nella stanza 5 e la settima nella stanza 6. Finalmente poté tornare nella prima stanza, e chiedere all’ultima persona di lasciare la prima da sola, visto che la stanza 7 era pronta per lui. Semplice, no?