Se mettete undici calzini in dieci cassetti, almeno un cassetto conterrà due calzini. Sembra troppo ovvio per meritare un nome, eppure questo principio, chiamato dei cassetti o della piccionaia, permette di dimostrare risultati per nulla evidenti e spiega alcuni limiti invalicabili dell'informatica: nessun programma comprime tutti i file, nessuna funzione hash è priva di collisioni.
Forma semplice
Principio dei cassetti: se n + 1 oggetti (o più) vengono distribuiti in n cassetti, almeno un cassetto contiene almeno due oggetti.
La dimostrazione è per assurdo: se ogni cassetto contenesse al più un oggetto, gli oggetti sarebbero al più n.
In termini di funzioni: se |A| > |B|, nessuna funzione da A a B è iniettiva. Due elementi diversi di A finiscono necessariamente sullo stesso elemento di B.
Forma generalizzata
Se N oggetti vengono distribuiti in k cassetti, almeno un cassetto contiene almeno ⌈N/k⌉ oggetti, dove ⌈x⌉ indica l'intero più piccolo maggiore o uguale a x.
Esempio: in un gruppo di 100 persone, almeno ⌈100/12⌉ = 9 sono nate nello stesso mese. Non si sa quale mese, né chi siano: si sa solo che devono esistere. È tipico del principio dei cassetti: dà dimostrazioni di esistenza non costruttive.
Esempi che sorprendono
Due numeri, uno multiplo dell'altro
Enunciato: scegliendo 51 numeri qualsiasi tra 1 e 100, ce ne sono sempre due di cui uno divide l'altro.
Idea: ogni numero si scrive in modo unico come 2ᵃ · d, con d dispari. Tra 1 e 100 i dispari possibili come d sono 50 (1, 3, 5, …, 99). Questi sono i cassetti. Con 51 numeri, due hanno la stessa parte dispari d: sono 2ᵃ · d e 2ᵇ · d con a < b, e il primo divide il secondo.
Con 50 numeri l'enunciato può fallire: i numeri da 51 a 100 non contengono coppie di questo tipo.
Punti in un quadrato
Enunciato: dati 5 punti in un quadrato di lato 1, ce ne sono due a distanza non superiore a √2/2 ≈ 0,707.
Idea: si divide il quadrato in 4 quadratini di lato 1/2. Con 5 punti e 4 quadratini, due punti cadono nello stesso, e la distanza massima in un quadratino di lato 1/2 è la sua diagonale, √2/2.
Sottoinsiemi con la stessa somma
Enunciato: dati 10 numeri interi distinti tra 1 e 100, esistono due sottoinsiemi disgiunti non vuoti con la stessa somma.
Idea: i sottoinsiemi non vuoti sono 2¹⁰ − 1 = 1023. La somma di un sottoinsieme non può superare 91 + 92 + … + 100 = 955, quindi le somme possibili sono al più 955. Ci sono più sottoinsiemi che somme, quindi due sottoinsiemi diversi hanno la stessa somma. Togliendo da entrambi gli elementi comuni si ottengono due sottoinsiemi disgiunti, ancora con la stessa somma.
Notate che la dimostrazione non dice quali siano: trovarli è un problema a sé.
Compressione senza perdita: un limite assoluto
Un programma di compressione senza perdita deve essere iniettivo: due file diversi non possono produrre lo stesso file compresso, altrimenti la decompressione non saprebbe quale restituire.
Contiamo. I file di esattamente n bit sono 2ⁿ. I file più corti, da 0 a n − 1 bit, sono 2⁰ + 2¹ + … + 2ⁿ⁻¹ = 2ⁿ − 1. Uno in meno. Quindi nessun compressore può ridurre la dimensione di tutti i file di n bit: almeno uno resta della stessa lunghezza o si allunga.
I compressori reali funzionano perché i file che ci interessano, testi, immagini, registrazioni, sono molto regolari e rappresentano una frazione minuscola di tutti i file possibili. Su dati già compressi o cifrati, che appaiono casuali, il guadagno è nullo o negativo. Per questo comprimere un archivio cifrato è inutile: se si vuole comprimere, va fatto prima di cifrare.
Hash, checksum e collisioni
Una funzione hash con uscita di 256 bit ha 2²⁵⁶ valori possibili, mentre gli input possibili sono infiniti. Per il principio dei cassetti le collisioni esistono sempre, in numero infinito. La sicurezza di un hash crittografico non sta nell'assenza di collisioni, ma nell'impossibilità pratica di trovarne una.
Lo stesso vale per checksum e cifre di controllo: una cifra di controllo decimale ha solo 10 valori, quindi in media una coppia su dieci di codici diversi ha la stessa cifra di controllo. Le cifre di controllo sono progettate per catturare gli errori più probabili, come una cifra sbagliata o due cifre scambiate, non tutti gli errori possibili.
Va distinto da un fenomeno affine ma diverso: il principio dei cassetti garantisce una collisione solo quando gli oggetti superano i cassetti, mentre la probabilità di collisione diventa alta molto prima, come mostra il calcolo probabilistico noto come paradosso del compleanno.
In sintesi
- Con più oggetti che cassetti, almeno un cassetto ne contiene due; con N oggetti e k cassetti, almeno ⌈N/k⌉.
- Il principio dimostra l'esistenza senza indicare quale oggetto o quale cassetto.
- La scelta dei «cassetti» giusti è la vera idea di ogni dimostrazione.
- Nessun compressore senza perdita può accorciare tutti i file di una data lunghezza.
- Hash e checksum hanno sempre collisioni: si progettano perché siano difficili da trovare o rare negli errori tipici.
