El Principio del Palomar

Un teorema muy famoso en matemáticas es el Principio del Palomar. Su enunciado puede reducirse a términos comprensibles por todo el mundo y parece muy intuitivo y lógico. Además proporciona maravillosos resultados sorprendentes para los ojos de cualquiera que no sepa el razonamiento que hay detrás. Pues bien, el teorema viene a decir algo así como:

Si se distribuyen $n$ palomas en $m$ palomares y $n>m$ entonces hay un palomar que alberga dos o más palomas.

Es lógico, ¿verdad?, la peor situación es aquella en la que en cada palomar haya una paloma, pero aún así al haber más palomas que palomares tiene que sobrar al menos una paloma, y al meterla en algún otro palomar, al ya albergar a otra paloma, tendrá ahora dos. Parece que es comprensible. Ahora veamos brevemente el enunciado en términos matemáticos y su demostración.

$\text{Teorema (Principio del Palomar).}$ Sean $X$ e $Y$ dos conjuntos finitos con $|X|>|Y|.$ Entonces no existe ninguna función inyectiva de $X$ en $Y.$

Haremos la demostración por inducción.

1. Si $|Y|=0$ entonces $Y=\emptyset$ y en realidad no tiene sentido plantearse el problema. ¿Cómo hacemos para meter $n$ palomas en $0$ palomares? Por tanto hagámoslo para el caso $|Y|=1.$ En este caso $Y=\left\lbrace y \right\rbrace.$ Así, si $n=|X|>1$ podemos escribir $X=\left \lbrace x_1,x_2,\ ..., x_n \right\rbrace.$ Vayamos asignándoles imágenes a los elementos de $X:$ $f(x_1)=y$ dado que es la única opción que tenemos. Ahora, para que $f$ sea inyectiva, $x_2$ tendríamos que llevarlo en un elemento de $Y$ distinto de $y.$ Como no hay, la única opción para $f$ es que $f(x_2)=y$ y por tanto $f$ no puede ser inyectiva.


2. Ahora supongamos que si $X$ e $Y$ son dos conjuntos finitos y $|X|=n>m=|Y|$ entonces no puede haber funciones inyectivas de $X$ en $Y,$ es decir, toda función de $X$ en $Y$ es no inyectiva. Consideremos ahora $A$ y $B$ conjuntos con $|A|>n+1=|B|$ y una función $f$ de $A$ en $B.$ Sea $a$ un elemento de $A.$ Para $a$ pueden ocurrir dos cosas: o bien existe otro elemento $a'$ de $A$ tal que $f(a)=f(a'),$ o bien no existe. Si existiese entonces la función no sería inyectiva y habríamos terminado. Si no existiese entonces podemos considerar $X=A\setminus a$ e $Y=B\setminus f(a),$ teniendo $|X|=|A|-1>|B|-1=|Y|,$ es decir, $|Y|=n.$ Si pensamos en $f$ restringida a $X$ entonces $f:X \longrightarrow Y$ es una función como las de nuestra hipótesis de inducción, de manera que no es inyectiva, y por tanto $f:A \longrightarrow B$ tampoco lo es y hemos terminado.

Los problemas que requieren la ayuda del principio del palomar son muy curiosos y a la vez muy difíciles de resolver. Lo último que vamos a ver en el post son algunos de estos ejemplos.

Hay al menos dos personas en Manhattan que tienen la misma cantidad de pelos en la cabeza. Esto es cierto precisamente por este resultado: en Manhattan viven cerca de $1,6$ millones de personas, y normalmente no se suelen tener de media más de $150.000$ pelos en la cabeza. Dado que $1,6$ millones $> 150.000$ entonces al menos dos personas en Manhattan tienen que tener la misma cantidad de pelos en la cabeza.

Vamos a demostrar que si pintamos todo el plano $\mathbb{R}^2$ con dos colores de forma que a cada punto le asignamos un color (por ejemplo blanco o negro) entonces hay al menos dos puntos del mismo color a distancia $1.$ A primera vista parece un problema complicado, pero para resolverlo no hace falta más que fijarse en un triángulo equilátero de lado $1$ en el plano. Si pintamos dos de sus vértices, cada uno de un color distinto entonces al tercero habremos de asignarle un color. Si lo pintamos de blanco entonces estará a distancia $1$ del vértice que ya habíamos pintado de blanco. Si por el contrario lo pintamos de negro, estará a distancia $1$ del que ya habíamos pintado de negro. Es decir, estamos utilizando el principio del palomar con $3$ palomas, que son los puntos, y $2$ palomares, que son los colores.

En este ejemplo vamos a demostrar cómo es imposible poner $5$ puntos en un triángulo equilátero de lado $2$ sin que haya al menos dos a distancia menor o igual que $1.$ Si dividimos nuestro triángulo en $4$ triángulos equiláteros de lado $1,$ podemos ver que en el peor de los casos podemos poner un punto en cada triángulo y el quinto, lo pongamos donde lo pongamos, va a estar a distancia menor o igual a $1$ de alguno de los demás. De nuevo estamos utilizando el principio del palomar con $5$ palomas y $4$ palomares.