Principio dei cassetti

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à.