Principio del palomar
Esta afirmación aparentemente obvia, un tipo de argumento combinatorio, puede usarse para demostrar resultados posiblemente inesperados.
Dirichlet publicó su trabajo en francés y alemán, usando el término en alemán Schubfach o el término en francés tiroir.
El significado original de esos términos corresponde al español cajón, eso es, pieza móvil de diversos muebles, cerrada por sus costados y abajo, abierta por arriba, usada para guardar diversos elementos ordenadamente.
(Dirichlet escribió acerca de distribuir perlas entre esos cajones.)
Esos términos se transformaron en la palabra palomar en el sentido de un espacio pequeño en un escritorio, gabinete, o pared para guardar cartas o papeles, metafóricamente arraigado en estructuras que albergan palomas.
La sugerente (aunque no engañosa) interpretación de "casillero" como "palomar" ha encontrado su camino de regreso al alemán mediante una retrotraducción del principio del palomar como "Taubenschlagprinzip".
[2] El principio tiene varias generalizaciones y puede ser enunciado de distintas maneras.
En una versión más cuantificada: para los números naturales
conjuntos, entonces por el principio de casillas afirma que al menos uno de los conjuntos contendrá al menos
denotan las funciones suelo y techo, respectivamente.
Aunque la aplicación más directa es en conjuntos finitos (como palomas y cajas), también se utiliza con conjuntos infinitos que no pueden ser puestos en una correspondencia uno a uno.
Para esto es necesario la proposición formal del principio de casillas, cual es "no existe una función inyectiva cuyo codominio es más pequeño que su dominio".
Demostraciones matemáticas avanzadas como el lema de Siegel se construyen sobre este concepto más general.
Enunciemos el principio de la siguiente manera: Sean
casillas, alguna caja debe contener al menos
Asumamos por contradicción que cada casilla contiene como mucho
Esta demostración nos sirve para probar de manera análoga, el siguiente corolario: Si se desean colocar
casillas, alguna caja debe contener al sumo
entonces no existe ninguna función biyectiva de
personas seleccionadas aleatoriamente, ¿Cuál es la probabilidad que dos de ellos tengan el mismo cumpleaños?
El problema en sí tiene que ver principalmente con probabilidades contraintuitivas; sin embargo, también podemos decir por el principio que, si hay 367 personas en una habitación, hay una probabilidad del 100% de que haya dos personas que compartan fecha de cumpleaños, ya que solo hay 366 posibles cumpleaños de donde elegir (incluyendo el 29 de febrero, si es necesario).
Asumamos que una gaveta contiene una combinación de calcetines azules y blancos, cada uno puede ser usado en cualquier pie, y que se sacan calcetines de la gaveta sin mirar.
¿Cuál es el menor número de calcetines que se necesitan sacar para garantizar un par de un mismo color?
casillas, utilizando una por color), solo se necesitan sacar 3 calcetines de la gaveta (
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.
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.
El principio del palomar es encontrado a menudo en informática.
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).
