La semana pasada mi colega y amiga Marta Macho (por cierto, una excelente matemática, profesora y divulgadora) nos ofrecía con mucho humor y una pizca de ironía, en esta categoría, Matemoción, del Cuaderno de Cultura Científica, una lista de cuarenta técnicas de demostración. Era su entrada “Técnicas de demostración para casos desesperados”.
Muchas de ellas nos sonaban cercanas a todas aquellas personas que nos dedicamos a la enseñanza de las matemáticas. A mi me gustaría destacar tres de ellas, la prueba por intimidación “Es trivial!”, la prueba por finalización de tiempo “Vista la hora que es, dejo la prueba de este teorema como ejercicio” o la prueba por consenso “¿Estáis todos de acuerdo?”
En esta entrada de la sección Matemoción vamos a analizar una nueva técnica de demostración matemática, aunque algo más seria que las anteriores, ¿o no?. Es elprincipio del palomar, o de Dirichlet.
Este es un principio muy sencillo de formular y que no necesita demostrarse de lo obvio que es (y no estoy echando mano aquí de la prueba por intimidación), de hecho, cuando explicamos esta técnica matemática a las personas ajenas a esta ciencia, suelen pensar que estamos bromeando, que les estamos tomando el pelo o simplemente es otra excentricidad de estos locos matemáticos. A pesar de su sencillez, el principio del palomar es al mismo tiempo una herramienta muy potente dentro de la combinatoria, con aplicaciones en campos tan diversos como la teoría de grafos, la geometría, el análisis matemático, la teoría de números, las ciencias de la computación o la resolución de problemas, por citar algunos.
El principio del palomar 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. La verdad es que es un principio tan simple que no necesita demostración.
Mostremos algunos ejemplos sencillos de aplicación de este principio a cuestiones más o menos cotidianas.
Ejemplo 1: En cualquier espectáculo del Teatro Campos Elíseos de Bilbao, que esté lleno, existen dos personas del público tales que su primera y su última letra son iguales (como por ejemplo, Aitor y Amador, o Sorkunde y Salomé).
El aforo del Teatro Campos Elíseos es de 800 personas, que van a ser nuestras palomas, mientras que los pares formados por la primera y última letra de un nombre (en los ejemplos anteriores (a,r), de Aitor y Amador, y (s,e), de Sorkunde y Salomé), nuestros palomares. Puesto que hay 27 letras en el alfabeto, entonces hay 27 x 27 = 729 pares de letras posibles, desde la (a,a) hasta la (z,z). Como hay más palomas (personas) que palomares (pares de letras), entonces al menos dos personas deberán compartir la primera y la última letra de su nombre.
Ejemplo 2: En una fiesta cualquiera hay por lo menos dos personas con el mismo número de amigos.
Supongamos que a una fiesta, o reunión de cualquier tipo, han asistido n personas, bueno para que no parezca tan abstracto, pensemos que han sido 32 personas. Podríamos distinguir dos casos:
A. Si todas las personas de la reunión tienen al menos un amigo, cada una de esas 32 personas (que van a ser ahora nuestras palomas) pueden tener entre 1, ya que todas tienen al menos un amigo, y 31 amigos, ya que suponemos que “cada persona no es amiga de sí misma” (las cantidades de amigos son ahora los palomares), entonces aplicando el principio del palomar existen dos personas con el mismo número de amigos.
B. Pero si hubiese algunas personas en la fiesta que no tienen ningún amigo, razonaremos como antes, aunque sin tener en cuenta a las personas “solitarias”. Por ejemplo, si de las 32 que están en la fiesta, 7 no tienen amigos, se hace el razonamiento anterior con las 25 personas restantes, que ahora pueden tener entre 1 y 24 amigos.
Ejemplo 3: Siempre que haya 9 personas en una reunión, de edades comprendidas entre 18 y 58 años, es posible elegir dos grupos de personas tal que las sumas de las edades de las personas de cada grupo sean iguales.
Como estamos buscando grupos de personas dentro del grupo total de 9 personas, es decir, subconjuntos del conjunto de nueve elementos, es útil recordar que hay un total de 29 subconjuntos del conjunto de 9 elementos (esta es una cuestión que no vamos a explicar aquí hoy, pero que tiene que ver con los números combinatorios y el binomio de Newton), incluido el vacío, luego 511 subconjuntos no vacíos. Estos van a ser las palomas en esta ocasión.
Ahora, como las edades de las personas de la reunión están comprendidas entre los 18 y los 58 años, las sumas de las edades de cualquier subconjunto de personas están comprendidas entre 18 = 1 x 18 (una única persona, y que tenga la menor de las edades posibles) 522 = 9 x 58 (las nueve personas, y que todas tuviesen la mayor edad posible). Por lo tanto, tenemos 504 valores posibles para las sumas de las edades de las personas de cualquier subconjunto de las personas que están en esta reunión. Estos van a ser los palomares.
En consecuencia, el principio del palomar nos dice que existen dos subconjuntos distintos, del grupo de 9 personas que hay en la reunión, con la misma suma de las edades de las personas de cada uno de ellos.
Pero podría ocurrir que en esta conclusión, consecuencia del principio de Dirichlet, hubiese alguna persona que estuviese siendo considerada a la vez en esos dos subconjuntos que existen. Si esto ocurriese, no tenemos más que eliminar a esa persona de cada uno de los dos subconjuntos, y los dos nuevos subconjuntos que obtenemos siguen cumpliendo la propiedad de que la suma de las edades de sus miembros es la misma, ya que al eliminar a la misma persona de ambos, se quita el mismo número a las sumas de las edades, y se sigue manteniendo la igualdad.
Aunque estamos poniendo ejemplos más bien cotidianos para entender la fuerza del principio, lo interesante es que se puede aplicar a todo tipo de situaciones, de hecho, como decíamos al principio, es una potente herramienta en matemáticas.
El primer matemático en utilizarlo explícitamente dentro de su investigación fue el matemático prusiano Gustav L. Dirichlet (1805-1859), para demostrar un resultado de aproximación de números irracionales mediante racionales (recordemos que los números racionales son aquellos que se pueden expresar como división de dos números enteros, por ejemplo, 5/2, y que si los expresamos con decimales o tienen un número finito de decimales, o un número finito que se repite periódicamente), por este motivo se conoce también como el principio de Dirichlet.
En particular, se pueden demostrar muchos resultados de teoría de números haciendo uso del principio del palomar. A continuación, mostramos algunos sencillos ejemplos.
Ejemplo 4: Consideremos un conjunto arbitrario de 47 números, entonces existen al menos dos cuya diferencia es divisible por 46.
Antes de explicar la aplicación del principio de Dirichlet para probar esta afirmación, aclaremos una vez más, que esos 47 números son arbitrarios, el resultado va a ser válido cualesquiera que sean los 47 números que se consideren.
¿Cómo utilizar el principio para demostrar este resultado? Cuando dividimos un número cualquiera entre otro, en este caso nos interesa dividir por 46, entonces obtenemos el divisor y el resto. Así, si dividimos el número 357 entre 46 nos da 7 (el dividendo), pero nos sobran 35 (que es el resto).
Por lo tanto, 357 = 46 x 7 + 35. En matemáticas, se dice que 357 es congruente con 35, módulo 46, y se expresa 
.
.
Para aplicar el principio del palomar, vamos a distribuir nuestras palomas (que serán los 47 números arbitrarios que se han tomado) en los siguientes 46 palomares…
P1 = conjunto de números tales que al dividir por 46 queda de resto 0 (es decir, los números congruentes con 0, módulo 46),
P2 = conjunto de números tales que al dividir por 46 queda de resto 1 (es decir, los números congruentes con 1, módulo 46),
P46 = conjunto de números tales que al dividir por 46 queda de resto 45 es decir, los números congruentes con 45, módulo 46).
En consecuencia, habrá por lo menos dos palomas, es decir, dos números del conjunto de 47 que habíamos elegido arbitrariamente, compartiendo palomar, es decir, que tienen el mismo resto al dividir por 46.
Esos dos números se podrán escribir, como antes hemos hecho con el número 357, de la forma, 357 = 46 x 7 + 35, con distintos divisores, pero el mismo resto. Al restar ambos números, como los dos tienen el mismo resto, el resultado quedará múltiplo de 46, y se concluye el resultado.
Pero hay mucho, mucho más en: