Variantes del problema del cumpleaños.
El Principio de las Casillas Generalizado extiende el concepto básico de encontrar duplicados para encontrar multiplicidades más grandes. Mientras que el principio básico garantiza que distribuir $n+1$ objetos en $n$ recipientes resulta en que al menos un recipiente tenga 2 objetos, la versión generalizada te permite determinar las condiciones necesarias para garantizar que un recipiente tenga al menos $r$ objetos. Esta es una herramienta fundamental en combinatoria para resolver problemas del "peor de los casos", particularmente aquellos que involucran cantidades discretas y conjuntos finitos.
Este concepto se aplica seguido a las "variantes del Problema del Cumpleaños". En probabilidad, la Paradoja del Cumpleaños trata sobre la probabilidad de que dos personas compartan un cumpleaños. Sin embargo, en el contexto del Principio de las Casillas, lo que buscas es la certeza. Estas aplicaciones te piden el tamaño mínimo de población necesario para garantizar que al menos $r$ personas compartan un cumpleaños (o cualquier otra propiedad). La intuición se basa en el "principio del promedio": si el promedio de objetos por recipiente es $A$, entonces debe haber al menos un recipiente que tenga una cantidad mayor o igual a $A$. Si distribuyes los objetos lo más uniformemente posible para evitar crear un recipiente "amontonado", eventualmente llegas a un punto de saturación donde agregar un objeto más obliga a cruzar un umbral específico.
En matemáticas de competencia como el AMC 12 y el AIME, estas aplicaciones suelen aparecer disfrazadas en problemas de geometría, teoría de números o teoría de conjuntos. La clave siempre es identificar las "palomas" (los objetos que se distribuyen) y las "casillas" (las categorías o propiedades que poseen). Una vez que las identificas, el problema se reduce a calcular el número máximo de objetos que pueden existir sin que se cumpla la condición, y luego sumarle uno.
El Principio de las Casillas Generalizado (Forma de Techo) Si colocas $N$ objetos en $k$ cajas, entonces existe al menos una caja que contiene al menos $\lceil N/k \rceil$ objetos, donde $\lceil x \rceil$ denota la función techo (el entero más pequeño mayor o igual a $x$). $$ \exists \text{ caja } i \text{ tal que } |caja_i| \ge \left\lceil \frac{N}{k} \right\rceil $$
El Principio de las Casillas Generalizado (Forma de Umbral) Si distribuyes $kn + 1$ objetos entre $n$ cajas, entonces al menos una caja contiene al menos $k + 1$ objetos.
La Fórmula del "Peor de los Casos" (Problema Inverso) Para garantizar que al menos una caja contenga $r$ objetos cuando hay $k$ cajas disponibles, el número mínimo de objetos $N$ que necesitas es: $$ N = k(r - 1) + 1 $$ Esto viene del peor escenario posible donde cada caja contiene exactamente $r-1$ objetos.
Aplicación a Variantes de Cumpleaños Para garantizar que al menos $r$ personas compartan un cumpleaños (asumiendo 366 cumpleaños posibles): $$ \text{Personas necesarias} = 366(r - 1) + 1 $$
Teorema: Si colocas $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. Escribe $x_i$ como el 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} x_i = N $$
Toma $m = \lceil N/k \rceil$. Lo que hay que demostrar es que existe algún $j$ tal que $x_j \ge m$.
Supón, para llegar a una contradicción, que la afirmación es falsa. Esto significa que cada caja contiene menos de $m$ objetos. Como el número de objetos en una caja debe ser un entero, esto implica que: $$ x_i \le m - 1 \quad \text{para todo } i = 1, \dots, k $$
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) $$ $$ \sum_{i=1}^{k} x_i \le k(m - 1) $$
Sustituye $m = \lceil N/k \rceil$ de nuevo en la desigualdad. Por la definición de la función techo, sabes que $\lceil N/k \rceil < \frac{N}{k} + 1$. Por lo tanto: $$ m - 1 < \frac{N}{k} $$
Multiplica ambos lados por $k$ (ya que $k > 0$): $$ k(m - 1) < N $$
Al combinar esto con la desigualdad de la suma: $$ \sum_{i=1}^{k} x_i \le k(m - 1) < N $$ $$ \sum_{i=1}^{k} x_i < N $$
Esto dice que el número total de objetos es estrictamente menor que $N$, lo cual contradice el hecho de que hay exactamente $N$ objetos.
Por lo tanto, la suposición inicial tiene que ser falsa. Es imposible que todas las cajas tengan menos de $\lceil N/k \rceil$ objetos. Así que al menos una caja debe contener al menos $\lceil N/k \rceil$ objetos. $\square$