Principio del palomar, unos cuantos ejemplos prácticos.

Hoy os presento el que posiblemente sea el teorema más evidente en matemáticas y a la vez increíblemente útil: el principio del palomar. El enunciado es muy sencillo, si tenemos una cantidad de n palomas guardadas en m palomares con m<n, por fuerza debe de haber al menos un palomar que contenga varias palomas.

¿Hace falta que lo demuestre? Creo que no, cualquiera tiene que ver que evidentemente es cierto. Se puede generalizar un poco más y decir que de hecho en algún palomar habrá por lo menos $$\lceil\displaystyle{\frac{m}{n}}\rceil$$ palomas donde $$\lceil\displaystyle{\frac{m}{n}}\rceil$$ representa el número natural que hay justo por encima de m/n. Se cree que el primer enunciado de este principio se debe a Dirichlet en 1834, aunque bueno, yo estoy seguro de que alguien se tuvo que dar cuenta antes de esto, ¿no creéis? Pero Dirichlet es del primero que se tiene constancia, al menos de forma rigurosa. Supongo que nadie dudará que el mismo principio sería válido si cambiamos palomas por cualquier otra cosa y palomares por otro tipo de recipiente. Vamos a ver ahora unos cuantos ejemplos de cómo aplicar este principio tan sencillo para obtener resultados que aparentemente no parecen triviales:

Ejemplo 1:


En una fiesta con 100 personas, algunos invitados se dan la mano y otros no, pero puedo estar seguro de que al menos dos han saludado al mismo número de gente. ¿Por qué?.

Este ejemplo está sacado del artículo “En matemáticas no hay paro” que he leído precisamente hoy. Pulsa en mostrar para ver cómo llegar a esto.

[spoiler]En el mismo artículo se explica la solución usando el principio del palomar:

Llevando el razonamiento a la fiesta: los invitados son palomas y sus saludos, palomares. Al ser un gesto recíproco, solo hay 99 saludos posibles para 100 invitados, con lo que dos se estrujarán en el mismo palomar numérico.

Creo que el periodista resumió un poco la respuesta del entrevistado ya que en un principio habría 100 saludos posibles (cada invitado puede saludar de 0 personas a 99) por lo que habría 100 palomares, tantos como palomas. Pero ciertamente al ser un gesto recíproco, solo hay 99 saludos puesto que si alguien ha dado 99 apretones de manos, no habrá nadie que no le haya apretado la mano a él por lo que la existencia del palomar “99” haría que no existiese el “0” así que ahora podemos aplicar el principio y deducir que 2 personas han saludado al mismo número de personas.[/spoiler]

Ejemplo 2:


¿Puede contener un triángulo equilátero de 2 centímetros de lado 5 puntos de forma que no hayan 2 a distancia menor o igual que 1?

Este es mi ejemplo favorito. Si uno intenta encontrar esos puntos, seguro que enseguida se da cuenta de forma intuitiva que no va a ser posible. Pero de tener una idea intuitiva a comprobar que efectivamente es imposible hay una gran diferencia. Y para ellos vamos a usar de nuevo el principio del palomar. ¿No veis cómo? Quizá haga falta también poder, sabiduría y valor (los fans de la saga Zelda quizá ya sepan por donde voy!). Si aún no sabes cómo se haría, pulsa en mostrar.

[spoiler]

Podemos dividir el triángulo equilátero inicial en 4 triángulos menores de lado 1 (imitando precisamente el símbolo de la trifuerza de la saga Zelda):

Trifuerza!!!!

Ya tenemos nuestros 4 palomares (los 3 triángulos dorados y el triángulo blanco central) y nuestras 5 palomas (los 5 puntos), así que por fuerza al menos 2 puntos caerían sobre el mismo triángulo. Y esos dos puntos contenidos en el mismo triángulo, obligatoriamente estarán a una distancia menor que uno. ¡¡Qué bonito!! ¡¡Mezclando matemáticas con videojuegos!!

[/spoiler]

Ejemplo 3:


¡¡Hay 2 persona en el mundo que tienen exactamente el mismo número de pelos en la cabeza!! ¡¡Es más, seguro que podemos encontrar muchas más de 1000 personas con el mismo número de pelos en la cabeza!!

[spoiler]Ahora las palomas van a ser la humanidad y los palomares el número de pelos de la cabeza. Pero ¿cuántos pelos puede tener una persona en la cabeza? Si nos vamos a la wikipedia, un adulto puede tener alrededor de un millón en la cabeza, pero contando barba, nariz, orejas, pelusillas casi invisibles y tal. Si nos quedamos con el cuero cabelludo, hay entre 100.000 y 150.000. Bueno, para no quedarnos cortos, por si hubiese alguien super-peludo vamos a considerar que las personas pueden tener hasta un millón de pelos en el cuero cabelludo. El número de pelos podría variar de 0 a un millón, y en estos palomares tenemos que meter los aproximadamente 6.000 millones de habitantes actuales de la tierra (vaya, hemos crecido, según google vamos ya por 6.775.235.741). Aplicando el principio del palomar tendríamos que de hecho ¡¡¡deben de haber al menos unas 6.775 personas con exactamente el mismo número de pelos!!!

Bueno, algunos podrán decir que esto era obvio porque hay muchos calvos… sin ningún pelo en la cabeza. Bueno, puesto que el número de calvos totales en el mundo no debe de ser muy alto, podríamos haber hecho el mismo razonamiento considerando solo gente que tenga pelo y habríamos llegado también a una conclusión similar para gente con pelo.[/spoiler]

Ejemplo 4:


Cojamos 6 números del 1 al 10. Entre los escogidos, seguro que hay 2 que sumen 11.

[spoiler]En esta ocasión, los números a escoger son las palomas y los palomares son los pares de números entre 1 y 10 que suman 11, es decir los 5 pares 1-10, 2-9, 3-8, 4-7, 5-6. Como tenemos 5 pares y tenemos que elegir 6 números, seguro que 2 números pertenecen al mismo par y por lo tanto suman 11.[/spoiler]

Ejemplo 5:


Tenemos 100 monedas de oro que tenemos que repartir entre 14 trabajadores. Como no hay 2 que hayan trabajado exactamente lo mismo, las 14 pagas resultantes deberían de ser todas distintas. ¿Es esto posible sin necesidad de partir alguna moneda?

Uhm, este último podría ser uno de los típicos juegos de ingenio que pongo por el blog. Al que los vaya siguiendo, le recomiendo que intente sacarlo sin leer la solución.

[spoiler]Ahora tenemos 14 personas a las que pagar y 100 monedas. No, no tenemos que aplicar el principio del palomar directamente, solo nos serviría para decir que al menos uno cobraría al menos 8 monedas y no es eso lo que buscamos. En este caso las palomas van a ser los trabajadores y los palomares el número de monedas a cobrar y vamos a dar un pequeño rodeo ya que en un principio habrían más palomares que palomas. Vamos a ver que es imposible hacer el reparto:

Si hubiésemos conseguido el reparto deseado, lo que está claro es que el que más ha cobrado debería de cobrar al menos 14 monedas, ya que si cobra menos, tendríamos solo 13 posible pagas (de 1 a 13 monedas) por lo que por el principio del palomar, 2 trabajadores (palomas) habrían cobrado lo mismo (caerían en el mismo palomar). Así que para que todas las pagas sean distintas, el que más cobra cobrará al menos 14 monedas.

Consideremos los 13 restantes trabajadores y pensemos en cuánto cobrará el que más cobre de ellos. De nuevo debería de cobrar al menos 13 monedas, ya que si cobrase menos tendríamos 12 pagas (de 1 a 12 monedas) y 13 palomas y esto no podría ser porque por el principio del palomar habrían 2 que cobrasen lo mismo.

Y si seguimos así, el siguiente trabajador que más cobre debería de cobrar 12 monedas por lo menos, el siguiente 11, el siguiente 10 y así. Pero claro, si sumamos el número de monedas que irían cobrando cada uno como mínimo nos saldría que cobrarían en total de por lo menos

14+13+12+11+10+9+8+7+6+5+4+3+2+1=105 monedas

lo que es imposible porque solo tenemos 100. Por lo tanto no podemos hacer el reparto que queremos sin partir ninguna moneda.[/spoiler]

Ejemplo 6:


Si elegimos 100 números naturales al azar, siempre habrá 2 de ellos cuya diferencia sea múltiplo de 99.

Antes de seguir leyendo pensad un poco a ver si sabéis cómo aplicar aquí el principio del palomar. Si no se os ocurre, pensad en el mismo problema pero con 101 números y que la diferencia sea múltiplo de 100…

[spoiler]El caso de 101 números y diferencia múltiplo de 100 es más fácil de ver ya que la diferencia de 2 números será un múltiplo de 100 si las dos últimas cifras de uno de los dos números coincide con las dos últimas del otro. Por ejemplo 1532 y 132 terminan en 32 y su diferencia es 1400 que es múltiplo de 100. Tendríamos 101 números y 100 posibles terminaciones de 2 cifras así que por el principio del palomar, 2 números tendrían la misma terminación. Observad que 1532 y 132 terminan en 32 porque son de la forma 100xn+32 con n un número natural.

Para el caso de 100 números, tengamos primero en cuenta que todo número natural m se puede escribir de la forma m=99xn+r con n un número natural y r un número natural menor que 99. ¿Lo tenéis claro? Si no, dividir m entre 99 como se hacía en el colegio, es decir, calculando cociente y resto. Si os acordáis de qué significa dividir, el resto es lo que le sobra a m cuando multiplicamos 99 por el cociente. Dicho de otra forma, m=99xcociente+resto.

Pues bien, tenemos 100 números y 99 posibles restos (de 0 a 98) así que por el principio del palomar, de los 100 números tendremos 2 con el mismo resto, es decir, habrá un número a de la forma a=99xp+r y un número b de la forma b=99xq+r. Si restamos estos dos números tenemos que a-b=99x(p-q) que es un múltiplo de 99, como queríamos.

Siguiendo el mismo razonamiento podemos demostrar en general que si cogemos n números naturales y m<n, de entre los números escogidos siempre habrán 2 cuya diferencia sea un múltiplo de m.[/spoiler]

Ejemplo 7:


Un hombre se toma durante el mes de abril todos los días (30 en total) por lo menos una aspirina. A lo largo del mes se ha tomado en total 45 aspirinas. Habrá alguna sucesión de días consecutivos en los que en total se habrá tomado 14 aspirinas.

[spoiler]Para ver que esto es así, para cada día del mes vamos a considerar el número de aspirinas que se ha tomado al llegar a ese día. Para cada día nos saldrá un número entre el 1 y el 45 y todos los números serán distintos (de un día para otro siempre se ha tomado alguna más). Tenemos así 30 palomas.

Observad que si vemos que de estos 30 números, hay 2 números a y b con a<b que se diferencian exactamente en 14, eso quiere decir que el hombre se había tomado al llegar cierto día a aspirinas y que unos cuantos días después se había tomado b aspirinas, es decir 14 aspirinas más. Así que desde el día posterior al día de a aspirinas hasta el día que llegó a b aspirinas, se tomó exactamente 14.

Ok, pues nuestro problema se reduce a ver que de los 30 números, hay 2 cuya resta es 14. ¿Quiénes van a ser nuestros palomares ahora? Pues serán los pares de números que se de la forma n-(n+14), es decir

$$!1-15, 2-16, 3-17, 4-18, 5-19,\dots,29-43, 30-44, 31-45.$$

¡Necesitamos ver que de los 30 números hay 2 en el mismo par! Pero tenemos 31 palomares, más que palomas…, no nos sirve…Bueno, pero tengamos en cuenta una cosa, cada número pertenecerá a algún par, aunque puede pasar que de hecho que pertenezca a varios pares (por ejemplo 16 pertenece al par 2-16 y al par 16-30). Esto nos va a permitir eliminar 2 palomares, el par 15-29 y el 16-30 ya que los 4 números que pertenecen a estos pares, están también en otros pares (el 15 en el 1-15, el 16 en el 2-16, el 29 en el 29-43 y el 30 en el 30-44).

Nos quedamos entonces con 30 números (palomas) y 29 pares (palomares) de forma que cada número pertenece al menos a uno de los 29 pares. Si un número pertenece a 2 pares distintos, le asignamos por ejemplo el par más pequeño (si tuviésemos el 17, lo metemos en el palomar 3-17 y no en el 17-31). Ya hemos metido 30 palomas en 29 palomares. Ahora sí, algún palomar debe de tener al menos 2 palomas y esto es justo lo que necesitábamos.[/spoiler]

Como veis, en todos los ejemplos se ha aplicado el principio del palomar aunque en cada caso de una forma bien distinta. Podría poner muchísimos más ejemplos, ¿conoces alguno?

Con esta entrada participo una vez más en el Carnaval de Matemáticas. Gaussianos es en esta ocasión el anfitrión de la Edición 2.2.

12 Responses to “Principio del palomar, unos cuantos ejemplos prácticos.”

  1. Olá, Estamos com um projeto denominado UBM que pretende unir os blogs de matemática. Temos blogs do Brasl, Argentina e Espanha.

    De uma conferida:

    http://ubmatematica.blogspot.com/p/descricao-dos-blogs-filiados.html

    Caso haja interesse, deixe um recado no mural de recados ou nos envie um e-mail.

    Um abraço.

    Kleber

  2. Claudio dice:

    Aqui te mando un problema que se resuelve por el principio del palomar:

    Alrededor de una mesa circular estan puestas 15 tarjetas con los nombres de los 15 delegados que se van a reunir allí.
    Los delegados se sientan sin darse cuenta de que estababn puestas estas tarjetas, y una vez sentados, sorprendentemente, nadie está sentado frente a su propia tarjeta.

    Demostrar que la mesa se ​​puede girar para que al menos dos de los delegados a la vez esten sentados correctamente.

    Claudio

  3. Carlos dice:

    @Claudio:
    ¡¡Gracias por el ejemplo!!

  4. […] número de colaboraciones, con varios blogs que se estrenan en esta edición. Este jueves podemos leer sobre el principio del palomar en Zurditorium; podemos ver una interesante manera de introducir la geometría analítica doblando […]

  5. Rosa dice:

    @Claudio:
    Necesito la respuesta a este problema!!! es un poco urgente!!
    Muchas gracias!!

  6. Jota Ele dice:

    Saludos, aquí les dejo mi planteamiento a falta de un desarroyo mejor por las prisas.

    [spoiler] Nuestras palomas son las 15 tarjetas y nuestros palomares las 14 posibles posiciones a rodar en la mesa, ya que la 15 ó 0 (una vuelta completa) está prohibida al no haber nadie en su sitio. Se puede ver como cada tarjeta ha de rodarse de 1 a 14 posiciones para llegar a su sitio. Ergo {15/14}–>2 tarjetas han de rodarse el mismo número de puestos para colocarse en su lugar correcto. [/spoiler]

  7. Roberto Torres Jimenez dice:

    Sea n un entero positivo, demuestra que en cualquier grupo de n enteros consecutivos hay exactamente uno que es divisible por n.

    Necesito ayuda con esa demostración ya que se que eso es verdadero pero no se ocmo realizarla de forma matemática, por favor no me manden un ejemplo por que no me ayuda a demostrarlo un ejemplo D:!!

  8. Carlos dice:

    @Roberto Torres Jimenez:
    No sé qué conocimientos previos tienes y tal. La unicidad está clara (si hay 2 los restas y al ser un múltiplo de n, solo puede ser 0 y ser el mismo).

    La existencia te doy una idea ya que no te voy a hacer tampoco los deberes 😀

    Vamos a suponer que son todos positivos (si son negativos es lo mismo cambiando el signo y si hay positivos y negativos es trivial porque el 0 es un múltiplo de n).

    Sea m el primer elemento de ese conjunto de números enteros consecutivos y sea p el mayor múltiplo de n menor que m (p existe ya que pertenece al conjunto {0,1,…,n-1}. Te basta con demostrar que p+n es uno de esos n números consecutivos.

    Y no te voy a hacer más, que está ya casi hecho. Se puede hacer de más formas.

  9. Natalia dice:

    Me podrías ayudar con este, por favor ?

    “Busque información en internet sobre el principio del palomar. Ocupando lo anterior demuestre que existe al menos un resultado que se puede obtener con al menos 16.000.000 de configuraciones distintas de signos + ó −.”

    Gracias!

  10. josefa dice:

    hola me podrías ayudar con este ejercicio para mi clase de números, por favor?

    Busque información en internet sobre el principio del palomar. Ocupando lo anterior demuestre que existe al menos un resultado que se puede obtener con al menos 16.000.000 de configuraciones distintas de signos + o´ −.

  11. Aimy dice:

    gracias por los ejemplos están entretenidos e interesantes!!

Leave a Reply