Conteo · Definición
Principio del palomar
Antes de empezar necesitas conocer
Garantiza que algo se repite sin necesidad de construirlo ni de saber exactamente cómo se reparten los objetos.
Definición
Si se colocan \(n\) objetos en \(k\) cajas, alguna caja contiene al menos \(\lceil n/k\rceil\) objetos, y en particular dos cuando \(n>k\).
El enunciado básico es casi una obviedad: si hay más palomas que nidos, algún nido recibe dos palomas. Su fuerza está en elegir bien quiénes son las «cajas». En el problema de 13 personas y 12 meses, las cajas son los meses; con 8 enteros y los 7 residuos posibles al dividir entre 7, las cajas son los residuos.
La versión general dice que, si \(n>mk\), alguna caja contiene al menos \(m+1\) objetos; en forma compacta, alguna caja recibe \(\lceil n/k\rceil\) o más. Por ejemplo, 100 personas en 12 meses obligan a que algún mes tenga \(\lceil 100/12\rceil=9\) personas. Para garantizar un cierto número se razona al revés: lo máximo que se puede evitar es \(m\) objetos por caja, es decir \(mk\) objetos en total, así que el objeto \(mk+1\) rompe la evasión.
El principio es solo de existencia: asegura que hay una caja con muchos objetos, pero no dice cuál ni cómo encontrarla. Muchas demostraciones consisten en inventar las cajas, como los pares \(\{a,\,13-a\}\) para sumas iguales a 13, o las clases de residuos módulo \(k\).
Errores típicos: olvidar el redondeo hacia arriba (\(\lceil 7.5\rceil=8\), no 7), contar mal las cajas (hay 7 residuos módulo 7, no 6) o usarlo para afirmar que una caja tiene exactamente cierto número de objetos, cuando el principio solo da una cota inferior.
Para pensar
¿Cuántos calcetines de 3 colores hay que sacar a ciegas para asegurar un par del mismo color?
Cuatro: con tres pueden ser de colores distintos y el cuarto repite color (3 cajas, 4 objetos).
Si hay 25 objetos en 6 cajas, ¿se puede asegurar que alguna caja tiene exactamente 5?
No. Solo se asegura \(\lceil 25/6\rceil=5\) o más: alguna caja tiene al menos 5, pero podría tener más.
Ejercicios 10
- En un grupo hay 13 personas. ¿Qué se puede afirmar con certeza sobre sus meses de nacimiento?
- Se reparten 30 canicas en 4 cajas. ¿Cuál es el mayor número que se puede garantizar como mínimo en alguna caja?
- ¿Cuántas cartas de una baraja de 52 (4 palos) hay que tomar como mínimo para garantizar dos del mismo palo?
- ¿Cuántas personas se necesitan como mínimo para garantizar que al menos 9 cumplen años en el mismo mes, si hay 12 meses?
- Se reparten 100 personas según su mes de nacimiento (12 meses). ¿Cuántas, como mínimo, comparten mes con seguridad en algún mes?
- ¿Cuántos enteros hay que elegir como mínimo para garantizar que dos tengan el mismo residuo al dividir entre 7?
- Un cajón tiene calcetines sueltos de 3 colores. Sin ver, ¿cuántos hay que sacar como mínimo para garantizar un par del mismo color?
- Una lista tiene 1000 palabras distintas del español. Usando 26 letras iniciales, ¿cuántas palabras con la misma inicial se pueden garantizar?
- Se eligen 7 números del conjunto \(\{1,2,\dots,12\}\). ¿Cuál afirmación es siempre verdadera?
- Se eligen 21 enteros. ¿Cuántos, como mínimo, terminan con la misma cifra de las unidades con seguridad?
Referencias
- Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §6.2
- Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §9.4
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §5.5