Principio del palomar

Si ${\displaystyle A}$ y ${\displaystyle B}$ son conjuntos finitos con ${\displaystyle \vert A\vert }$ > ${\displaystyle \vert B\vert }$ entonces no existe ninguna función biyectiva de ${\displaystyle A}$ a ${\displaystyle B}$.

Demostración por inducción:[3]

• 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 biyectiva.
• Hipótesis inductiva: ${\displaystyle f\colon A\to B\,}$ no es biyectiva 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 \leq n}$, con ${\displaystyle n\geq 0}$.
• Tesis inductiva: Para ${\displaystyle \vert A\vert >\vert B\vert =n+1}$, no existe una función ${\displaystyle f\colon A\to B\ }$ biyectiva.
• Demostración del paso inductivo: Como ${\displaystyle A}$ no es vacío, elijamos un ${\displaystyle a\in {\mbox{A}}}$. Pueden ocurrir dos cosas. O bien existe otro elemento distinto a ${\displaystyle a}$ en ${\displaystyle 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 ${\displaystyle f}$ no es biyectiva y termina la demostración. Tomemos el caso que no existe, entonces ${\displaystyle f(a)}$ tiene solo una preimagen que es ${\displaystyle a}$. Consideramos la función ${\displaystyle g\colon A-\{a\}\to B-\{f(a)\}\,}$ que coincide con ${\displaystyle f}$ en todos los elementos de ${\displaystyle A-\{a\}}$. Ahora aplicamos la hipótesis inductiva pues ${\displaystyle B-\{f(a)\}}$ tiene ${\displaystyle 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 ${\displaystyle g}$ no es biyectiva. Como ${\displaystyle g}$ no es biyectiva, ${\displaystyle f}$ no es biyectiva. ${\displaystyle \blacksquare }$

El problema de cumpleaños pregunta, para un conjunto de ${\displaystyle n}$ 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 fechad de cumpleaños, ya que solo hay 366 posibles cumpleaños de donde elegir (incluyendo el 29 de febrero, si es necesario).

Asumamos que un 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? Usando el principio de casillas (${\displaystyle m=2}$ casillas, utilizando una por color), solo se necesitan sacar 3 calcetines de la gaveta (${\displaystyle n=3}$ objetos). Se pueden tener tres de un solo color, o se puede tener dos de unos y uno de otro.

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