El principio del palomar afirma que, al distribuir más objetos que recipientes, al menos un recipiente debe contener varios objetos. Esta idea elemental permite demostrar la existencia inevitable de repeticiones, colisiones y agrupamientos.
El principio del palomar, también llamado principio de Dirichlet, parece evidente: si hay más palomas que palomares, algún palomar debe alojar al menos dos palomas. Su potencia está en aplicarlo a objetos que no parecen palomas ni recipientes.
En programación, los objetos pueden ser datos, solicitudes, valores de un arreglo o mensajes; los recipientes pueden ser índices, clases de residuos, cubetas de una tabla hash o días del año. Identificar correctamente esta correspondencia es la parte creativa del razonamiento.
Si se colocan n + 1 objetos en n recipientes, entonces al menos un recipiente contiene dos o más objetos.
El principio no dice cuáles son esas dos personas ni en qué mes nacieron. Garantiza solamente que una coincidencia existe.
Supongamos que n + 1 objetos se distribuyen en n recipientes y que ningún recipiente recibe más de un objeto. Entonces cada recipiente contiene como máximo un objeto.
La suposición era falsa, por lo que al menos un recipiente debe contener dos objetos. La prueba es corta, pero se reutiliza una y otra vez en problemas de conteo.
Antes de aplicar el principio debemos definir con precisión qué se está distribuyendo y dónde. Una mala elección puede llevar a una conclusión incorrecta.
Los enteros pueden ser todos diferentes, pero al clasificarlos por su residuo solo hay 25 clases. Dos de ellos necesariamente caen en la misma clase.
Los residuos módulo m forman exactamente m recipientes: 0, 1, ..., m - 1. Por ello, entre m + 1 enteros cualesquiera existen dos congruentes módulo m.
Esta observación une el principio con la aritmética modular. Es una fuente frecuente de demostraciones de divisibilidad y de resultados sobre ciclos.
Si ignoramos el 29 de febrero, hay 365 días posibles para un cumpleaños. En un grupo de 366 personas, al menos dos cumplen años el mismo día del año.
Este resultado es seguro. No debe confundirse con la pregunta probabilística de cuántas personas se necesitan para que una coincidencia sea probable: eso corresponde al problema del cumpleaños y requiere calcular probabilidades.
Consideremos seis enteros elegidos de 1 a 10. Cada uno puede asociarse a su distancia respecto de un valor fijo, por ejemplo 5, o a otra clasificación adecuada. El desafío consiste en escoger recipientes que representen la propiedad buscada.
Este tipo de ejercicio ilustra que el principio no sustituye el modelado: contar objetos y recipientes es simple después de decidir qué rasgo comparten los objetos que caen en un mismo recipiente.
Si se colocan N objetos en k recipientes, entonces algún recipiente contiene al menos ⌈N/k⌉ objetos. El símbolo techo redondea hacia arriba.
No se afirma que todos los recipientes tengan esa cantidad. El resultado garantiza un mínimo para el recipiente más cargado.
Supongamos que ningún recipiente contiene ⌈N/k⌉ objetos. Entonces todos contienen a lo sumo ⌈N/k⌉ - 1 objetos.
La fórmula general es la versión cuantitativa del principio básico. En vez de garantizar solo un par, garantiza cuántos objetos deben acumularse en algún recipiente.
Si se asignan 53 tareas a 8 trabajadores, incluso con una distribución tan equilibrada como sea posible, alguien recibirá al menos ⌈53/8⌉ = 7 tareas.
El principio proporciona una cota inevitable. No decide la política de reparto ni asegura equilibrio temporal, dificultad similar o disponibilidad de los trabajadores.
Una función es inyectiva si elementos distintos del dominio siempre tienen imágenes distintas. Si el dominio finito tiene más elementos que el codominio, no puede existir una función inyectiva.
Esta es la formulación abstracta del principio del palomar. Los objetos son los elementos del dominio; los recipientes son los valores posibles del codominio.
Una tabla hash con capacidad m transforma claves en uno de m índices. Si se insertan más de m claves distintas, por el principio del palomar al menos dos terminan en el mismo índice: ocurre una colisión.
Las implementaciones deben resolverlas mediante encadenamiento, direccionamiento abierto u otra estrategia. Una buena función hash busca repartir mejor las claves, no hacer imposible una colisión.
function modulo(a, m) {
return ((a % m) + m) % m;
}
function primeraColisionModulo(valores, m) {
if (!Number.isInteger(m) || m <= 0) throw new Error("m debe ser positivo");
const visto = new Map();
for (const valor of valores) {
const residuo = modulo(valor, m);
if (visto.has(residuo)) {
return { primero: visto.get(residuo), segundo: valor, residuo };
}
visto.set(residuo, valor);
}
return null;
}
console.log(primeraColisionModulo([11, 25, 8, 19], 7));
// { primero: 11, segundo: 25, residuo: 4 }La función encuentra una colisión concreta si aparece. El principio del palomar garantiza que la función devolverá una colisión si recibe más de m valores, aunque los valores exactos no se conozcan de antemano.
Un arreglo de n + 1 enteros no garantiza un duplicado si sus valores pueden ocupar n + 1 posibilidades distintas, por ejemplo de 0 a n. Para garantizar repetición, el rango debe contener como máximo n valores.
Es importante contar con precisión. Un error de uno en los límites puede cambiar una afirmación segura en una afirmación falsa.
function primerDuplicado(valores) {
const vistos = new Set();
for (const valor of valores) {
if (vistos.has(valor)) return valor;
vistos.add(valor);
}
return null;
}
console.log(primerDuplicado([4, 9, 2, 7, 9, 1])); // 9
console.log(primerDuplicado([4, 9, 2, 7])); // nullEl principio prueba que un duplicado debe existir bajo ciertas condiciones; el algoritmo anterior lo localiza. Esta diferencia entre existencia matemática y construcción algorítmica es fundamental.
El principio del palomar es no constructivo en su forma básica: asegura que hay una coincidencia, pero no identifica dónde está. Para encontrarla necesitamos inspeccionar los datos o una estructura auxiliar.
En informática teórica y diseño de algoritmos, esta distinción ayuda a separar una propiedad del problema de la estrategia usada para resolverlo.
Un hash de longitud fija transforma un conjunto enorme de mensajes posibles en una cantidad finita de resultados. Por el principio del palomar, necesariamente existen mensajes distintos con el mismo hash.
La seguridad de un hash criptográfico no significa que no haya colisiones; significa que debería ser computacionalmente inviable encontrarlas de manera práctica. Para seguridad real se usan funciones y bibliotecas criptográficas reconocidas, no hashes inventados.
El principio responde a preguntas del tipo «¿es inevitable que ocurra?». No responde «¿qué tan probable es que ocurra antes de ese límite?».
Mezclar garantía y probabilidad lleva a interpretaciones incorrectas en pruebas, capacidad de sistemas y seguridad de hashes.
Un identificador de k bits admite 2k valores distintos. Si se crean más de 2k objetos y cada uno recibe solo ese identificador, una repetición es inevitable.
La observación se aplica a códigos temporales, índices, nombres acortados y claves de una base de datos. Aumentar el espacio de identificadores reduce colisiones, pero un espacio finito siempre tiene un límite.
El último paso es crucial. Si los recipientes son residuos, caer en el mismo recipiente significa ser congruentes; si son cubetas, significa una colisión; si son meses, significa compartir mes de nacimiento.
El principio del palomar transforma un conteo sencillo en una demostración de existencia muy poderosa. En el próximo tema combinaremos conjuntos y contaremos elementos sin duplicarlos mediante el principio de inclusión y exclusión.