Si hay más palomas que palomares, al menos un palomar contiene más de una paloma.
1. La idea fundamental
El principio del palomar, llamado también principio de los cajones o principio de Dirichlet, nace de una observación muy sencilla: si distribuimos más objetos que recipientes, al menos un recipiente recibirá más de un objeto. Su fuerza aparece cuando las «palomas» y los «palomares» están ocultos: personas y meses, números y restos, puntos y regiones geométricas, subconjuntos y sumas, números y partes impares.
- Palomas = los objetos que distribuimos.
- Palomares = las categorías en las que los clasificamos.
2. Forma general
Si N objetos se distribuyen entre k recipientes, al menos un recipiente contiene como mínimo ⌈N / k⌉, donde ⌈x⌉ es el menor entero mayor o igual que x. Por ejemplo, si distribuimos 25 personas entre los 12 meses del año, al menos un mes contiene como mínimo 3 personas, porque 25/12 es mayor que 2.
3. Fórmula inversa
¿Cuántos objetos hacen falta para tener la certeza de que al menos un palomar contiene r objetos? Podemos colocar como máximo r − 1 objetos en cada uno de los k palomares sin llegar a r. El máximo es k(r − 1); el siguiente objeto fuerza el resultado: k(r − 1) + 1.
4. El método del peor caso
Muchos problemas se resuelven imaginando la distribución más desfavorable: evitamos el resultado deseado durante el mayor tiempo posible y añadimos un último objeto. En resumen: máximo posible sin alcanzar el objetivo + 1.
5. Veinticinco problemas resueltos
Problema 1 - Los meses
En una clase hay 13 estudiantes. Demuestra que al menos dos nacieron en el mismo mes.
Solución
Las 13 personas son las palomas y los 12 meses son los palomares. Como 13 > 12, al menos un mes contiene dos cumpleaños.
Problema 2 - Tres personas en el mismo mes
¿Cuántas personas se necesitan para tener la certeza de que al menos 3 nacieron en el mismo mes?
Solución
Podemos colocar como máximo 2 personas en cada uno de los 12 meses: 12 × 2 = 24. La vigesimoquinta obliga a que algún mes tenga 3 personas. Respuesta: 25.
Problema 3 - Calcetines a oscuras
En un cajón hay calcetines de 5 colores diferentes. ¿Cuántos hay que sacar a oscuras para tener la certeza de obtener al menos dos del mismo color?
Solución
En el peor caso, los primeros 5 calcetines son todos de colores distintos. El sexto tiene que repetir uno de esos 5 colores. Respuesta: 6.
Problema 4 - Cuatro calcetines del mismo color
Hay calcetines de 6 colores. ¿Cuántos hay que sacar para tener la certeza de obtener al menos 4 del mismo color?
Solución
Podemos sacar 3 de cada color sin llegar a 4 iguales: 6 × 3 = 18. El siguiente fuerza un cuarto calcetín de algún color. Respuesta: 19.
Problema 5 - Restos módulo 5
Se eligen 6 números enteros cualesquiera. Demuestra que al menos dos dejan el mismo resto al dividirlos entre 5.
Solución
Los restos posibles son 0, 1, 2, 3, 4: solo 5 palomares. Entre 6 enteros, dos tienen necesariamente el mismo resto.
Problema 6 - Diferencia múltiplo de 5
Demuestra que entre 6 enteros siempre hay dos cuya diferencia es divisible entre 5.
Solución
Por el problema anterior, dos números tienen el mismo resto módulo 5. Si a = 5q + r y b = 5p + r, entonces a − b = 5(q − p); la diferencia es múltiplo de 5.
Problema 7 - Días de la semana
En un grupo de 15 personas, demuestra que al menos 3 nacieron el mismo día de la semana.
Solución
Si cada uno de los 7 días contuviera como máximo 2 personas, habría como máximo 7 × 2 = 14. La decimoquinta obliga a que un día contenga al menos 3.
Problema 8 - Última cifra
Se eligen 11 números naturales. Demuestra que al menos dos terminan en la misma cifra.
Solución
Las últimas cifras posibles son 0, 1, 2, …, 9: diez posibilidades. Con 11 números, al menos dos comparten la última cifra.
Problema 9 - Diferencia múltiplo de 10
Se eligen 11 enteros. Demuestra que existen dos cuya diferencia es múltiplo de 10.
Solución
Clasificamos los números por su resto módulo 10. Hay 10 clases; con 11 números, dos pertenecen a la misma clase y, por tanto, su diferencia es divisible entre 10.
Problema 10 - Al menos cinco
En una escuela hay 101 estudiantes repartidos entre 25 clases. Demuestra que alguna clase contiene al menos 5 estudiantes.
Solución
Si cada clase tuviera como máximo 4 estudiantes, el total sería como máximo 25 × 4 = 100. Como hay 101, alguna clase tiene al menos 5.
Problema 11 - Dos números consecutivos
Se eligen 6 números distintos del conjunto {1,2,…,10}. Demuestra que al menos dos son consecutivos.
Solución
Agrupamos los números en 5 parejas (1,2), (3,4), (5,6), (7,8), (9,10). Al elegir 6 números, al menos dos pertenecen a la misma pareja y son consecutivos.
Problema 12 - ¿Por qué 5 no bastan?
En el problema anterior, ¿bastarían 5 números?
Solución
No. El contraejemplo {1,3,5,7,9} contiene 5 números pero ninguna pareja de consecutivos. Por eso 6 es el umbral mínimo.
Problema 13 - Dos números que suman 11
Se eligen 6 números distintos entre 1 y 10. Demuestra que al menos dos suman 11.
Solución
Formamos las 5 parejas (1,10), (2,9), (3,8), (4,7), (5,6). Cada pareja suma 11. Al elegir 6 números, se elige por completo al menos una pareja. Suma = 11.
Problema 14 - Una diferencia pequeña
Se eligen 6 números distintos entre 1 y 10. Demuestra que al menos dos difieren como máximo en 1.
Solución
Usamos las parejas (1,2), (3,4), (5,6), (7,8), (9,10). Con 6 números, dos caen en la misma pareja; como son distintos, difieren exactamente en 1.
Problema 15 - Números del 1 al 100
Se eligen 51 números distintos entre 1 y 100. Demuestra que al menos dos son consecutivos.
Solución
Dividimos los 100 números en 50 parejas (1,2), (3,4), …, (99,100). Con 51 elecciones, al menos una pareja se elige entera.
Problema 16 - Diferencia divisible entre 7
Se eligen 8 enteros cualesquiera. Demuestra que dos difieren en un múltiplo de 7.
Solución
Cada entero tiene uno de los 7 restos 0,1,2,3,4,5,6 módulo 7. Con 8 enteros, dos tienen el mismo resto; su diferencia es divisible entre 7.
Problema 17 - Ciento un números entre 1 y 200
Se toman 101 enteros distintos comprendidos entre 1 y 200. Demuestra que al menos dos difieren menos de 2.
Solución
Al ser enteros distintos, diferir menos de 2 significa diferir exactamente en 1. Formamos las 100 parejas (1,2), (3,4), …, (199,200). Con 101 números, se elige entera alguna pareja.
Problema 18 - Puntos en un cuadrado
Se eligen 5 puntos en un cuadrado de lado 2. Demuestra que al menos dos distan como máximo √2.
Solución
Dividimos el cuadrado en 4 cuadrados de lado 1. Dos de los 5 puntos caen en el mismo cuadrado pequeño. La distancia máxima es su diagonal: d ≤ √2.
Problema 19 - Diez puntos en el cuadrado
Se eligen 10 puntos en un cuadrado de lado 3. Demuestra que al menos dos distan como máximo √2.
Solución
Dividimos el cuadrado en 9 cuadrados de lado 1. Con 10 puntos, dos caen en el mismo cuadrado pequeño y su distancia no supera su diagonal, √2.
Problema 20 - Personas y conocidos
En una fiesta hay 6 personas. Cada pareja se conoce o no se conoce. Demuestra que siempre hay tres que se conocen mutuamente o tres entre las cuales ninguna conoce a las otras dos.
Solución
Elegimos a una persona A. Entre las otras 5, al menos 3 conocen todas a A o al menos 3 no la conocen. En el primer caso, si dos de esas 3 se conocen, forman con A un trío de conocidos; si ninguna pareja se conoce, las 3 forman un trío de desconocidos. El segundo caso es simétrico. Es un pequeño ejemplo de la teoría de Ramsey.
Problema 21 - El mismo número de amigos
En una fiesta hay n ≥ 2 personas. Demuestra que al menos dos tienen el mismo número de amigos presentes.
Solución
Cada persona podría tener de 0 a n − 1 amigos, pero 0 y n − 1 no pueden aparecer a la vez: si alguien conoce a todos, nadie tiene 0 amigos. Así hay como máximo n − 1 cantidades posibles para n personas. Al menos dos comparten el mismo número de amigos.
Problema 22 - Dos subconjuntos con la misma suma
Se eligen 10 enteros positivos no superiores a 100. Demuestra que existen dos subconjuntos diferentes con la misma suma.
Solución
Distinguimos las diez posiciones elegidas aunque coincidan algunos valores. Generan 2¹⁰ = 1024 subconjuntos de posiciones, incluido el vacío. La suma total no supera 1000, de modo que hay como máximo 1001 sumas posibles, de 0 a 1000. Puesto que 1024 > 1001, dos subconjuntos distintos tienen la misma suma.
Problema 23 - Sumas parciales
Sean a₁,a₂,…,aₙ enteros cualesquiera. Demuestra que existe un bloque de términos consecutivos cuya suma es divisible entre n.
Solución
Consideramos las n sumas parciales S₁=a₁, S₂=a₁+a₂, …, Sₙ=a₁+…+aₙ. Si alguna es divisible entre n, hemos terminado. Si no, sus restos están entre 1,…,n − 1: n sumas en n − 1 clases. Dos sumas Sᵢ y Sⱼ tienen el mismo resto. Por tanto, su diferencia Sⱼ − Sᵢ = aᵢ₊₁+…+aⱼ es divisible entre n.
Problema 24 - Divisibilidad oculta
Se eligen 51 números distintos del conjunto {1,2,…,100}. Demuestra que entre ellos siempre hay dos tales que uno divide al otro.
Solución
Todo entero positivo se escribe de forma única como 2^k·m con m impar. Clasificamos los números por su parte impar m. Entre 1 y 100 hay 50 partes impares posibles. Con 51 números, dos comparten la misma parte impar: 2^a·m y 2^b·m. Si a<b, el segundo es 2^(b−a) veces el primero, así que el primero divide al segundo.
Problema 25 - Subsucesión creciente o decreciente
Se eligen 10 números distintos y se escriben en cierto orden. Demuestra que siempre hay una subsucesión creciente de al menos 4 números o una decreciente de al menos 4.
Solución
A cada término xᵢ asociamos Cᵢ, longitud de la subsucesión creciente más larga que termina en xᵢ, y Dᵢ, la longitud decreciente análoga. Si ninguna alcanzara longitud 4, tendríamos Cᵢ,Dᵢ ∈ {1,2,3}: solo 9 parejas posibles (Cᵢ,Dᵢ) para 10 términos. Dos términos compartirían una pareja. Pero para posiciones i<j, si xⱼ>xᵢ aumenta la longitud creciente posible, mientras que si xⱼ<xᵢ aumenta la decreciente. Una pareja idéntica es imposible: contradicción. 3 × 3 = 9 < 10.
6. ¿Qué hace difíciles estos problemas?
En los primeros ejercicios los palomares son evidentes: meses, colores, clases, días. En los problemas más interesantes hay que inventarlos. Pueden ser restos de una división, parejas de números, intervalos, regiones geométricas, partes impares, sumas posibles o parejas de propiedades. El principio matemático sigue siendo elemental; la verdadera dificultad consiste en elegir la clasificación adecuada.
7. Estrategia general
- ¿Cuáles son las palomas?
- ¿Cuáles podrían ser los palomares?
- ¿Cuántos palomares hay?
- ¿Cuál es el máximo de objetos que puedo colocar sin obtener el resultado?
- ¿Qué ocurre al añadir un objeto?
Pregunta clave: ¿cómo puedo clasificar los objetos para que el principio del palomar se vuelva inevitable?