Principio del palomar para niños
El principio del palomar, también llamado principio de Dirichlet o principio de las cajas, 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. A manera de ejemplo: 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.
Contenido
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 palomas.
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 la 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.
Formulación 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 
y 
son conjuntos finitos con 
> 
entonces no existe ninguna función inyectiva de en .
Demostración por inducción:
- Paso base: Supongamos
, es decir, 
. Entonces no existe ninguna función 
, en particular no existe ninguna función inyectiva. - Hipótesis inductiva: no es inyectiva para todo conjunto finito y para todo conjunto finito , que cumplan
, y 
, con 
. - Tesis inductiva: Para
, no existe una función 
inyectiva. - Demostración del paso inductivo: Como no es vacío, elijamos un
. Pueden ocurrir dos cosas. O bien existe otro elemento distinto a 
en , llamémosle 
que cumpla 
. O bien no existe tal elemento. Si el caso es que existe, la función 
no es inyectiva y termina la demostración. Tomemos el caso que no existe, entonces 
tiene solo una preimagen que es . Consideramos la función 
que coincide con en todos los elementos de 
. Ahora aplicamos la hipótesis inductiva pues 
tiene 
elementos y 
, por lo tanto 
no es inyectiva. Como no es inyectiva, no es inyectiva, que es lo que queríamos demostrar.
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. Este 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).
Véase también
En inglés: Pigeonhole principle Facts for Kids
- Combinatoria
- Teoría de Ramsey
- Lema de Siegel
