Principio de las Casillas

Teoría

El Principio de las Casillas (también llamado principio de las cajas de Dirichlet) es una de las herramientas más simples pero más poderosas en combinatoria. Dice que si tienes más palomas que casillas, al menos una casilla debe tener más de una paloma.

A pesar de su sencillez, el principio es increíblemente útil para demostrar resultados de existencia; o sea, para mostrar que algo debe existir sin tener que construirlo explícitamente. El truco suele estar en identificar quiénes son las "palomas" y quiénes son las "casillas".

Algunas aplicaciones comunes incluyen:

• Probar que dos objetos deben compartir una propiedad
• Encontrar colisiones en conjuntos finitos
• Teoría de números (residuos, teorema de Dirichlet)
• Geometría (puntos en regiones)
• Teoría de gráficas (grados, aristas)

Fórmulas Clave

Principio de las Casillas Básico:

Si pones $n + 1$ objetos en $n$ cajas, entonces al menos una caja tiene al menos 2 objetos.

Principio de las Casillas Generalizado:

Si pones $n$ objetos en $k$ cajas, entonces al menos una caja tiene al menos $\lceil n/k \rceil$ objetos.

De forma equivalente: si $n > km$, entonces alguna caja tiene más de $m$ objetos.

Forma Fuerte:

Si pones $n_1 + n_2 + \cdots + n_k - k + 1$ objetos en $k$ cajas, entonces pasa alguna de estas cosas:

• La caja 1 tiene al menos $n_1$ objetos, o
• La caja 2 tiene al menos $n_2$ objetos, o
• ... o la caja $k$ tiene al menos $n_k$ objetos.

Demostración

Demostración del Principio de las Casillas Básico:

Supón por contradicción que cada una de las $n$ cajas tiene a lo más 1 objeto.

Entonces el número total de objetos es a lo más $n \cdot 1 = n$.

Pero tienes $n + 1$ objetos, lo cual es una contradicción.

Por lo tanto, al menos una caja debe tener al menos 2 objetos. $\square$

Demostración del Principio de las Casillas Generalizado:

Supón por contradicción que cada caja tiene a lo más $\lceil n/k \rceil - 1$ objetos.

Entonces el número total de objetos es a lo más: $$k \cdot (\lceil n/k \rceil - 1) = k \cdot \lceil n/k \rceil - k$$

Ahora, nota que $k \cdot \lceil n/k \rceil < k \cdot (n/k + 1) = n + k$.

Así que el total es menor que $(n + k) - k = n$.

Pero tienes $n$ objetos, lo cual es una contradicción.

Por lo tanto, al menos una caja tiene al menos $\lceil n/k \rceil$ objetos. $\square$

Demostración Alternativa (Argumento de Promedio):

Si distribuyes $n$ objetos en $k$ cajas, el promedio de objetos por caja es $n/k$.

Al menos una caja debe tener al menos el promedio (redondeado hacia arriba), que es $\lceil n/k \rceil$.

Para ser más precisos: si cada caja tuviera menos de $\lceil n/k \rceil$ objetos, el promedio sería menor que $\lceil n/k \rceil$. Como $\lceil n/k \rceil \leq \frac{n}{k} + 1$, tendrías un promedio $< n/k + 1$, lo que significa que el total sería $< n + k$. Para que la cuenta sea exactamente $n$, necesitas que alguna caja tenga $\geq \lceil n/k \rceil$. $\square$