|
|
|
Principio del palomar
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}
|
|
Página principal
Tabla de Contenidos
Noticias matemáticas
|
