Principi de les caselles

En aquest exemple hi ha n = 10 coloms i k = 9 forats, per tant, hi ha d'haver un forat amb més d'un colom.

El principi de les caselles, de Dirichlet o del colomar 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. 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.

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.

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.

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.

Exemples

Agafant mitjons

Suposant que tinc una barreja de mitjons negres i blaus, quin és el mínim nombre de mitjons que he d'agafar per a poder garantir que en tinc dos del mateix color?

Considerem dues «caselles», k = 2, una per cada color. Pel principi de les caselles, només cal que agafi tres mitjons, n = 3, i ja tindré un color amb almenys 2 mitjons.

Encaixades de mans

Si hi ha n persones que es poden donar la mà entre elles (amb n > 1), el principi de les caselles prova que sempre hi haurà un parell de persones que hauran donat la mà a la mateixa quantitat de persones.

El nombre de persones a les quals algú dona la mà seran les nostres «caselles». Cada persona donarà a entre 0 i n − 1 altres persones, i això crea n caselles possibles. Ara bé, o bé la casella del '0' o bé la de 'n − 1' han de quedar buides (si una persona dona la mà a totes les altres, no és possible tenir una altra persona que no hagi donat la mà a ningú, i viceversa), i per tant tindrem n − 1 caselles per omplir. I com que hem de col·locar n persones en un màxim de n − 1 caselles, tindrem alguna repetició.

Comptant cabells

Podem argumentar que hi ha d'haver almenys dues persones a Barcelona amb el mateix nombre de cabells. Com que les persones tenen de mitjana uns 150.000 cabells, no és fora de lloc assumir (com a fita superior) que ningú no té més d'1.000.000 de cabells (prendrem k = 1 milió de caselles). Hi ha més d'1.000.000 de persones a Barcelona (n és més gran que 1 milió). Si assignem les persones a les caselles segons el seu nombre de cabells, hi ha d'haver almenys dues persones assignades a la mateixa casella quan fem l'assignació 1.000.001 (perquè tenen la mateixa quantitat de cabells). El principi només demostra l'existència d'una superposició, no diu res de la quantitat de superposicions (que és un tema que correspon a la teoria de la probabilitat).

Treballs de grup

En una classe de n = 25 alumnes, s'ofereixen k = 11 treballs, i cada alumne n'ha d'escollir un. El principi de les caselles ens diu que hi haurà almenys un treball que serà fet per com a mínim 3 alumnes. Per deduir-ho, com que 11 no és divisor de 25, el que s'ha de calcular és:

$\left\lfloor {\frac {n}{k}}\right\rfloor +1=\left\lfloor {\frac {25}{11}}\right\rfloor +1=\left\lfloor 2,27...\right\rfloor +1=2+1=3$

Suma en subconjunts

Qualsevol suconjunt de 6 elements del conjunt C = {1,2,3,...,9} ha de contenir dos elements que sumen 10. Etiquetarem les caselles amb els parells {1,9}, {2,8}, {3,7}, {4,6} i l'element {5}, un total de cinc caselles. Quan els sis elements (els elements del subconjunt de mida 6) es col·loquen en aquestes 5 caselles, posant cada element a la casella en què està etiquetat, com a mínim una de les caselles etiquetades amb dos nombres contindrà els dos nombres, i aquests sumaran 10.

Formulació forta

Siguin q₁, q₂, ..., q_n enters positius. Si

$q_{1}+q_{2}+\cdots +q_{n}-n+1$

objectes es distribueixen en n capses, llavors o bé la primera capsa conté almenys q₁ objectes, o la segona capsa conté almenys q₂ objectes, ..., o la capsa número n conté almenys q_n objectes.

Usos i aplicacions

El principi de les caselles sorgeix en la informàtica teòrica. Per exemple, les col·lisions són inevitables en una taula de hash perquè la quantitat de claus possibles és més gran que el nombre de posicions de la taula. Una funció resum, tant és com estigui feta, no pot evitar aquestes col·lisions.

El principi es fa servir per demostrar que qualsevol algorisme de compressió sense pèrdua, assumint que redueix la mida d'algunes entrades (com suggereix el nom), també farà que algunes altres entrades augmentin de mida. Altramnent, el conjunt de totes les seqüències d'entrada de longitud com a màxim L es podrien enviar al conjunt molt més petit de totes les seqüències de longitud menor que L, i això es faria sense col·lisions (perquè la compressió no té pèrdua), situació impossible segons el principi de les caselles.

Un problema destacat de l'anàlisi matemàtica és, fixat un nombre irracional a, provar que el conjunt de nombres donat per la part decimal dels múltiples enters de a (na on n és enter) és un subconjunt dens de l'interval [0, 1]. Hom es troba que no sembla fàcil trobar explícitament enters n i m tals que |na − ma| < e, on e > 0 és un nombre positiu arbitràriament petit i a és un nombre irracional. Però si es pren M tal que 1/M < e, pel principi de les caselles hi ha d'haver n₁, n₂ ∈ {1, 2, ..., M + 1} tals que n₁a i n₂a es trobin a la mateixa subdivisió de mida 1/M (només hi ha M trossos d'aquesta mida entre dos enters). En particular, es poden trobar n₁, n₂ tals que n₁a és a (p + k/M, p + (k + 1)/M), i n₂a és a (q + k/M, q + (k + 1)/M), per a certs p, q enters i k a {0, 1, ..., M − 1}. Llavors, es pot verificar que (n₂ − n₁)a és a (q − p − 1/M, q − p + 1/M). Això implica que la part decimal de na és més petita que 1/M que és més petit que e, on n = n₂ − n₁ o n = n₁ − n₂. Això demostra que 0 és un punt d'acumulació del conjunt. Ara es pot fer servir aquest resultat per demostrar el cas per a p a (0, 1]: amb aquesta n, si p ∈ (0, 1/M] ja hem acabat. Altrament p és a (j/M, (j + 1)/M] i, fent servir els símbols [·] per denotar la part decimal, si es pren k = sup{r ∈ N : r[na] < j/M}, s'obté |[(k + 1)na] − p| < 1/M < e.