Pruebas de Existencia

Teoría

En el contexto de la combinatoria y las matemáticas de competencia, una prueba de existencia es un argumento lógico que demuestra que un objeto con propiedades específicas tiene que existir, sin que necesariamente tengas que construir el objeto o dar un algoritmo para encontrarlo. Estas pruebas suelen ser "no constructivas". Mientras que las pruebas constructivas muestran la existencia identificando explícitamente un ejemplo (por ejemplo, "aquí hay un número $x$ que cumple la condición"), las pruebas de existencia no constructivas se basan en la necesidad lógica. Argumentan que si tal objeto no existiera, se llegaría a una contradicción lógica o se violaría un principio fundamental de conteo.

La herramienta más importante para las pruebas de existencia en el AMC 10/12 y en las Olimpiadas es el Principio de las Casillas (también conocido como el Principio del Palomar o de Dirichlet). La intuición es simple: si tienes más objetos que contenedores, y tienes que poner cada objeto en un contenedor, al menos un contenedor debe tener más de un objeto. Aunque esta observación parece trivial, te da un mecanismo muy poderoso para probar la existencia de patrones complejos, relaciones numéricas o configuraciones geométricas. Por ejemplo, puedes probar que en cualquier grupo de 6 personas, existe un grupo de 3 amigos mutuos o 3 desconocidos mutuos, sin saber nada sobre las personas específicas involucradas.

La clave para resolver estos problemas es identificar correctamente los "pichones" (los objetos que vas a distribuir) y las "casillas" (las categorías o propiedades). La dificultad muchas veces no está en el principio en sí, sino en definir estos conjuntos de tal forma que una "colisión" (dos pichones en una casilla) garantice que existe la estructura que buscas. Estas pruebas se basan mucho en pensar en el "peor escenario posible": incluso si intentas distribuir los elementos de la forma más uniforme posible para evitar la condición, la cantidad de elementos te obliga a que se cumpla.

Fórmulas Clave

El Principio de las Casillas Básico Si distribuyes $n+1$ objetos (pichones) en $n$ cajas (casillas), entonces al menos una caja contiene al menos dos objetos. $$ \exists \text{ caja } i \text{ tal que } |caja_i| \ge 2 $$

El Principio de las Casillas Generalizado Si pones $N$ objetos en $k$ cajas, entonces existe al menos una caja que 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 \text{ caja } i \text{ tal que } |caja_i| \ge \left\lceil \frac{N}{k} \right\rceil $$

Formulación Alternativa (Kn + 1) Una variación común que sirve mucho para problemas del AMC: si distribuyes $kn + 1$ objetos en $n$ cajas, entonces al menos una caja contiene al menos $k + 1$ objetos.

El Principio del Promedio Esta es otra forma de decir el principio generalizado que se usa mucho en pruebas de existencia con sumas: dado un conjunto de números, existe al menos un número que es mayor o igual al promedio del conjunto, y al menos un número que es menor o igual al promedio. $$ \exists x \in S \text{ tal que } x \ge \frac{\sum_{s \in S} s}{|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.

1. Sean $x_1, x_2, \dots, x_k$ la cantidad de objetos en la caja 1, caja 2, ..., caja $k$ respectivamente.
2. Sabes que el número total de objetos es la suma de los objetos en las cajas: $$ \sum_{i=1}^{k} x_i = N $$
3. Supón, para llegar a una contradicción, que el teorema es falso. Esto significa que cada caja contiene menos de $\lceil N/k \rceil$ objetos.
4. Matemáticamente, esta suposición implica que: $$ x_i < \frac{N}{k} \quad \text{para todo } i = 1, \dots, k $$ (Nota: Como $x_i$ es un entero, $x_i < \lceil N/k \rceil$ implica que $x_i < N/k$ no es estrictamente necesario, pero $x_i \le \lceil N/k \rceil - 1$ es el límite entero preciso. Sin embargo, la desigualdad estricta $x_i < N/k$ es suficiente para la contradicción si manejas el promedio directamente, o puedes decir que el valor máximo posible para $x_i$ es estrictamente menor que el promedio necesario para que la suma sea $N$).
5. Si sumas la cantidad de objetos en todas las cajas basándote en esta suposición: $$ \sum_{i=1}^{k} x_i < \sum_{i=1}^{k} \frac{N}{k} $$
6. Al evaluar el lado derecho de la desigualdad: $$ \sum_{i=1}^{k} \frac{N}{k} = k \cdot \left( \frac{N}{k} \right) = N $$
7. Combinando los pasos 2 y 6, llegas a: $$ N < N $$
8. Esto es una contradicción. Es imposible que el número total de objetos sea estrictamente menor que $N$.
9. Por lo tanto, la suposición inicial tiene que ser falsa. No es posible que todas las cajas tengan menos de $\lceil N/k \rceil$ objetos. Así que existe al menos una caja $j$ tal que $x_j \ge \lceil N/k \rceil$.

$\square$