Principio dei cassetti

10 piccioni in 9 caselle

Il principio dei cassetti, detto anche legge del buco della piccionaia, afferma che se n+k oggetti sono messi in n cassetti, allora almeno un cassetto deve contenere più di un oggetto. Un altro modo di vedere il principio è che una piccionaia con m caselle può contenere al più m piccioni, se non se ne vogliono mettere più di uno in nessuna casella: un ulteriore volatile dovrà necessariamente condividere la casella con un suo simile. Formalmente, il principio afferma che se A e B sono due insiemi finiti e B ha cardinalità strettamente minore di A, allora non esiste alcuna funzione iniettiva da A a B.

Il principio dei cassetti è un esempio di un argomento combinatorio, che può essere applicato a molti problemi formali, compresi quelli relativi a insiemi infiniti che non possono essere messi in corrispondenza biunivoca. Nell'approssimazione diofantea l'applicazione quantitativa del principio all'esistenza di soluzioni intere di un sistema di equazioni lineari va sotto il nome di "lemma di Siegel".

Si ritiene che il principio sia stato esplicitato per la prima volta da Dirichlet nel 1834 col nome Schubfachprinzip ("principio del cassetto"). In alcune lingue, (ad esempio il russo) questo principio è pertanto noto come il "principio di Dirichlet", da non confondersi con il principio dello stesso nome sulle funzioni armoniche. In inglese, invece, si parla di pigeonhole principle, dove il "pigeonhole" si riferisce alle cassette postali aperte in uso in alcuni uffici e università.

Esempi

Anche se il principio dei cassetti può a prima vista sembrare un'osservazione banale, può essere usato per dimostrare risultati inaspettati, come ad esempio "A Roma abitano almeno due persone con lo stesso numero di capelli". Dimostrazione: una persona media ha circa 150000 capelli. È ragionevole assumere che nessuno ne abbia più di un milione: ma Roma ha più di un milione di abitanti. Se prepariamo un enorme schedario con un milione di cassetti, e associamo a ognuno di essi il numero di capelli corrispondente, e assegniamo ogni persona - o più pragmaticamente un loro documento - al cassetto corrispondente, ci dovranno essere due persone nello stesso cassetto, e quindi con lo stesso numero di capelli.

Un altro esempio è il caso in cui ci sono cinque persone che vogliono giocare a calcetto in un torneo, e quattro squadre presenti. Questo non sarebbe un problema se non fosse che nessuno dei cinque vuole giocare nella stessa squadra di uno qualunque degli altri quattro: ma per il principio dei cassetti è impossibile suddividerli tra le varie squadre.

Nel campo dell'informatica ci sono molti esempi pratici del principio dei cassetti. Si prenda ad esempio una tabella hash: le collisioni dei valori avvengono perché il numero di chiavi possibili è di gran lunga superiore a quello degli indici hash. Nessun algoritmo, per quanto sofisticato, potrà pertanto eliminare con certezza le collisioni. Allo stesso modo si dimostra che non può esistere un algoritmo di compressione senza perdita di informazioni "perfetto", che riduca cioè la dimensione di un file di una dimensione qualunque - o anche solo maggiore di un certo numero M di bit - datogli in input. Infatti i file composti da M+1 bit sono 2^M+1, ma la somma di tutti i possibili file con dimensione $1,2,3,\ldots ,M$ bit vale 2^M+1 - 2: quindi ci devono essere almeno due file in ingresso mappati sullo stesso file in uscita. Ma allora l'ipotesi che la compressione sia senza perdita di informazioni fallisce, dato che non si potrebbe distinguere tra i due file convertiti nello stesso file di output.

Nel testo di Grimaldi sono riportati altri esempi.

Generalizzazioni

Una versione generalizzata del principio afferma che se ci sono n oggetti discreti che devono essere allocati in m contenitori, allora ci sarà almeno un contenitore che conterrà almeno $\lceil n/m\rceil$ oggetti (il simbolo $\lceil \dots \rceil$ denota la parte intera superiore).

Una generalizzazione probabilistica del principio dei cassetti afferma che, se si mettono a caso n piccioni in una piccionaia da m posti con probabilità uniforme 1/m, allora almeno un posto della piccionaia conterrà più di un piccione con probabilità

$1-{\frac {m!}{(m-n)!\;m^{n}}}=1-{\frac {m^{\underline {n}}}{m^{n}}},$

dove $m^{\underline {n}}$ è un fattoriale decrescente. Per n = 0 e per n = 1 (con m > 0), questa probabilità è zero, mentre per n > m è uno, coincidendo così con l'ordinario principio dei cassetti.

In meccanica quantistica

Nel 2014 un gruppo di scienziati (Yakir Aharonov et al.) ha dimostrato che in meccanica quantistica il principio dei cassetti può essere violato, proponendo anche alcuni esperimenti interferometrici per una possibile verifica sperimentale.

Bibliografia

• (EN) Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: an Applied Introduction, 4ª ed., 1998, pp. 244–248, ISBN 0-201-19912-2.

Voci correlate

• Combinatoria
• Numero cardinale
• Teorema di Ramsey

Collegamenti esterni

• (EN) pigeonhole principle, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Principio dei cassetti, su MathWorld, Wolfram Research.