El método probabilístico

Existencia sin construcción explícita

A veces necesitamos demostrar que existe un objeto con cierta propiedad, pero construirlo explícitamente es difícil. El método probabilístico ofrece una alternativa elegante: si eliges el objeto al azar y la probabilidad de que tenga la propiedad deseada es mayor que cero, entonces ese objeto debe existir.

La lógica es tan simple como poderosa: si $\Pr[A] > 0$ para algún evento $A$, entonces $A$ ocurre en al menos un resultado posible. Ese resultado es el objeto que buscamos.

Este método fue desarrollado por Paul Erdős en la década de 1940 y revolucionó la combinatoria. A nivel regional, sus aplicaciones más simples son completamente accesibles.

Primer ejemplo: 2-coloración de aristas sin triángulo monocromático

Colorea al azar las aristas de $K_n$ con dos colores (rojo y azul), cada arista de forma independiente con probabilidad $1/2$ para cada color. ¿Cuándo podemos garantizar que existe una 2-coloración sin triángulo monocromático?

Para un triángulo fijo $\{i,j,k\}$, la probabilidad de que sea monocromático (todo rojo o todo azul) es $2 \cdot (1/2)^3 = 1/4$.

Hay $\binom{n}{3}$ triángulos. Por linealidad de la esperanza, el número esperado de triángulos monocromáticos es $\binom{n}{3} \cdot \frac{1}{4}$.

Si este valor es menor que 1, es posible que no haya triángulos monocromáticos (porque si la esperanza es $< 1$, algún resultado tiene 0 triángulos). La condición $\binom{n}{3}/4 < 1$ equivale a $n(n-1)(n-2) < 24$, que se cumple para $n \le 4$. Luego, existe una 2-coloración de $K_4$ sin triángulo monocromático.

La desigualdad de Markov como herramienta

Sea $X$ una variable aleatoria no negativa. La desigualdad de Markov afirma que $\Pr[X \ge 1] \le \mathbb{E}[X]$.

Consecuencia clave: si $\mathbb{E}[X] < 1$, entonces $\Pr[X \ge 1] < 1$, lo que implica $\Pr[X = 0] > 0$. Es decir, **es posible que $X = 0$**, así que existe un resultado donde $X = 0$.

En el contexto extremal: si $X$ cuenta el número de "objetos malos" (triángulos monocromáticos, pares conflictivos, etc.) y $\mathbb{E}[X] < 1$, entonces existe una configuración sin ningún objeto malo.

Esta es la versión más elemental del método probabilístico y es la que aparece en problemas regionales. Para niveles superiores se usan versiones más refinadas (Lovász Local Lemma, segundo momento), pero aquí basta con Markov.

Ejemplo: partición de un grafo en dos partes con muchas aristas cruzadas

Sea $G$ un grafo con $m$ aristas. Demuestra que existe una partición de los vértices en dos conjuntos $A$ y $B$ tal que al menos $m/2$ aristas van de $A$ a $B$.

Coloca cada vértice en $A$ o $B$ de forma independiente y uniforme (probabilidad $1/2$ cada uno). Para una arista $\{u,v\}$, la probabilidad de que cruce la partición (un extremo en $A$, el otro en $B$) es $\Pr[u \in A, v \in B] + \Pr[u \in B, v \in A] = 1/4 + 1/4 = 1/2$.

El número esperado de aristas cruzadas es $m \cdot 1/2 = m/2$. Como la esperanza es $m/2$, debe existir al menos una partición que alcanza o supera $m/2$ aristas cruzadas.

Nótese que esto da una prueba de existencia pero no dice cómo encontrar la partición. Sin embargo, para la olimpiada, existencia es suficiente.

Cómo reconocer cuándo usar el método probabilístico

El método probabilístico es especialmente útil cuando: (a) el problema pide demostrar existencia de un objeto con varias condiciones simultáneas, (b) la construcción directa parece imposible por el tamaño del espacio de búsqueda, o (c) la condición deseada puede expresarse como "cero objetos malos".

La receta es: (1) define un espacio de probabilidad natural (aleatorizar la estructura), (2) define $X$ = número de "objetos malos", (3) calcula $\mathbb{E}[X]$ por linealidad de la esperanza, (4) si $\mathbb{E}[X] < 1$, concluye existencia.

En la ONEM regional el método aparece principalmente en problemas de coloración y partición. El paso más importante es elegir el espacio de probabilidad correcto; generalmente es la distribución uniforme sobre alguna estructura simétrica.