El principio de las palomas (también llamado principio del palomar o principio de las casillas) afirma de forma intuitiva que si se colocan más objetos que contenedores, entonces al menos un contenedor debe contener más de un objeto. En la metáfora clásica las «palomas» representan los objetos y los «agujeros» (o casillas) los contenedores; por ejemplo, si hay más palomas que agujeros, alguna paloma tendrá que compartir agujero con otra.

Formulación precisa y variante cuantitativa

Sea m el número de objetos (palomas) y n el número de contenedores (agujeros). El enunciado básico es:

  • Si m > n, entonces existe al menos un contenedor que contiene al menos 2 objetos.

Una forma más fuerte y útil es la versión cuantitativa:

  • Si m objetos se distribuyen en n contenedores, entonces algún contenedor contiene al menos ceiling(m / n) = ⌈m/n⌉ objetos.

Equivalentemente, si cada contenedor tuviera como máximo k objetos, entonces m ≤ k·n; por lo tanto, si m > k·n, alguno debe tener más de k objetos.

Boceto de demostración

La demostración es sencilla por contradicción o por argumento de promedio. Si ningún contenedor tuviera ≥ ⌈m/n⌉ objetos, entonces todos tendrían como máximo ⌈m/n⌉ − 1, lo que implicaría que el total m sería ≤ n·(⌈m/n⌉ − 1) < n·(m/n) = m, contradicción. Otra forma: el número medio de objetos por contenedor es m/n, por tanto al menos uno debe tener un número ≥ media.

Ejemplos sencillos

  • Si hay 13 personas y 12 meses, al menos dos personas cumplen años en el mismo mes.
  • Si colocas 7 calcetines en 6 cajones, algún cajón tendrá al menos 2 calcetines.
  • Si 25 cartas se reparten en 4 manos, alguna mano tendrá al menos ⌈25/4⌉ = 7 cartas.

Aplicaciones en matemáticas

  • Teoría de números: para demostrar que en cualquier conjunto de n+1 enteros existe un par cuya diferencia es divisible por n (considérense las clases residuales módulo n).
  • Combinatoria: en demostraciones de existencia (por ejemplo, existencia de coincidencias, repeticiones o subestructuras obligatorias en configuraciones finitas).
  • Teoría de grafos: para probar que un grafo finito tiene un vértice con grado al menos la media de los grados, o para argumentos sobre coloraciones y distribuciones de aristas.
  • Aproximación de números reales: el principio de Dirichlet (a veces relacionado con el principio del palomar) se usa para obtener aproximaciones racionales de números reales.

Aplicaciones en informática

Este teorema es fundamental en informática y en matemáticas, tanto para resultados teóricos como para análisis prácticos:

  • Hashing: con un número finito de posiciones en una tabla hash, asignar más claves que posiciones garantiza colisiones; el principio cuantitativo da estimaciones mínimas de ocupación.
  • Balanceo de carga: al distribuir tareas entre un número fijo de servidores, si hay más tareas que servidores alguno procesará varias tareas.
  • Comprobaciones de inyectividad: para demostrar que no existe una función inyectiva entre dos conjuntos finitos cuando el dominio es mayor que el codominio.
  • Algoritmos y pruebas de existencia: se usa para garantizar la existencia de configuraciones adversas o coincidencias necesarias en pruebas de corrección y complejidad.

Consejos y aclaraciones

  • No debe confundirse con fenómenos probabilísticos: el principio es una afirmación determinista sobre conteo, aunque aparece en argumentos probabilísticos como el problema del cumpleaños.
  • Se aplica únicamente a conjuntos finitos o a particiones discretas; en contextos continuos hay análogos medidos con medidas y densidades, pero requieren formulaciones distintas.

En resumen, el principio de las palomas es una herramienta elemental pero poderosa para demostrar la existencia de coincidencias, colisiones o repeticiones en situaciones discretas, con aplicaciones que van desde problemas elementales hasta resultados avanzados en teoría de grafos, teoría de números y ciencia de la computación.