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. De
otra manera: si se toman trece personas, al menos dos habrán nacido el mismo
mes.
El primer enunciado del
principio se cree que proviene de Dirichlet en 1834 con el nombre de Schubfachprinzip
("principio de los cajones"). No debe confundirse con otro
principio sobre funciones armónicas,
también con el nombre de este autor.
Enunciado
Principio de distribución, del
palomar o del cajón de la paloma de Dirichlet. Sean m, n y p tres números naturales. Si se desean colocar np + m palomas 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 < np + 1 ≤ np + m.
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.
Aplicaciones
Aunque el principio del
palomar puede parecer una observación trivial, se puede utilizar para demostrar
resultados inesperados. Por ejemplo, hay por lo
menos 2 personas en Guatemala con el mismo número de pelos en la cabeza.
Demostración: la cabeza de una persona tiene en torno a 150.000 cabellos y
tener un millón de pelos requeriría de una cabeza gigante (nadie tiene un
millón de pelos en al cabeza). Asignamos un palomar por cada número de 0 a
1.000.000 y asignamos una paloma a cada persona que irá al palomar
correspondiente al número de pelos que tiene en la cabeza. Como en Guatemala
hay más de un millón de personas, habrá al menos dos personas con el mismo
número de pelos en la cabeza. De hecho se puede asegurar con seguridad que en
cualquier ciudad de más de un millón de personas hay más de 5 personas con el
mismo número de pelos en la cabeza (por el principio de Dirichlet
generalizado).
Enunciado general
Una versión generalizada de
este principio dice que, si n objetos discretos deben
guardarse en m cajas, al menos una caja debe contener no menos de
objetos,
donde 
denota la función techo.
Además existirá otra caja que
contendrá no más de
objetos, donde denota la función suelo.
Como ejemplo de aplicación en
una ciudad de más de un millón de habitantes habrá como mínimo 2733 personas
que hayan nacido el mismo día del año, ya que:
Donde se ha tenido en cuenta
que existen 366 posibilidades para la fecha de aniversario de una persona
contando la existencia de años bisiestos.
Formula Matemática
Técnicamente el principio del palomar, se corresponde con la aritmética modular, por lo
que se puede dirigir a dicho artículo para profundizar en aspectos técnicos.
Si 
son
conjuntos finitos con
entonces no existe ninguna
función inyectiva de A en B.
son
conjuntos finitos con entonces no existe ninguna
función inyectiva de A en B.
Demostración por inducción
Paso
base: Supongamos 
Entonces
no existe ninguna función 
, en particular no existe
ninguna función inyectiva.
Entonces
no existe ninguna función , en particular no existe
ninguna función inyectiva.
Usos y Aplicaciones
El principio del palomar es
encontrado a menudo en informática. Por ejemplo, las colisiones son inevitables
en una tabla hash porque el número de posibles valores que pueden tomar los elementos de
un vector exceden a menudo el número de sus índices. Ningún algoritmo de hashing,
sin importar lo bueno que sea, puede evitar estas colisiones. Éste principio
también prueba que cualquier algoritmo de
compresión sin pérdida que hace al
menos de un archivo de entrada otro más pequeño hará que otro fichero de
entrada sea más grande. (De lo contrario, dos archivos distintos podrían ser
comprimidos a un mismo archivo más pequeño y al ser restaurado habría
conflicto)
Ejemplos
Ejercicios Resueltos:1) Cuantas veces debemos lanzar un solo dado para obtener el mismo resultado al menos dos veces.
6 Lados Nidos
7 Lanzamientos Palomas
2) Unas oficina emplea 13 personas por lo que al menos 2 de ellas deben cumplir año durante el mismo mes determine las palomas y los nidos.
13 Personas Palomas
12 Meses Nidos
Referencias
1. ↑ Harry
R. Lewis and Christos H. Papadimitriou; Elements of the Theory of
Computation, Second Edition; Prentice-Hall, Englewood Cliffs, New Jersey,
1997
Biografía
·
Grimaldi, Ralph P. (1997)
Addison -Wesley Ibero Americana; Wilmington,Delawarw, E.U.A.
·
Guzmán, Miguel de (1986), Editorial Labor S.A.
Barcelona, España.
Enlaces externos
·
Weisstein, Eric W. «Dirichlet's Box Principle» (en inglés). MathWorld. Wolfram Research.
