Il principio dei cassetti (noto anche come principio della piccionaia o principio di Dirichlet) afferma che se si devono distribuire n oggetti in m contenitori, e n > m, allora almeno uno dei contenitori dovrà ospitare almeno due oggetti.
Enunciato Generale
Se si distribuiscono n oggetti in m contenitori, esiste almeno un contenitore che contiene almeno \lceil n/m \rceil oggetti (dove \lceil \cdot \rceil indica la funzione parte intera superiore).
Esempi Classici
- In un gruppo di 13 persone, almeno due sono nate nello stesso mese (13 persone > 12 mesi).
- Se hai 10 calzini neri e 10 calzini blu in un cassetto, devi prenderne almeno 3 per essere sicuro di averne una coppia dello stesso colore.
Significato Ingegneristico
- Informatica e Algoritmi (Hashing): È il motivo fondamentale per cui avvengono le collisioni nelle tabelle hash. Se lo spazio delle possibili chiavi è più grande dello spazio degli indirizzi di memoria della tabella, per il principio dei cassetti esisteranno sempre almeno due chiavi diverse che mappano allo stesso indirizzo.
- Teoria dell’Informazione e Compressione: Dimostra che non può esistere un algoritmo di compressione “perfetto” che riduca la dimensione di qualsiasi file. Se comprimiamo tutti i file di N bit in file di N-1 bit, per il principio dei cassetti almeno due file diversi di input produrrebbero lo stesso file compresso, rendendo impossibile la decompressione univoca (compressione lossless).
- Telecomunicazioni: Utilizzato per analizzare il sovraffollamento dei canali in sistemi ad accesso multiplo (come il Wi-Fi o le reti cellulari) quando il numero di utenti attivi supera il numero di risorse (time slot o frequenze) disponibili.
Vedi anche: Calcolo Combinatorio, Hash.