Principio de las Casillas

Teoría

El Principio de las Casillas (también conocido como el Principio del Palomar de Dirichlet) es un concepto fundamental en combinatoria que formaliza la idea del "traslape inevitable". En su forma más simple, dice que si distribuyes $n+1$ objetos ("palomas") en $n$ contenedores ("casillas"), entonces al menos un contenedor debe tener más de un objeto. Aunque esto parece obvio por intuición, te da una herramienta muy poderosa para demostrar que algo existe sin necesidad de construir un ejemplo específico. Transforma problemas de complejidad continua o infinita en restricciones discretas y finitas.

Este principio aparece por todos lados en las matemáticas de competencia, desde teoría de números hasta geometría y teoría de gráficas. Lo usas principalmente para demostrar que existe cierta configuración, propiedad numérica o arreglo geométrico. Por ejemplo, puedes demostrar que en un grupo de personas, al menos dos deben tener el mismo número de amigos presentes, o que un algoritmo de compresión sin pérdida no puede comprimir todos los archivos. El principio no es constructivo; te dice que algo existe, pero no necesariamente cuál es el objeto específico que cumple la condición o dónde está.

El truco para aplicar el Principio de las Casillas no está en el teorema en sí, sino en cómo modelas el problema. La dificultad normalmente viene de identificar correctamente qué son las "palomas" (los objetos que vas a distribuir) y qué son las "casillas" (las categorías o particiones). Muchas veces, las "casillas" se definen por residuos módulo $n$, subconjuntos de una partición o regiones dentro de una figura geométrica. Una estrategia común es considerar el "peor escenario posible" —intentar distribuir los objetos de la forma más uniforme que puedas— y demostrar que las restricciones te obligan a romper esa uniformidad.

Fórmulas Clave

1. El Principio de las Casillas Básico Si pones $n+1$ objetos en $n$ cajas, entonces al menos una caja contiene al menos $2$ objetos. $$ \text{Si } |X| > |Y| \text{ y } f: X \to Y, \text{ entonces } f \text{ no es inyectiva.} $$

2. El Principio de las Casillas Generalizado Si pones $N$ objetos en $k$ cajas, entonces al menos una caja contiene al menos $\lceil N/k \rceil$ objetos, donde $\lceil x \rceil$ es la función techo (el entero más pequeño que es mayor o igual a $x$). $$ \exists y \in Y \text{ tal que } |f^{-1}(y)| \ge \left\lceil \frac{|X|}{|Y|} \right\rceil $$ Corolario: Para asegurar que al menos $r$ objetos terminen en la misma caja, tienes que distribuir al menos $k(r-1) + 1$ objetos en $k$ cajas.

3. Teorema de Erdős-Szekeres Esta es una aplicación famosa del Principio de las Casillas sobre sucesiones. Para cualquier sucesión de $(r-1)(s-1) + 1$ números reales distintos, existe:

• Una subsucesión creciente de longitud $r$, O
• Una subsucesión decreciente de longitud $s$.

Demostración

Teorema: El Principio de las Casillas Generalizado. 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 usar una contradicción.

Toma $N$ como el número total de objetos y $k$ como el número de cajas. Llama $n_i$ al número de objetos en la $i$-ésima caja, para $i = 1, 2, \dots, k$. Sabes que la suma de los objetos en todas las cajas debe ser igual al total de objetos: $$ \sum_{i=1}^{k} n_i = N $$

Sea $M = \lceil N/k \rceil$. Lo que hay que demostrar es que existe alguna caja $j$ tal que $n_j \ge M$.

Supón, para llegar a una contradicción, que esto es falso. Esto significa que cada caja contiene estrictamente menos de $M$ objetos. $$ n_i < M \quad \text{para todo } i = 1, \dots, k $$

Como $n_i$ tiene que ser un entero, si $n_i < M$, entonces $n_i \le M - 1$. Ahora suma el número de objetos en todas las cajas bajo esta suposición: $$ \sum_{i=1}^{k} n_i \le \sum_{i=1}^{k} (M - 1) = k(M - 1) $$

Sustituye $M = \lceil N/k \rceil$. Por la definición de la función techo, sabes que $\lceil N/k \rceil \ge N/k$. Una propiedad útil es que $M - 1 = \lceil N/k \rceil - 1 < N/k$.

Por lo tanto: $$ \sum_{i=1}^{k} n_i \le k(M - 1) < k\left(\frac{N}{k}\right) = N $$

Esto te lleva a la desigualdad: $$ \sum_{i=1}^{k} n_i < N $$

Esto contradice la premisa fundamental de que el número total de objetos distribuidos es $N$. Es imposible que la suma de las partes sea estrictamente menor que el todo.

Entonces, la suposición de que cada caja tiene menos de $\lceil N/k \rceil$ objetos debe ser falsa. Por lo tanto, al menos una caja tiene que contener al menos $\lceil N/k \rceil$ objetos. $\square$