Este interesante principio fue formulado por primera vez de manera formal por Peter Gustav Lejeune Dirichlet (1805-1859), y en consecuencia se conoce a veces como el principio de distribución de Dirichlet o el principio de la caja de Dirichlet.
Dirichlet contribuyó mucho en las matemáticas aplicadas y la teoría de números. Además realizó un trabajo fundamental con respecto a la definición de una función. Su trabajo enfatizaba la relación entre dos conjuntos de números y no pedía la existencia de una fórmula o expresión que relacionara los dos conjuntos.
Si m palomas ocupan n nidos y m > n, entonces al menos un nido tiene dos o más palomas en él.
Ejemplo
Una oficina emplea a 13 oficinistas, por lo que al menos dos de ellos deben cumplir años durante el mismo mes.
Los 13 oficinistas son las palomas y los 12 meses del año son los nidos. A cada paloma le corresponde un nido (el mes en que cumple años). Como hay más palomas que nidos, hay al menos un nido (mes) con dos o más palomas (oficinistas que cumplen en ese mes).
Ejercicios
Demuestre que si 8 personas están en una habitación, al menos dos de ellas cumplen años el mismo día de la semana.
Las palomas son las personas y los nidos son los días de la semana. Como hay 8 palomas y 7 nidos, hay algún nido con más de una paloma, es decir, hay algún día de la semana en el cual cumplen años dos (o más) de esas personas.
En una lista de 600.000 palabras, donde cada palabra consta de 4 o menos letras minúsculas, ¿pueden ser las 600.000 palabras distintas?
El número de palabras diferentes de 4 o menos letras es
274 + 273 + 272 + 27 = 551.880 (sumamos todas las palabras posibles de 4 letras, todas las palabras de 3 letras, todas las de dos letras y todas las de 1 letra.)
Las 551.880 palabras son los nidos y las 600.000 palabras de la lista son las palomas, por lo que al menos una palabra se repite.
Si una persona puede tener no más de 200.000 cabellos, ¿es posible que en una ciudad de 300.000 habitantes haya dos personas con la misma cantidad de cabellos en la cabeza?
Si, es seguro que existen dos personas con la misma cantidad de cabellos.
Las palomas son las 300.000 personas y los nidos son las cantidades de cabellos (0,1,2,…,200.000). A cada “paloma” le corresponde uno de esos “nidos”. Como hay más palomas que nidos, hay algún nido (cantidad) con más de una paloma (habitante).
¿Cuántas veces debemos tirar un sólo dado para obtener el mismo resultado
al menos dos veces?
Los “nidos” son los 6 resultados posibles (1,2,3,4,5,6). Las “palomas” son las tiradas, cada una de ellas “cae” en un nido.
La cantidad de palomas necesaria para que en alguno de los 6 nidos haya dos o más, es 7.
Alcanza con que el dado se tire 7 veces.
al menos tres veces?
Queremos que haya un nido con 3 o más palomas. Si hay 12 palomas (o menos) esto no está garantizado, pues podrían ubicarse dos en cada nido. Pero si hay 13 palomas está claro que tiene que haber 3 o más en algún nido.
||| || || || || ||
— — – — – –
1 2 3 4 5 6
Se necesitan 13 tiradas.
al menos n veces, para n >= 4?
Queremos que haya un nido con (al menos) n palomas. Podemos pensar qué cantidad máxima de palomas puede haber, sin la necesidad de que haya un nido con n palomas. Esto ocurre cuando hay n-1 palomas en cada nido, es decir 6(n-1) palomas. En este punto, si se agrega otra paloma, habrá n palomas en un nido.
1
n-1 n-1 n-1 n-1 n-1 n-1
— — — — — —
1 2 3 4 5 6
Se necesitan 6(n-1) + 1 tiradas.
Cualquier subconjunto de tamaño 6 del conjunto A={1,2,3,4,5,6,7,8,9} debe contener dos elementos cuya suma es 10. Justificarlo.
Los pares de elementos de A que suman 10 son: {1,9}, {2,8}, {3,7} y {4,6}. Estos son los nidos. Las palomas son los 6 números del subconjunto. Cada número va al “nido” correspondiente, por ejemplo, el 1 va a {1,9}, el 2 va al {2,8}, y así. Como 6 > 4, hay al menos dos números que van al mismo nido, es decir, hay dos números que suman 10. (Si uno de los números es el 5, no lo consideramos, de todas maneras hay 5 palomas y 4 nidos.)
1 2 8 3 7 4
{1,9}, {2,8}, {3,7} y {4,6}
andres1973