Principio del palomar

El principio del palomo cojo, 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.

La inspiración para el nombre del principio: aves en un palomar. Aquí n = 7 y m = 9.

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

${\displaystyle \lceil {\tfrac {n}{m}}\rceil }$  objetos, donde ${\displaystyle \lceil \dots \rceil }$  denota la función techo.

Además existirá otra caja que contendrá no más de

${\displaystyle \lfloor {\tfrac {n}{m}}\rfloor }$  objetos, donde ${\displaystyle \lfloor \dots \rfloor }$  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:

${\displaystyle \lceil 1000000/366\rceil =\lceil 2732,24\dots \rceil =2733}$ 

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 ${\displaystyle A}$  y ${\displaystyle B}$  son conjuntos finitos con ${\displaystyle \vert A\vert }$  > ${\displaystyle \vert B\vert }$  entonces no existe ninguna función inyectiva de A en B.

^[1]​Demostración por inducción

Paso base: Supongamos ${\displaystyle \vert B\vert =0}$ , es decir, ${\displaystyle B=\emptyset }$ . Entonces no existe ninguna función ${\displaystyle f\colon A\to B\,}$  , en particular no existe ninguna función inyectiva.

Hipótesis inductiva: ${\displaystyle f\colon A\to B\,}$  no es inyectiva para todo conjunto finito ${\displaystyle A}$  y para todo conjunto finito ${\displaystyle B}$ , que cumplan ${\displaystyle \vert A\vert >\vert B\vert }$ , y ${\displaystyle \vert B\vert <=n}$ , con ${\displaystyle n>=0}$ .

Tesis inductiva: Para ${\displaystyle \vert A\vert >\vert B\vert =n+1}$ , no existe una función ${\displaystyle f\colon A\to B\ }$  inyectiva.

Demostración del paso inductivo: Como A no es vacío, elijamos un ${\displaystyle a\in {\mbox{A}}\qquad }$ . Pueden ocurrir dos cosas. O bien existe otro elemento distinto a ${\displaystyle a}$  en A, llamémosle ${\displaystyle a'}$  que cumpla ${\displaystyle f(a)=f(a')}$ . O bien no existe tal elemento. Si el caso es que existe, la función f no es inyectiva y termina la demostración. Tomemos el caso que no existe, entonces f(a) tiene solo una preimagen que es a. Consideramos la función ${\displaystyle g\colon A-\{a\}\to B-\{f(a)\}\,}$  que coincide con f en todos los elementos de A − {a}. Ahora aplicamos la hipótesis inductiva pues ${\displaystyle B-\{f(a)\}}$  tiene n elementos y ${\displaystyle \vert A-\{a\}\vert =\vert A\vert -1>\vert B\vert -1=\vert B-\{f(a)\}\vert =n}$ , por lo tanto g no es inyectiva. Como g no es inyectiva, f 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).

Ejemplos

Ejemplo 1:

En una fiesta con 100 personas, algunos invitados se dan la mano y otros no, pero puedo estar seguro de que al menos dos han saludado al mismo número de gente. ¿Por qué?.

Este ejemplo está sacado del artículo "En matemáticas no hay paro" que he leído precisamente hoy. Pulsa en mostrar para ver cómo llegar a esto.

En el mismo artículo se explica la solución usando el principio del palomar:

Llevando el razonamiento a la fiesta: los invitados son palomas y sus saludos, palomares. Al ser un gesto recíproco, solo hay 99 saludos posibles para 100 invitados, con lo que dos se estrujarán en el mismo palomar numérico.

Creo que el periodista resumió un poco la respuesta del entrevistado ya que en un principio habría 100 saludos posibles (cada invitado puede saludar de 0 personas a 99) por lo que habría 100 palomares, tantos como palomas. Pero ciertamente al ser un gesto recíproco, solo hay 99 saludos puesto que si alguien ha dado 99 apretones de manos, no habrá nadie que no le haya apretado la mano a él por lo que la existencia del palomar "99" haría que no existiese el "0" así que ahora podemos aplicar el principio y deducir que 2 personas han saludado al mismo número de personas.

Ejemplo 2:

¡¡Hay 2 personas en el mundo que tienen exactamente el mismo número de pelos en la cabeza!! ¡¡Es más, seguro que podemos encontrar muchas más de 1000 personas con el mismo número de pelos en la cabeza!!

Ahora las palomas van a ser la humanidad y los palomares el número de pelos de la cabeza. Pero ¿cuántos pelos puede tener una persona en la cabeza? Si nos vamos a la Wikipedia, un adulto puede tener alrededor de un millón en la cabeza, pero contando barba, nariz, orejas, pelusillas casi invisibles y tal. Si nos quedamos con el cuero cabelludo, hay entre 100.000 y 150.000. Bueno, para no quedarnos cortos, por si hubiese alguien muy peludo vamos a considerar que las personas pueden tener hasta un millón de pelos en el cuero cabelludo. El número de pelos podría variar de 0 a un millón, y en estos palomares tenemos que meter los aproximadamente 6.000 millones de habitantes actuales de la tierra (vaya, hemos crecido, según Google vamos ya por 6.775.235.741). Aplicando el principio del palomar, tendríamos que de hecho deben de haber al menos unas 6.775 personas con exactamente el mismo número de pelos.

Bueno, algunos podrán decir que esto era obvio porque hay muchos calvos... sin ningún pelo en la cabeza. Bueno, puesto que el número de calvos totales en el mundo no debe de ser muy alto, podríamos haber hecho el mismo razonamiento considerando solo gente que tenga pelo y habríamos llegado también a una conclusión similar para gente con pelo.

Curiosidades

10 Curiosidades del principio del palomar en la vida real.

1. Por cada frase de 28 palabras en cualquier texto en español, por lo menos dos palabras comenzarán con la misma letra.

El abecedario español tiene 27 letras, por tanto, si tenemos 28 palabras, al menos 2 palabras van a empezar con la misma letra.

2. En la ciudad de Nueva York, hay dos personas que tienen la misma cantidad de pelos en la cabeza.

La cabeza humana puede contener hasta varios cientos de miles de pelos, con un máximo de unos 500.000 pelos. En comparación, hay millones de personas en Nueva York. En consecuencia, al menos dos de ellos deben compartir la misma cantidad de pelos en la cabeza.

3. Como mínimo, dos personas que lean este blog cumplen los años el mismo día.

Hay 366 posibles cumpleaños (incluyendo 29 de febrero en un año bisiesto) y este blog tiene más de 367 lectores. Por lo tanto, dos de vosotros habéis nacido el mismo día.

4. En un concierto con más de 800 personas, habrá dos personas que tendrán las mismas iniciales de su nombre y de su primer apellido.

Cada inicial puede tener una de las 27 letras del abecedario, lo que significa que hay 27 x 27 = 729 posibles combinaciones entre nombre y apellido. Si en un concierto hay más de 800 personas, consecuentemente, dos de ellas deben compartir las mismas iniciales de su nombre y de su primer apellido.

5. Si escoges cinco cartas de una baraja francesa estándar de 52 cartas, al menos dos serán del mismo palo.

Una baraja tiene 4 palos. Cada una de las cinco cartas puede pertenecer a uno de los cuatro palos, pero por el principio del palomar, dos o más deben pertenecer al mismo palo.

6. Si tienes 10 calcetines negros y 10 calcetines blancos y estás eligiendo calcetines al azar, sólo tendrás que elegir tres para encontrar un par que coincida.

De los tres calcetines, al menos dos serán del mismo color según el principio del palomar.

Otra forma de ver esto es pensando calcetín por calcetín. Si el color del segundo calcetín coincide con el primero, entonces hemos terminado. De lo contrario, los dos primeros calcetines ya cubren las dos posibilidades de color y necesitas sacar un tercer calcetín, que debe ser de uno de esos colores y formará un par que coincida.

7. Si escoges cinco números enteros al azar, del 1 al 8, entonces dos de ellos deben sumar hasta 9.

Cada número puede ser emparejado con otro para sumar nueve. En total, hay cuatro pares de este tipo: los números 1 y 8,2 y 7,3 y 6, y por último, 4 y 5.

Cada uno de los cinco números pertenece a uno de esos cuatro pares. Por el principio del palomar, dos de los números deben ser del mismo par que sume 9.

8. En cualquier fiesta con dos o más personas, debe haber al menos dos personas que tengan el mismo número de amigos. (asumiendo ser amigo es algo recíproco, es decir, que si x es un amigo de y, entonces y es un amigo de x.)

Imagina que una fiesta tiene a «n» gente. Entonces cada persona puede ser amigo de cualquier persona desde 0 a n-1 personas.

Caso 1: todo el mundo tiene al menos un amigo

Si todos tienen al menos un amigo, entonces cada persona tiene entre 1 y 1 amigo. Cada uno de los asistentes a la fiesta puede ser clasificado como uno de los valores n-1, y por lo tanto dos de los asistentes deben tener el mismo valor, es decir, el mismo número de amigos, por el principio del palomar.

Caso 2: alguien no tiene amigos

Si a alguien le falta algún amigo, entonces esa persona es un extraño para todos los demás huéspedes. Debido a que el amigo es recíproco, el valor más alto que cualquier otro puede tener es n – 2, es decir, que sería amigo de todos excepto de la persona que no tiene amigos. Por lo tanto, cada uno tiene entre 0 y n – 2 amigos.

Este medio de los n fiesteros puede ser clasificado como uno de los valores n-1, y por lo tanto dos de los fiesteros deben tener el mismo valor, o número de amigos.

9. Imagina que estás tratando de cubrir un tablero de ajedrez con piezas de dominó cada una que cubra exactamente dos cuadrados. Si quita dos esquinas diagonalmente opuestas, será imposible cubrir el tablero de ajedrez.

10. En un grupo de seis personas, siempre habrá tres personas que sean amigos o extraños mutuos. (asumiendo otra vez que ser amigo es recíproco: si x es un amigo de y, entonces y es un amigo de x.)

El problema se puede pensar geométricamente. Imagina a las seis personas como puntos y deja que un borde entre los puntos indique la amistad. Independientemente de cómo se dibuje el gráfico, queremos mostrar que hay un conjunto de tres puntos que están todos conectados o un conjunto de tres puntos que no tienen bordes de conexión.

Considera cualquier punto en particular. Hay otros cinco puntos a los que podría conectarse. Según el principio del palomar, el punto está conectado a al menos otros tres puntos o no está conectado a al menos otros tres puntos.

Caso 1: el punto está conectado a (al menos) otros tres puntos

Si alguno de estos puntos está conectado entre sí, entonces hemos encontrado un triángulo de tres amigos mutuos. (Estos dos puntos están conectados, además de que ambos están conectados al punto original).

De lo contrario, eso significa que ninguno de estos tres puntos está conectado y por lo tanto son mutuamente extraños. Esto sería un conjunto de tres puntos sin aristas.

Caso 2: el punto no está conectado a (al menos) otros tres puntos

Si alguno de estos puntos no está conectado entre sí, entonces hemos encontrado un triángulo de tres mutuos extraños. (Estos dos puntos no están conectados, además de que ambos no están conectados al punto original).

De lo contrario, eso significa que todos estos tres puntos están conectados y por lo tanto son amigos mutuos. Esto sería un conjunto de tres puntos con todos los bordes de unión.

Véase también

• Combinatoria
• Teoría de Ramsey
• Lema de Siegel

Referencias

1. Harry R. Lewis and Christos H. Papadimitriou; Elements of the Theory of Computation, Second Edition; Prentice-Hall, Englewood Cliffs, New Jersey, 1997

Bibliografí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 Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

•   Datos: Q188276