Principi de les caselles

El principi de les caselles, de Dirichlet o del colomar^[1][2] diu que si repartim n objectes en k caselles, i n és més gran que k, aleshores, necessàriament alguna de les caselles ha de rebre més d'un objecte.^[3] La idea en què es basa és molt senzilla: si s'han de col·locar tres coloms en dues gàbies, per força dos coloms han de compartir una mateixa gàbia.^[2]

L'origen del principi, almenys en el camp de les matemàtiques, és atribuït al matemàtic Johann Peter Gustav Lejeune Dirichlet el 1834. Segons Peter Flor, a la dècada de 1950 els especialistes en teoria de nombres de les universitats de Viena i Hamburg ja parlaven del principi de les caselles, referint-lo de vegades a Dirichlet. La denominació original en alemany fa referència a calaixos (Schubfachprinzip, on Schubfach vol dir calaix), però la traducció anglesa, pigeonhole principle, ha fet que en els exemples sovint es parli de pigeons ('coloms') i holes ('forats'), i això duu a la pintoresca denominació de principi del colomar.^[4][2]

Hi ha diverses versions més generals del principi que es poden enunciar de diferents maneres. Una versió diu que per k i m nombres naturals, si es distribueixen n = km + 1 objectes en k caselles, aleshores almenys una de les caselles tindrà com a mínim m + 1 objectes. Per a n i k arbitraris, això es generalitza de manera que almenys una casella tindrà ⌊n/k⌋ + 1 objectes, si k no és divisor de n, o n/k objectes, si k és divisor de n, a on els símbols ⌊·⌋ denoten la part entera.^[2]

Encara que pugui semblar trivial, el principi de les caselles és molt eficaç per a demostrar, en un conjunt amb condicions que afecten només el nombre d'elements, l'existència d'alguns elements que comparteixen les mateixes propietats.^[2]