Estrategia de competencia

Los cinco tipos de problema combinatorio en ONEM

En la ONEM regional, los problemas de combinatoria suelen clasificarse en cinco tipos:

(1) Conteo directo: usa los principios multiplicativo y aditivo, permutaciones y combinaciones. Primer movimiento: ¿el orden importa? ¿hay repetición?

(2) Inclusión-exclusión: cuando hay condiciones negativas ("al menos uno", "ninguno de los tres"). Primer movimiento: aplica PIE al conjunto de elementos "malos".

(3) Principio de las casillas: cuando el problema pide demostrar la existencia de dos elementos con cierta propiedad. Primer movimiento: identifica las "casillas" (residuos, intervalos, colores).

(4) Recursión y recurrencia: cuando el problema tiene estructura interna que permite reducir a tamaños menores. Primer movimiento: ¿qué pasa con la última pieza, persona o casilla?

(5) Coloración o paridad: cuando la condición involucra una invariante (paridad de un número, colores de un tablero). Primer movimiento: asigna paridades o colorea y observa la invariante.

Errores frecuentes en combinatoria olímpica

Error 1: Contar objetos distinguibles como indistinguibles (o viceversa). Siempre verifica: ¿las personas tienen nombres? ¿Los objetos tienen etiquetas? En caso afirmativo, son distinguibles y el orden (o la identidad) importa.

Error 2: Olvidar el caso vacío. En problemas de subconjuntos o selecciones, el conjunto vacío a veces se incluye y a veces no, según el enunciado. Lee con cuidado.

Error 3: Aplicar el PIE incorrectamente. Los signos del PIE alternan: $+$ para intersecciones impares, $-$ para intersecciones pares. Verifica con un ejemplo de $|A \cup B| = |A|+|B|-|A\cap B|$ antes de generalizar.

Error 4: Confundir permutaciones y combinaciones. $P(n,k) = n!/(n-k)!$ (importa el orden); $\binom{n}{k} = n!/(k!(n-k)!)$ (no importa el orden). Si el problema dice "seleccionar un equipo" es combinación; si dice "asignar roles distintos" es permutación.

Error 5: No verificar los casos base en inducción o recurrencia. Una recurrencia incorrecta puede dar la respuesta correcta en $n = 3, 4, 5$ y fallar en $n = 1$ o $n = 2$.

Distribución del tiempo y estrategia de examen

En un examen ONEM regional con cuatro problemas de combinatoria en 60 minutos: los primeros dos problemas suelen ser de nivel 1 y resolverse en 5-8 minutos cada uno. Los últimos dos son de nivel 2-3 y requieren 15-20 minutos.

Si en 5 minutos no identificas el tipo del problema, considera si hay una simetría o invariante oculta. En combinatoria, las invariantes (paridades, colores, residuos) suelen ser la clave para los problemas del tercer y cuarto puesto.

Cuando resuelvas un problema de conteo, siempre verifica con un caso pequeño: si tu fórmula da $a_3$, calcula $a_3$ manualmente (listando todas las posibilidades) y confirma que coincide. Este paso toma 1-2 minutos y evita errores que cuestan todo el puntaje.

En competencias con puntaje parcial: una solución que lista correctamente los primeros $5$ casos y conjetura la fórmula, aunque sin demostración, recibe más puntos que no entregar nada. Entrega todo.

El arte del doble conteo

El doble conteo (contar el mismo conjunto de dos maneras distintas) es la técnica más elegante y frecuente en combinatoria olímpica. La clave es:

(1) Identifica el conjunto que quieres contar (llámalo $S$).

(2) Cuenta $|S|$ de una primera manera (obtienes una expresión $E_1$).

(3) Cuenta $|S|$ de una segunda manera (obtienes $E_2$).

(4) Concluye $E_1 = E_2$.

Ejemplo: en un grafo con $n$ vértices y $m$ aristas donde cada vértice tiene grado $d_i$, el doble conteo de los extremos de las aristas da $\sum_{i=1}^n d_i = 2m$ (handshaking lemma).

Otro ejemplo: en un torneo round-robin con $n$ equipos, el doble conteo de los puntos (1 punto al ganador, 0 al perdedor) da que la suma total de puntos es $\binom{n}{2}$.

Practica el doble conteo identificando en cada problema qué conjunto de "pares" o "incidencias" puede contarse de dos maneras distintas.