El principio del palomar, una potente herramienta matemática (parte 2)

Esta es la segunda parte de una mini serie de dos entradas en la sección Matemoción, del Cuaderno de Cultura Científica, dedicadas al principio del palomar, o de Dirichlet. Como ya comentamos en la entrada anterior, este principio matemático es muy sencillo de formular, no necesita demostrarse, pero al mismo tiempo es una potente herramienta dentro de las matemáticas. Dice lo siguiente: si hay más palomas que palomares, alguno de los palomares deberá contener por lo menos dos palomas. En general, podemos hablar de objetos y cajas donde guardar estos objetos.

En la primera parte vimos algunos ejemplos de su aplicación en problemas relacionados con la vida cotidiana (personas en un teatro con la mismas letras inicial y final en su nombre, número de amigos en una fiesta o sumas de las edades de las personas de una reunión), en teoría de números (algunos resultados sobre divisibilidad) o en geometría (distribución de puntos en un triángulo equilátero), e incluso vimos una generalización del mismo (lo que nos permitió mostrar un ejemplo de coincidencia de cumpleaños).

Si hay más cartas que buzones, eso quiere decir que alguno de los vecinos recibirá por lo menos dos cartas

El ejemplo que se utiliza con más frecuencia en la divulgación científica para explicar la aplicación del principio del palomar a cuestiones más o menos cotidianas, o también como una práctica herramienta para resolver problemas de ingenio, tiene que ver con el número de pelos que tenemos en la cabeza. Aunque me resistía a incluirlo en estas dos entradas por ser un resultado muy conocido, veremos que desde una perspectiva histórica tiene sentido volverlo a recordar.

Ejemplo 1: En Bilbao hay al menos dos personas con el mismo número de pelos en la cabeza.

Para resolver esta cuestión lo primero que tenemos que conocer es cuántos pelos podemos tener como máximo en nuestras cabezas. ¿Lo sabéis? ¿No? No importa, tampoco es una información vital para nuestra existencia. Sin embargo, vamos a realizar una estimación por lo alto de dicha cantidad con el objetivo de utilizarla para resolver este problema.

Supongamos que tenemos cabezas completamente redondas que miden 12 cm. de radio, es decir, unos 75 cm. de perímetro, lo que está al nivel del concurso de cabezones de Kortezubi, en Bizkaia. En tal caso, la superficie de nuestras cabezas, , es de unos 1.800 cm2. Para realizar una estimación por lo alto, supongamos que tenemos pelos por toda nuestra cabeza, por toda la superficie de esa esfera de 12 cm de radio, y que la densidad del pelo es de 100 pelos por cm2, entonces el número de pelos de la cabeza de cualquier persona no va a llegar nunca a los 180.000 pelos. Esta es una estimación por lo alto.

Supongamos que no existe nadie que sea completamente calvo, sin un solo pelo (en caso contrario, además estaría resuelto el problema), por lo tanto, el número de pelos que puede tener una persona va entre 1 y 180.000 (estas cantidades van a ser los palomares para aplicar el principio matemático). Las palomas serán los habitantes de Bilbao, que son unos 350.000. Como hay más bilbaínos que posibles números de pelos, el principio del palomar nos dice que existen al menos dos bilbaínos con el mismo número de pelos en la cabeza.

Hermosa imagen de Bilbao por la noche, sacada de la página “conoce Bilbao conmigo”

Pero si tenemos en cuenta la generalización del principio del palomar que vimos en la primera entrega dedicada a esta herramienta matemática, podemos obtener un resultado más impactante aún. La generalización dice lo siguiente: si hay n palomas y k palomares (n > k), existe al menos un palomar con al menos (no solo dos, sino) n/k palomas, es decir, el valor máximo es al menos mayor que el valor medio.

Si tenemos en cuenta que el número de habitantes de la Península Ibérica es de al menos 57 millones de habitantes, entonces aplicando el principio del palomar generalizado se obtiene lo siguiente.

Ejemplo 2: En la Península Ibérica hay al menos 317 personas con el mismo número de pelos en la cabeza.

En la entrada anterior habíamos comentado que se atribuye al matemático prusianoGustav L. Dirichlet (1805-1859), el haber sido la primera persona en aplicar explícitamente este principio matemático, allá por el año 1834, para demostrar un resultado de aproximación de números irracionales mediante racionales. Dirichlet lo llamó Schubfachprinzip (principio de los cajones), y nosotros lo conocemos desde entonces como el principio de Dirichlet.

Sin embargo, en el artículo “The pigeonhole principle, two centuries before Dirichlet” (que me envió Samuel Dalva, a quien le agradezco la información), se explica que la primera referencia al principio del palomar es de dos siglos antes de Dirichlet y tiene que ver con el ejemplo de los pelos de la cabeza.

En el libro, escrito en latín en 1622, Selectae Propositiones del jesuita francés Jean Leurechon, que enseñó matemáticas en la Universidad jesuita de Lorraine en Pont-à-Mousson, se menciona de forma indirecta este principio: “Es necesario que dos hombres tengan el mismo número de pelos, oro y otros”. Además, en el libro Récréation mathematique composee de plusieurs problemes plaisants et facetieux (1624), atribuido al propio Jean Leurechon, se explica por qué “es absolutamente necesario que dos personas tengan el mismo número de pelos”, utilizando el argumento que conocemos como el principio del palomar, si hay más personas que cantidades distintas de pelos que puedan tener, entonces habrá dos con el mismo número de pelos.

Pero volvamos a los ejemplos de aplicaciones de este principio. El primero tiene que ver, de nuevo, con una fiesta, pero esta vez relacionado con el lugar en el que se sientan los comensales en una mesa.

Ejemplo 3: En una fiesta, 8 de los invitados están sentados en una mesa octogonal, con cada uno de los comensales sentado en uno de los lados de la mesa. Cada sitio ha sido asignado a un invitado concreto (marcado con su nombre), sin embargo, los invitados no se han dado cuenta de esta circunstancia y se han sentado al azar. Curiosamente, ninguno de los 8 invitados de esa mesa se ha sentado en el lugar que le correspondía. Vamos a demostrar que hay una forma de rotar la mesa de forma que haya dos personas que quedan sentadas en el sitio correcto.

En la siguiente imagen vemos una posible distribución de las ocho personas sentadas en la mesa octagonal, en la que ninguna de ellos se ha sentado en el sitio que había sido designado para ella.

Para probar la afirmación de que se puede realizar un giro de la mesa en el que al menos dos de los comensales estén sentados en su sitio, vamos a considerar la distancia (en el sentido de las agujas del reloj) de cada una de las personas al sitio que le había sido asignado. Como cada persona está sentada en un lugar incorrecto, entonces las posibles distancias de cada persona a su lugar correcto son {1, 2, 3, 4, 5, 6, 7}.

Pero hay 8 personas que se sientan a la mesa, y 7 posibles distancias de ellas a su sitio correcto (en el sentido de las agujas del reloj), luego por el principio de los cajones, habrá dos personas que estén a la misma distancia (en el sentido de las agujas del reloj) del lugar que tiene escrito su nombre. Por lo tanto, rotando la mesa (en el sentido contrario a las agujas del reloj) tantas posiciones como la distancia que comparten esas dos personas, situará la mesa de tal forma que esas dos personas estén colocadas en el lugar correcto.

Distribución de las ocho personas sentadas en la mesa octagonal, en la que ninguna de ellos se ha sentado en el sitio que había sido designado para ella. Si se giran cuatro posiciones los comensales C y E quedarán sentados en su sitio

El siguiente es un ejemplo interesante, con un argumento sencillo, pero curioso.

Ejemplo 4: Una joven que quiere participar en la Olimpiada Matemática decide entrenarse en la resolución de problemas matemáticos. Durante un periodo de 61 días (dos meses) va a estar haciendo problemas, por lo menos un problema al día, pero no más de 92 problemas (que es la cantidad total que tiene el libro que utiliza). Independientemente de la cantidad de problemas que decida hacer cada día, va a existir una cantidad de días consecutivos durante los cuales realiza exactamente 29 problemas.

Si denotamos por  la cantidad de problemas realizados hasta el día , es decir, la cantidad de problemas acumulados desde el primer día, entonces tenemos que

Los 61 números  son distintos, y están ordenados en orden creciente, puesto que todos los días hace por lo menos un problema.

Con esta notación, lo que tenemos que demostrar es que existen dos días  y  tales que (es decir, hay un periodo de  días consecutivos en los que ha realizado 29 ejercicios). Por lo tanto, vamos a sumar 29 a todas las sumas acumuladas anteriores, esto es,

Por la misma razón de antes, estos 61 números  son distintos y están ordenados en orden creciente. Las dos desigualdades nos están diciendo que hay 122 números ( y ) que toman valores entre los números 1 y 121. Como tenemos más números (122) que posibles valores (121), eso quiere decir que al menos dos números tienen el mismo valor, es decir, son iguales. Pero, resulta que los 61 primeros números, , son diferentes entre sí, al igual que los otros 61, , de manera que los dos números que son iguales deberán pertenecer uno al primer grupo y el otro al segundo, es decir, existirá un , lo que significa un elemento del primer grupo de números , y un , lo que significa un elemento del segundo grupo de números , tales que , como deseábamos.

Logotipo de la Olimpiada Internacional de Matemáticas

Como ya comentamos en la entrada anterior del Cuaderno de Cultura Científica dedicada a este tema, el principio de Dirichlet tiene muchas aplicaciones a la teoría de números. Empecemos con algunos resultados sencillos.

Muchísimos más ejemplos en:

Cultura Científica