Estrategia para problemas combinatorios difíciles

El ciclo de ataque a un problema difícil

Un problema combinatorio de nivel IbAm P3–P6 raramente se resuelve con la primera idea. El proceso estándar es iterativo: explorar, formular conjeturas, refinar, y finalmente demostrar.

Fase 1 — Exploración (5–10 min): Resolver casos pequeños ($n = 2, 3, 4$) a mano. Identificar el patrón. Formular una conjetura precisa sobre el resultado. No escribir la demostración todavía.

Fase 2 — Reducción (5 min): ¿Se puede reducir el problema a algo conocido? ¿Hay un grafo bipartito oculto? ¿Las condiciones son las de Hall? ¿La pregunta es equivalente a una cobertura mínima (König)? Reformular el problema en términos de herramientas del arsenal.

Fase 3 — Intento de demostración (15–20 min): Aplicar la herramienta identificada. Si la demostración se traba, buscar invariantes, cambiar la formulación, o probar con la herramienta alternativa de la lista.

Fase 4 — Verificación (5 min): Revisar cada paso. Verificar que la demostración cubre todos los casos (incluido $n$ par/impar, el caso base, las intersecciones vacías en el PIE). Asegurarse de que no hay circularidad.

Gestión del tiempo en competencia: Si después de 20 minutos no hay progreso, escribir los avances parciales (a veces valen puntos), pasar al siguiente problema, y volver al problema difícil con "ojos frescos".

Combinando Hall y König: la dualidad completa

Hall responde "¿existe?"; König responde "¿cuánto?". En problemas de nivel P3–P4, la solución frecuentemente requiere ambos: primero Hall garantiza que algo existe, luego König cuantifica cuánto.

Patrón combinado 1: "Demuestra que el número mínimo de... es exactamente $k$." Estrategia: (a) construir una configuración con $k$ elementos (upper bound), (b) demostrar que no basta con $k-1$ elementos (lower bound via König: la cobertura mínima = matching máximo = $k$).

Patrón combinado 2: "Demuestra que existe una selección de $k$ elementos tal que...". Estrategia: construir el grafo bipartito apropiado, verificar la condición de Hall para el matching de tamaño $k$ (no necesariamente perfecto, usar el defecto de Hall: matching máximo $= |X| - \max_S(|S| - |N(S)|) \geq k$).

Patrón combinado 3: "Prueba que se puede descomponer el conjunto en... de modo que..." Estrategia: coloración de aristas (descomposición en matchings perfectos via Hall para grafos $k$-regulares). Luego König garantiza que el índice cromático es mínimo.

Ejemplo: Demuestra que en cualquier torneo round-robin de $2n$ equipos, los $\binom{2n}{2}$ partidos pueden organizarse en $2n-1$ rondas con $n$ partidos cada una. Demostración: $K_{2n}$ es $(2n-1)$-regular. Por Hall para grafos regulares, tiene un matching perfecto $M_1$. El grafo restante $K_{2n} \setminus M_1$ es $(2n-2)$-regular. Por inducción (Hall repetido), obtenemos $2n-1$ matchings perfectos de tamaño $n$ que particionan todas las aristas. $\square$

Combinando PIE con coloración y grafos

Los problemas más ricos de la IbAm combinan PIE con coloración de grafos o con teoría de matchings. Los patrones más frecuentes:

PIE + coloración: Contar coloraciones propias de un grafo que además satisfacen alguna condición de exclusión. Primero calcula el polinomio cromático $P(G, k)$ (usando la fórmula de expansión por aristas o la recurrencia de contracción-eliminación). Luego aplica el PIE sobre los colores prohibidos para obtener el número de coloraciones con las condiciones adicionales.

PIE + matching: Contar el número de matchings perfectos de un grafo bipartito que evitan ciertos pares. Esto es el permanente de una matriz 0-1 con restricciones, y se calcula con el PIE sobre las posiciones prohibidas: $\sum_{S \subseteq E_{\text{prob}}} (-1)^{|S|} \cdot (\text{matchings perfectos que incluyen todos de } S)$.

Ejemplo combinado: En un tablero $n \times n$, ¿cuántas maneras hay de colocar $n$ torres no atacantes (sin dos en la misma fila ni columna) tal que ninguna torre esté en la diagonal principal? Esto es el número de derangements de permutaciones de $\{1,\ldots,n\}$: $D_n$ (las torres sin diagonal principal son exactamente las permutaciones sin puntos fijos). Pero si el tablero tiene más restricciones (por ejemplo, las celdas $(i,j)$ con $i+j$ par están bloqueadas), se usa el polinomio de la torre.

Técnica de reducción al caso simétrico: Cuando el PIE involucra condiciones no simétricas, buscar una transformación (reindexar, reflejar, rotar) que las haga simétricas. En el caso simétrico, las intersecciones $|A_S|$ solo dependen de $|S|$ y el PIE se simplifica enormemente.

Advertencia: Al combinar herramientas, es fácil cometer el error de "sobrecontar" o "infracontar". Verificar siempre el caso base y un caso concreto ($n=3$ o $n=4$) para confirmar que la fórmula da el resultado correcto.

El invariante como complemento de Hall/König

Los problemas más difíciles de la IbAm combinan matchings/Hall con invariantes. El patrón es: una secuencia de operaciones que modifica un grafo, y la pregunta es si se puede llegar a un estado específico (un matching perfecto, una coloración, etc.).

Patrón: "Se tiene un grafo $G$ y se pueden realizar operaciones de tipo X. ¿Cuántas operaciones son necesarias para obtener un matching perfecto?" Estrategia: (a) mostrar que el matching máximo aumenta en a lo sumo 1 por operación (invariante monovariante), (b) calcular la distancia entre el matching actual y el perfecto usando el defecto de Hall.

Invariantes en tableros con matchings: En problemas donde un tablero se transforma (celdas se marcan o desmarcan) y se pregunta si siempre existe un cubrimiento, el invariante es la paridad del número de celdas de cada color (coloración de ajedrez). Si en algún momento hay más celdas negras que blancas (o viceversa), ningún cubrimiento con dominós es posible (Hall falla: la condición $|N(S)| \geq |S|$ falla para $S$ = celdas del color mayoría).

La conexión entre invariantes y la condición de Hall: La condición de Hall $|N(S)| \geq |S|$ para todo $S$ es en sí misma un conjunto de invariantes locales del grafo bipartito. Si una operación puede violar la condición de Hall para algún $S$, el invariante adecuado es $\min_{S \subseteq X}(|N(S)| - |S|)$ (el "slack" de Hall). Si este slack se mantiene no negativo durante todas las operaciones, existe siempre un matching perfecto.

Ejemplo de nivel P5 (estilo IbAm): En un grafo bipartito $G$, en cada paso se puede añadir o eliminar una arista. Demuestra que si $G$ siempre tiene grado mínimo $\geq 1$, el matching máximo no puede disminuir en más de 1 en un solo paso. Demostración: Al eliminar la arista $xy$, el matching $M$ que usaba $xy$ pierde esa arista, dando un matching de tamaño $|M|-1$. Pero como $x$ todavía tiene grado $\geq 1$ en $G \setminus \{xy\}$, existe $xy'$ en el grafo residual, y el matching aumentante de longitud 1 vía $x - y' - \ldots$ restaura el matching. El defecto de Hall aumenta en a lo sumo 1. $\square$

Los errores más comunes en problemas de combinatoria difícil

Aprender de los errores frecuentes es tan importante como aprender las técnicas correctas. Los errores más comunes en combinatoria difícil de nivel IbAm:

**Error 1 — No verificar la condición de Hall para todos los subconjuntos $S$:** Es tentador verificar solo los $S$ "pequeños" o "grandes", pero la condición de Hall puede fallar para subconjuntos de tamaño intermedio. Siempre es necesario argumentar para "todo $S \subseteq X$" de manera general.

Error 2 — Confundir necesidad y suficiencia en Hall: Hall dice: matching perfecto $\iff$ condición de Hall. Demostrar que la condición de Hall se cumple es suficiente para mostrar que existe un matching perfecto. Pero si se quiere demostrar que NO existe matching perfecto, hay que exhibir un $S$ que viole la condición.

Error 3 — Sobrecontar en el PIE por intersecciones no vacías: Cuando las condiciones $A_i$ no son mutuamente exclusivas respecto a las intersecciones, hay que calcular $|A_S|$ para cada $S$, no solo los pairwise. Un error clásico es asumir que $|A_i \cap A_j| = 0$ sin justificación.

Error 4 — Olvidar el caso base en la inducción sobre el teorema de Hall: Al usar Hall por inducción (caso Clase 1 vs. Clase 2 en la demostración de Hall), el caso donde la condición de Hall es "justa" ($|N(S)| = |S|$ para algún $S$ propio) requiere un argumento más cuidadoso.

Error 5 — Usar König cuando el grafo no es bipartito: König es válido solo para grafos bipartitos. Para grafos generales, la igualdad $\nu(G) = \tau(G)$ puede no ser válida (el triángulo $K_3$ tiene $\nu = 1$, $\tau = 2$).

Estrategia de revisión: Antes de cerrar una demostración, revisar: (a) ¿la herramienta aplica? (grafo bipartito para Hall/König, condiciones simétricas para PIE simétrico, etc.); (b) ¿se cubrieron todos los casos?; (c) ¿el argumento es circular?; (d) ¿se verificó con un ejemplo pequeño?

Problema trabajado: un P3 de la IbAm con múltiples herramientas

Problema (IbAm 2020, estilo P3): Sea $n \geq 3$ un entero. Hay $n$ jugadores $P_1, \ldots, P_n$ y $n$ premios $R_1, \ldots, R_n$. Cada jugador $P_i$ quiere exactamente uno de $k$ premios específicos (la lista $L_i \subseteq \{R_1,\ldots,R_n\}$ con $|L_i| = k$). Cada premio es deseado por exactamente $k$ jugadores. Demuestra que: (a) es posible dar a cada jugador un premio de su lista sin repetir premios; (b) la mínima $k$ para la cual esto es posible sin importar cuáles sean las listas es $k = 1$ (trivialmente) y para $k \geq 2$ siempre es posible.

Análisis: La condición "cada jugador desea exactamente $k$ premios y cada premio es deseado por exactamente $k$ jugadores" define un grafo bipartito $k$-regular $G = (\{P_i\} \cup \{R_j\}, E)$. La asignación pedida es un matching perfecto.

Demostración parte (a): Por el corolario del teorema de Hall para grafos bipartitos $k$-regulares ($k \geq 1$), $G$ tiene un matching perfecto. Este matching es la asignación pedida. $\square$

Demostración parte (b): Para $k = 1$, el grafo es 1-regular (cada jugador desea un solo premio y cada premio es deseado por uno), que es directamente un matching perfecto. Para $k \geq 2$, la regularidad garantiza que la condición de Hall siempre se cumple: para cualquier $S \subseteq \{P_1,\ldots,P_n\}$, el doble conteo da $k|S| \leq k|N(S)|$, es decir $|N(S)| \geq |S|$. Esto es independiente de cuáles sean las listas específicas (siempre que la hipótesis de regularidad se mantenga). $\square$

Reflexión metodológica: El problema tiene dos partes. La parte (a) es Hall aplicado al caso regular (un corolario directo). La parte (b) es una observación sobre la robustez del resultado: la regularidad es la condición suficiente, sin importar la estructura específica de las listas. Este tipo de problema "a dos partes" es característico del P2–P3 de la IbAm: la primera parte es más accesible, la segunda requiere más abstracción.