Si se distribuyen más objetos que casillas, al menos una casilla debe contener dos o más objetos.
El principio del palomar, también llamado principio de Dirichlet, permite demostrar que una coincidencia es inevitable sin identificar exactamente dónde ocurre.
La idea es simple: si hay pocas categorías para muchos elementos, no es posible colocar cada elemento en una categoría diferente.
Si se colocan n+1 objetos en n casillas, al menos una casilla contiene dos o más objetos.
No importa cómo se realice la distribución. La coincidencia está garantizada por la diferencia entre la cantidad de objetos y de casillas.
Si hay 13 personas y solo 12 meses posibles de nacimiento, al menos dos personas nacieron en el mismo mes.
No necesitamos saber los meses concretos para garantizar la coincidencia.
Indica la cantidad de objetos y casillas. La simulación distribuye los objetos de forma ordenada y muestra la casilla que contiene la mayor cantidad.
Supongamos que ninguna casilla tuviera dos objetos. Entonces cada casilla tendría como máximo un objeto.
Pero se colocaron n+1 objetos. Esto contradice la suposición, por lo que alguna casilla debe tener al menos dos.
Si se distribuyen N objetos en k casillas, alguna casilla contiene al menos:
El símbolo ⌈x⌉ representa el menor entero mayor o igual que x. Esta versión indica una cantidad mínima garantizada en alguna casilla.
Si se distribuyen 25 registros entre 6 categorías:
Al menos una categoría contiene 5 registros. Puede contener más, pero no es posible que todas tengan como máximo 4.
Podemos calcular la cantidad mínima garantizada en una casilla con la función techo.
function minimoGarantizado(objetos, casillas) {
return Math.ceil(objetos / casillas);
}
console.log(minimoGarantizado(25, 6));
console.log(minimoGarantizado(13, 12));El resultado es 5 para 25 objetos en 6 casillas y 2 para 13 objetos en 12 casillas.
El principio garantiza que existe una coincidencia, pero no necesariamente identifica cuál. Para encontrarla, podemos recorrer una lista y registrar la categoría de cada elemento.
function encontrarRepetido(elementos) {
const vistos = new Set();
for (const elemento of elementos) {
if (vistos.has(elemento)) return elemento;
vistos.add(elemento);
}
return null;
}
console.log(encontrarRepetido(["A", "B", "C", "B"]));El algoritmo encuentra un caso concreto, mientras que el principio del palomar solo necesita comparar cantidades para garantizar que existe alguno.
Al dividir enteros por un número k, solo existen k restos posibles: 0, 1, ..., k-1. Si tomamos k+1 enteros, dos deben tener el mismo resto.
Esta observación aparece en demostraciones sobre divisibilidad y en algoritmos que agrupan valores por clases de resto.
El principio del palomar permite demostrar que ciertas coincidencias son inevitables cuando la cantidad de objetos supera la cantidad de categorías disponibles. Su fuerza está en garantizar una conclusión sin conocer la distribución exacta.
En el próximo tema estudiaremos el conteo mediante complemento, una estrategia que cuenta los casos válidos restando los casos que no cumplen una condición.