n objetos en k cajas implica ⌈n/k⌉ en una.
El Principio de las Casillas Generalizado extiende la garantía básica de "existencia" del principio estándar a un límite cuantitativo. Mientras que el principio estándar te dice que meter $n+1$ objetos en $n$ cajas resulta en una colisión (una caja con al menos 2 objetos), la fórmula generalizada te permite predecir grupos más grandes. Específicamente, si distribuyes un número grande de objetos $n$ en un número menor de cajas $k$, puedes garantizar que al menos una caja contiene un número de objetos igual o mayor que el promedio redondeado hacia arriba.
Este concepto es fundamental en combinatoria porque te da una garantía del "peor de los casos". Cuando resuelves problemas, muchas veces buscas una configuración específica o un subconjunto de cierto tamaño. El Principio de las Casillas Generalizado te permite demostrar que tal configuración existe simplemente contando el total de elementos y las categorías disponibles. Básicamente es un argumento de promedio: no puedes tener todas las cajas con menos objetos que el promedio. Si el promedio no es un entero, al menos una caja tiene que superar ese promedio.
Intuitivamente, para evitar que una caja tenga muchos objetos, intentarías repartir los $n$ objetos lo más parejo posible entre las $k$ cajas. Esta es la distribución "más uniforme". Incluso en esta distribución óptima, si $n$ no es múltiplo de $k$, algunas cajas tienen que cargar con el resto. Por lo tanto, la carga máxima de una sola caja nunca puede ser menor que el techo del promedio, $\lceil n/k \rceil$.
La fórmula principal para el Principio de las Casillas Generalizado se escribe así:
Si pones $n$ objetos en $k$ cajas, entonces existe al menos una caja que contiene al menos $$ \left\lceil \frac{n}{k} \right\rceil $$ objetos, donde $\lceil x \rceil$ es la función techo (el entero más pequeño que es mayor o igual a $x$).
Formulación Alternativa: A veces es útil escribir $n$ en términos del tamaño del grupo que buscas. Para garantizar que al menos una caja contenga $r$ objetos, el número mínimo de objetos $n$ que necesitas es: $$ n = k(r - 1) + 1 $$
El Principio Dual: Por otro lado, existe al menos una caja que contiene a lo mucho $$ \left\lfloor \frac{n}{k} \right\rfloor $$ objetos, donde $\lfloor x \rfloor$ es la función piso.
Teorema: Si pones $n$ objetos en $k$ cajas, entonces al menos una caja contiene al menos $\lceil n/k \rceil$ objetos.
Demostración: La idea es demostrarlo por contradicción.
Llama $x_1, x_2, \dots, x_k$ al número de objetos en cada caja. Sabes que el número total de objetos es $n$, así que: $$ \sum_{i=1}^{k} x_i = n $$
Digamos que $M = \lceil n/k \rceil$. Lo que hay que demostrar es que existe algún $i$ tal que $x_i \ge M$.
Supón, para llegar a una contradicción, que esto es falso. Esto quiere decir que cada caja contiene estrictamente menos de $M$ objetos. Como el número de objetos en una caja debe ser un entero, esto significa que para todo $i \in {1, \dots, k}$: $$ x_i \le M - 1 $$
Ahora, suma el número de objetos en todas las cajas basándote en esta suposición: $$ \sum_{i=1}^{k} x_i \le \sum_{i=1}^{k} (M - 1) = k(M - 1) $$
Sustituye $M = \lceil n/k \rceil$ de nuevo en la desigualdad: $$ \text{Total de objetos} \le k\left(\left\lceil \frac{n}{k} \right\rceil - 1\right) $$
Por la definición de la función techo, sabes que $\lceil x \rceil < x + 1$. Por lo tanto, $\lceil n/k \rceil < n/k + 1$, lo que significa que: $$ \left\lceil \frac{n}{k} \right\rceil - 1 < \frac{n}{k} $$
Si usas esta desigualdad estricta en la suma: $$ \text{Total de objetos} \le k\left(\left\lceil \frac{n}{k} \right\rceil - 1\right) < k\left(\frac{n}{k}\right) = n $$
Esto te lleva a la conclusión de que el número total de objetos es estrictamente menor que $n$: $$ \sum_{i=1}^{k} x_i < n $$
Esto contradice el hecho de que hay exactamente $n$ objetos. Por lo tanto, la suposición inicial tiene que ser falsa, y debe existir al menos una caja que contenga al menos $\lceil n/k \rceil$ objetos. $\square$