Configuraciones extremas

La idea detrás de lo extremal

Muchos problemas olímpicos preguntan: ¿cuál es el mayor número de objetos que puede tener cierta propiedad? ¿O el menor? Este tipo de pregunta —encontrar el máximo o mínimo posible— es el núcleo de la combinatoria extremal.

El método tiene dos partes que siempre van juntas. Primero, demuestra una cota: argumenta que el número buscado no puede superar (o ser menor que) cierto valor $M$. Segundo, da una construcción: exhibe un ejemplo concreto que alcanza exactamente $M$. Sin la construcción, solo tienes la mitad de la solución.

Este principio aparece en la ONEM regional bajo frases como "encuentra el mayor número de…", "¿cuántos como máximo…?", o "demuestra que siempre existe al menos uno que…".

Ejemplo fundamental: subconjuntos sin dos elementos sumando $n+1$

Sea $n$ un entero positivo. Considera el conjunto $\{1, 2, \ldots, 2n\}$. ¿Cuántos elementos puede tener a lo sumo un subconjunto $S$ tal que ningún par de elementos de $S$ sume $n+1$?

Observa que los pares $\{k, n+1-k\}$ para $k = 1, 2, \ldots, n$ particionan el conjunto: $\{1, n\}, \{2, n-1\}, \ldots, \{\lfloor n/2 \rfloor, \lceil n/2 \rceil + 1\}$... en realidad los pares que suman $n+1$ son $\{1,n\}, \{2,n-1\}, \ldots$.

Más precisamente: los pares complementarios respecto a la suma $n+1$ son $\{1, n\}, \{2, n-1\}, \ldots, \{\lfloor n/2 \rfloor, n+1-\lfloor n/2 \rfloor\}$. Hay $\lfloor n/2 \rfloor$ tales pares. El conjunto $\{n+1, n+2, \ldots, 2n\}$ no contiene ningún par complementario (sus elementos suman al menos $2n+2 > n+1$), y tiene exactamente $n$ elementos.

En cambio, de cada par $\{k, n+1-k\}$ con $1 \le k < n+1-k$ podemos tomar a lo sumo uno. Hay exactamente $\lfloor n/2 \rfloor$ tales pares, más el elemento $n+1$ si $n$ es par (el elemento central). Esto da la cota $n$. La construcción $S = \{n+1, n+2, \ldots, 2n\}$ la alcanza.

El método del elemento extremo

Una técnica clásica es mirar el elemento más grande (o más pequeño) en una configuración e imponer condiciones sobre él. Esto a menudo crea una recurrencia o reduce el problema a un caso más pequeño.

Ejemplo: en un conjunto de $n$ números enteros distintos tomados de $\{1, 2, \ldots, 2n-1\}$, demuestra que siempre hay dos cuya diferencia es exactamente $n-1$.

Sea $S \subseteq \{1, \ldots, 2n-1\}$ con $|S| = n$. Considera los $n-1$ pares $\{k, k+n-1\}$ para $k = 1, \ldots, n-1$, más el elemento $n$. Si $n \in S$, observa los pares. Los $n$ elementos de $S$ deben caer en estos $n$ "ranuras". Por el principio del palomar, algún par es ocupado por dos elementos de $S$, dando diferencia $n-1$.

Este ejemplo muestra cómo lo extremal y el palomar se combinan: identificar las ranuras correctas es el arte.

Antichain: el teorema de Dilworth en miniatura

Sea $\mathcal{F}$ una familia de subconjuntos de $\{1, 2, \ldots, n\}$ tal que ningún miembro de $\mathcal{F}$ está contenido en otro. Tal familia se llama una anticadena. La pregunta extremal es: ¿cuál es el mayor tamaño posible de $\mathcal{F}$?

La respuesta —el Teorema de Sperner, 1928— es $\binom{n}{\lfloor n/2 \rfloor}$: la familia más grande es simplemente la colección de todos los subconjuntos de tamaño $\lfloor n/2 \rfloor$. La prueba elemental usa el hecho de que todo subconjunto de tamaño $k$ pertenece a exactamente $k!(n-k)!$ permutaciones de $\{1,\ldots,n\}$; contar permutaciones que "pasan" por la anticadena da la cota.

Para la ONEM regional basta conocer el enunciado y la construcción: tomar todos los subconjuntos de un tamaño fijo da la anticadena máxima.

Estrategia para resolver problemas extremales

Paso 1: Explorar casos pequeños. Calcula la respuesta para $n = 1, 2, 3, 4$ a mano. Esto da intuición sobre el patrón y a menudo sugiere la construcción óptima.

Paso 2: Conjeturar el extremo. Con los casos pequeños, adivina el valor general $f(n)$.

Paso 3: Probar la cota superior. Argumenta que ninguna configuración puede superar $f(n)$. Usa herramientas como el principio del palomar, particiones en pares, o doble conteo.

Paso 4: Dar la construcción. Exhibe explícitamente una configuración que alcanza $f(n)$. Sin esto la solución está incompleta.

Paso 5: Revisar la construcción. Verifica que la construcción realmente satisface todas las condiciones del problema.