Il principio dei cassetti dimostra che una cosa esiste senza trovarla

Certezza a 367, testa o croce a 23

Il divario fra ciò che è garantito e ciò che è probabile è qui enorme, ed è ciò che rende sorprendente il problema del compleanno. Ventitré persone danno già il 50,7 per cento di probabilità che due condividano una data, e cinquantasette la portano al 99 per cento — eppure la certezza richiede ancora 367, perché una disposizione in cui tutti i compleanni differiscono resta possibile fino a quel punto. Il principio dei cassetti parla solo della colonna garantita e tace sull'altra. Ricorrervi quando si voleva una probabilità produce un enunciato vero e inutile; ricorrere alla probabilità quando serviva una garanzia produce un'affermazione che cade proprio sulla disposizione non considerata.

Prove di esistenza che nascondono la risposta

Una funzione di hash che trasforma un file qualsiasi in un numero fisso di bit ha più ingressi possibili che uscite, quindi le collisioni devono esistere — due file diversi con lo stesso digest — e il principio dei cassetti lo dimostra in una riga. Trovarne una è tutt'altra faccenda, e la sicurezza pratica di un hash poggia su quel divario: tutti sanno che le collisioni ci sono, e per una funzione sana nessuno ne produce. La stessa figura compare ovunque sia disponibile un argomento di conteggio: stabilisce se qualcosa è possibile e lascia intatta la ricerca. È un pregio quando serve sapere che una ricerca non è vana, ed è una frustrazione quando ci si aspettava un indirizzo.

Domande frequenti

Perché 366 e non 365?

Perché il 29 febbraio è un compleanno possibile e il principio deve reggere il caso peggiore. Usare 365 cassetti darebbe una garanzia a 366 persone che cade appena qualcuno del gruppo è nato in un giorno bisestile, e una garanzia che cade non è una garanzia. È questa la disciplina caratteristica del principio: ogni conteggio dev'essere il numero di cassetti concepibilmente utilizzabili, non quello abitualmente usato, e ogni ragionamento costruito sul caso tipico crolla proprio sull'esempio che qualcuno produrrà per metterlo alla prova.

Esiste una versione per cassetti disuguali?

Sì, ed è lo stesso argomento di conteggio scritto con più cura. Se ogni cassetto ha una propria capienza, ciò che conta è la capienza totale: supera la somma e qualche cassetto è oltre il proprio limite, benché il principio continui a non dire quale. C'è anche un cugino probabilistico, usato quando gli oggetti non sono collocati da un avversario ma a caso, e dà soglie molto più basse — il problema del compleanno è esattamente quel cugino, e la distanza fra 23 e 367 misura bene quanto renda l'ipotesi di casualità.