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

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

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

Green-Tao Theorem with Endre Szemeredi de Oliver Sin, 2012

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.

Podemos reformular el principio del palomar diciendo que si tenemos más pares de zapatos que huecos en nuestro zapatero, como en la imagen, entonces por lo menos dos pares de zapatos deberán compartir hueco en el mismo

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.

Momento de la escena del camarote de la divertida película Una noche en la opera, de los Hermanos Marx, en el que hay ya nueve personas en el camarote

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.

Peter Gustav Lejeune Dirichlet (1805-1859)

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:

Cultura Científica

¿Quién es la jefa en una bandada de palomas?

Jueves, 08 de abril de 2010

¿Quién es la jefa en una bandada de palomas?

La aves individuales vuelan dentro de las bandadas en posiciones que podrían representar su posición jerárquica en el grupo, según un estudio de la Universidad Etvs Loránd en Budapest (Hungría) que se publica en la revista Nature. El trabajo es el primero en demostrar con claridad la organización del movimiento dentro de las bandadas de aves.

Los investigadores colocaron un GPS en miniatura en un grupo de palomas / Zsuzsa Áka

Los autores explican que casi no existen datos relativos al movimiento de grupos de aves en largas distancias en la naturaleza debido a las dificultades técnicas existentes para su registro. Los científicos, dirigidos por Tamás Vicsek, utilizan dispositivos GPS de peso ligero para seguir los movimientos de palomas mensajeras en grupos de alrededor de diez para conseguir información sobre las estrategias de orientación de las aves.

Los investigadores descubrieron una jerarquía bien definida entre los miembros de la bandada. Los autores identificaron al 'líder' al anotar cuánto tiempo tardaban en seguirle el resto de aves después de un cambio de dirección y descubrieron que la posición espacial en la que se situaba un ave dentro del grupo se asociaba con su lugar en la jerarquía. Los investigadores confirman que las aves situadas al frente del conjunto son las líderes.

Los autores también señalan que las aves tenían una preferencia por la visión con el ojo izquierdo. Esto significaba que las aves situadas a la derecha probablemente eran más inferiores que las aves a la izquierda ya que utilizaban su visión izquierda para seguir los movimientos.

Una de las palomas, con el GPS / Z. Ákos

Los investigadores concluyen que, en las bandadas que son lo suficientemente grandes para permitir interacciones entre parejas, las relaciones líder-seguidor parecen producirse de forma consistente. También apuntan que esta conducta tiene el potencial de trasladarse a grupos más grandes de aves e incluso a animales diferentes, lo que puede ser un punto de estudio muy interesante.

Fuente:

ABC.es