De palomas y principios


En matemáticas la afirmación más simple puede producir los resultados más sorprendetes.

Imaginemos que tenemos 5 palomares y 6 palomas. Si las palomas llegan a su sitio, es claro que en uno de ellos habrá por lo menos dos palomas. ¡Obvio, si solo tenemos 5 palomares! diría alguien, ¡si cada paloma primero tuviera su "hueco individual" la última no le quedaría más que compartir uno ya ocupado! y esto en un caso extremo, porque sería incluso posible que no se ocuparan algunos lugares.

Generalizando, el principio se enunciaría matemáticamente como "Si se dispone de n casillas para colocar m objetos y m>n, entonces en alguna casilla deberán colocar por lo menos dos objetos"

Esta es la idea básica del conocido principio del palomar, también llamado principio de las casillas, de distribución, de Dirichlet, etc. (sí, tiene muchos nombres)

Obvio, trivial, inofensivo... ¿seguros?

Y este simple principio, del cual cualquiera se puede dar cuenta, es la base de la demostración de una cantidad impresionante de problemas e incluso puede mostrar afirmaciones muy interesantes.

La clave al usarlo es identificar cuales son las casillas (o palomares, o como quieran llamarle) que son los lugares en que poner cada elemento, y identificar los objetos (palomas, perros, dulces, perlas, lo que quieran) a colocar, donde son más objetos que casillas.

Un problema clásico donde se utiliza este principio es aquel que dice:

¿Cuántas personas son necesarias para asegurar que dos cumplen años el mismo día?

En este caso los días del año serían nuestros palomares y las personas las palomas. Tenemos 366 días en un año (contando si este fuera bisiesto) por lo tanto hay 366 palomares. Según el principio antes enunciado si tenemos más personas que días del año se cumpliría el problema, teniendo 367 personas podemos asegurar que dos cumplen el mismo día.

La respuesta sería 367, aunque este principio sólo nos asegura su existencia; no nos dice que día del año sería el cumpleaños, ni la identidad de las personas.

Ahora intentenlo ustedes. Prueben lo siguiente.

En una fiesta, cada quién conoce a determinado número de gente. Alguien puede conocer a todos, otro invitado más solo a dos, entre otras cantidades. En la fiesta de Enrique, donde no hay colados (todos son muy decentes) asisten 13 personas, incluyendolo a él. Demuestra que hay al menos dos invitados que conocen al mismo número de personas.

Sugerencia: ¡Utilicen el principio del palomar!


Fuentes: M. L. Pérez Segui, Combinatoria. Cuadernos de la Olimpiada de Matemáticas, 2006

3 comentarios:

  1. Los "palomares" son la cantidad de gente que puede conocer cada persona (de 1 a 12). La cantidad de "palomas" es 13. Como "palomas" es mayor que "palomares", al menos 2 personas conocen a la misma cantidad de gente.
    ¿Esta bien?

    ResponderBorrar
  2. Primer paso: Si hubiera dos que no conocen a nadie, ya se cumpliría. Considero que solo hay uno. Quedan 12 que conocen a alguien.
    De ellos, puede que alguno solo conoza a uno solo. Si hay mas de uno ya se cumpliría. Considero que solo hay uno. Quedan 11.
    Así sucesivamente, hasta que los números 12 y 13 de la lista conoce a los otros 12 (no a 13, pues no se cuenta a sí mismo

    ResponderBorrar
  3. Supongamos que las personas son:
    A (el anfitrion), B, C,D,E,F,G,H, I,J,K,L,M.
    A conoce a todos, o sea 12
    B conoce a A+10 (no 11 sino conoceria igual que A).
    C conoce a A+9
    D conoce a A+8, y asi sucesivamente, llegamos que:
    K conoce a A+1
    L conoce solo a A
    M necesariamente tiene que conocer a un similar número que alguno de los anteriores. Es decir siempre habrá al menos 2 personas que conocen a un mismo número de invitados.
    Saludos desde Chile.
    Marco Chacana Barra

    ResponderBorrar

Related Posts Plugin for WordPress, Blogger...