Principio del palomar
El principio del palomar es una técnica de conteo clásica en matemáticas y combinatoria. Afirma que si se tienen más elementos que casillas para colocarlos, entonces al menos una casilla debe contener más de un elemento.
El principio es sorprendentemente simple, pero muy poderoso. Se utiliza para demostrar que ciertas situaciones son inevitables, sin importar cómo se distribuyan los elementos. Existe una versión simple y una general.
Principio simple del palomar
Si se tienen k + 1 elementos que deben distribuirse en k casillas, entonces al menos una casilla contendrá más de un elemento.
Ejemplo 1: Cumpleaños
En un grupo de 13 personas, al menos dos deben tener su cumpleaños en el mismo mes, ya que solo hay 12 meses.
Ejemplo 2: Calcetines
Si tienes 3 calcetines pero solo 2 colores (por ejemplo negro y blanco), entonces al menos dos calcetines tendrán el mismo color.
Demostración (simple)
Supongamos lo contrario: que ninguna casilla contiene más de un elemento. Entonces puede haber como máximo k elementos en k casillas. Pero tenemos k + 1 elementos. Esto es una contradicción, por lo tanto al menos una casilla debe tener más de un elemento.
Principio general del palomar
Si se distribuyen N elementos en k casillas, al menos una casilla contendrá al menos:
$$ \large \left\lceil \frac{N}{k} \right\rceil $$
Esto significa que siempre se puede garantizar una distribución mínima, sin importar cómo se coloquen los elementos.
Ejemplo 1: Partido de fútbol
Hay 40.000 espectadores en un partido y 365 posibles cumpleaños. Al menos un cumpleaños es compartido por:
$$ \large \left\lceil \frac{40000}{365} \right\rceil = 110 $$
Esto significa que al menos 110 personas comparten cumpleaños.
Ejemplo 2: Juego de cartas
En una baraja de 52 cartas sin comodines, las cartas se dividen en 4 palos. Si se roban 21 cartas, entonces al menos un palo tendrá:
$$ \large \left\lceil \frac{21}{4} \right\rceil = 6 $$
Por lo tanto, se garantiza tener al menos 6 cartas del mismo palo.
Demostración (general)
Si todas las casillas tuvieran como máximo \( \large \left\lfloor \frac{N}{k} \right\rfloor \) elementos, entonces el número total de elementos sería como máximo \( \large k \cdot \left\lfloor \frac{N}{k} \right\rfloor \leq N \). Pero si este fuera el caso, faltaría espacio para algunos elementos. Por lo tanto, al menos una casilla debe tener \( \large \left\lceil \frac{N}{k} \right\rceil \) elementos.
Aplicaciones
El principio del palomar parece simple, pero se usa en muchos contextos avanzados:
- Combinatoria: Demostraciones sobre permutaciones y combinaciones.
- Probabilidad: Mostrar que ciertos resultados son inevitables.
- Teoría de grafos: Garantizar que un grafo tenga nodos con conexiones específicas.
- Informática: Funciones hash y almacenamiento de datos – si hay más elementos que espacios, deben producirse colisiones.
Resumen
El principio del palomar dice que si se tienen más elementos que casillas, entonces al menos una casilla debe contener más de un elemento. La versión general nos da la fórmula:
$$ \large \left\lceil \frac{N}{k} \right\rceil $$
El principio puede demostrarse de forma sencilla, pero tiene aplicaciones profundas en matemáticas e informática. Garantiza que podamos entender cuándo algo es inevitable, y es una herramienta importante en combinatoria y probabilidad.