Principio del palomar

El Principio del palomar o principio de las cajas se le atribuye al matemático alemán Johan Peter Gustav Lejeune Dirichlet $1805-1859$.

Principio del palomar

Si se reparten $n$ palomas en $m$ palomares y $n>m$, entonces algún palomar tendrá más de una paloma.

Si tenemos $m$ palomares, en cada palomar podemos albergar una paloma. Como el número de palomas es $n>m$ entonces como mínimo tenemos $m+1$ palomas. Las $m$ primeras las hemos colocado cada una en un palomar distinto, por lo que nos sobraría una paloma que tendremos que alojarla en uno de los $m$ palomares. Como consecuencia algún palomar tendrá más de una paloma. 

Para el caso en que tengamos $m=5$ palomares y $n=6$ palomas.

  

Las primeras 5 palomas entran cada una es un palomar y la sexta la tendríamos que colocar en uno de los 5 palomares, así habría un palomar con 2 palomas. Si el palomar en el que metemos las 2 palomas es el último la distribución quedaría así.

Principio del palomar generalizado

Sean $m,\,n,\,p$ números naturales tales que $n>m$. Si queremos colocar $n\cdot p + m$ palomas en $n$ cajas entonces alguna de las cajas debe contener al menos $p+1$ palomas.

Este resultado es muy parecido al anterior. Si colocamos $p$ palomas en cada caja, en total hemos colocado $n\cdot p$ palomas. Como $n\cdot p < n \cdot p + 1 \leq n \cdot p + m$ tenemos que todavía nos sobra alguna paloma por colocar. Como cada caja tiene $p$ palomas, la caja en la que metamos la siguiente paloma ya tiene $p+1$ palomas, que es lo que dice el enunciado.

Ejemplos en los que se utiliza el principio del palomar.

Problema de los calcetines

Supongamos que se apagan los fusibles de nuestra casa y tenemos que sacar a oscuras unos calcetines de un cajón. Si en el cajón tenemos 6 calcetines rojos, 6 azules, 6 blancos y 6 verdes, ¿cuántos calcetines debemos sacar como mínimo para asegurarnos que hemos sacado 2 calcetines del mismo color? ¿Y si te acompaña tu hermano y quiere otro par?

Solución:

1.  Si sacamos 2 calcetines no estamos seguros que los 2 sean del mismo color, por ejemplo: podemos haber sacado uno rojo y otro azul. Si sacamos 3 calcetines tampoco podemos estar seguros de tener 2 del mismo color, por ejemplo: podemos haber sacado uno rojo, otro azul y otro blanco. Si sacamos 4 calcetines tampoco es seguro que tengamos 2 del mismo color ya que podrían ser los 4 calcetines de colores distintos, es decir, rojo, azul, blanco y verde, aunque no tienen porque salir en este orden. Al sacar 5 calcetines estamos ya completamente seguros de que habrá 2 calcetines del mismo color ya que solo tenemos 4 colores.
2. Si tenemos que sacar 2 pares, partimos del caso anterior en el cual obtuvimos el mínimo número de calcetines que se tienen que sacar para tener un par. Si sacamos 6 calcetines, el peor de los casos es que saquemos un calcetín del mismo color que el par, es decir, 3 calcetines del mismo color y otros 3 cada uno distinto entre sí. Así, tendríamos un par y 4 calcetines de colores distintos, y por tanto si sacamos un calcetín más obtenemos otro par de calcetines. Luego tenemos que sacar 7 calcetines para asegurarnos que tendremos 2 pares.

Problema de los amigos

En cualquier grupo de 2 o más personas hay siempre 2 de ellas que tienen el mismo número de amigos dentro del grupo.

Solución:

Supondremos que ninguna persona es amiga de sí misma. Supondremos también que el número de personas de dicho grupo es $m\geq 2$, es decir, en el grupo hay al menos 2 personas.

Podemos observar:

1. Una persona del grupo puede tener como máximo $m-1$ amigos dentro del grupo, es decir, puede tener $0,\,...\,,\,m-1$ amigos.
2. Si una persona es amigo de todos los demás, entonces no existe ninguna persona en el grupo que no sea amigo de alguna otra persona, y viceversa, si una persona no tiene amigos en el grupo, entonces no existe ninguna persona que sea amigo de todos.

Llamaremos X al conjunto de las personas del grupo, e Y al conjunto formado por el número de amigos que puede tener una persona, luego $Y=\{0,\,...\,,\,m-1\}$. Por último, consideraremos $f : X \longrightarrow Y$ la aplicación que le asocia a cada persona del grupo el número de amigos que posee.

Nota: De la observación 2 sabemos que en el conjunto Y no pueden aparecer los números $0$ y $m-1$, es decir, no puede haber a la vez en el grupo una persona que sea amiga de todos y otra que no sea amiga de ninguno.

Por tanto tenemos 2 casos:

Caso1: Si no existe ninguna persona que sea amiga de todos. En este caso el conjunto formado por el número de amigos que puede tener una persona es $Y_1 = \{0,\,...\,,\,m-2\}$. El número de elementos en el conjunto $Y_1$ es $m-1$. A este número se le denomina cardinal del conjunto $Y_1$.

Caso2: Si no existe ninguna persona que no tenga amigos en el grupo. En este caso el conjunto formado por el número de amigos que puede tener una persona es $Y_2 = \{1,\,...\,,\,m-1\}$. El número de elementos en el conjunto $Y_2$ es también $m-1$.

Por un lado tenemos que el número de personas que hay en el grupo es $m$ y por otro lado que en cada caso tenemos como máximo $m-1$ personas que tienen diferente número de amigos. Luego por el principio del palomar, como $m > m-1$ entonces existen 2 personas que tienen el mismo número de amigos.

Si os ha gustado esto, os propongo el siguiente problema:

Problema propuesto

Comprobad que en cualquier conjunto de 6 personas siempre hay 3 que se conocen entre sí o 3 que no se conocen.

@antonio_arjona7