Principio de la caja de Dirichlet

Principio del palomar :

-El principio del palomar, también llamado principio de Dirichlet, establece que si n palomas se distribuyen en m palomares, y si n > m, entonces al menos habrá un palomar con más de una paloma. Otra forma de decirlo es que m huecos pueden albergar como mucho m objetos si cada uno de los objetos está en un hueco distinto, así que el hecho de añadir otro objeto fuerza a volver a utilizar alguno de los huecos.

Principio de distribución, del palomar o del cajón de Dirichlet. Sean m, n y p tres números naturales. Si se desean colocar np + m objetos en n cajas, alguna caja debe contener al menos p + 1 objetos.

Demostración. Si cada caja contiene como mucho p objetos, el número total de objetos que podemos colocar es np <>

En su versión más simple, este principio dice que no puede existir una aplicación inyectiva entre un conjunto de m elementos y otro de n elementos, si m > n. Equivalentemente, si se desean colocar m objetos en n cajas, con m > n, al menos una caja debe contener al menos 2 objetos.

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:

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

2-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?

3-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?

4-¿Cuántas veces debemos tirar un sólo dado para obtener el mismo resultado?

a) al menos dos veces.

b) al menos tres veces.

c) al menos n veces, para n >= 4.

Respuestas correctas a los ejercicios:

1-

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.

2-

El número de palabras diferentes de 4 o menos letras es
27⁴ + 27³ + 27² + 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.

3-

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

4-

a)

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.

b)

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.

c)

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.