Lección 1.4: Complemento y doble conteo — Espinoza Olimpiadas

Contar por complemento: lo que es más fácil evitar

A veces contar directamente lo que queremos es difícil, pero contar lo que no queremos es sencillo. El principio de complemento dice: si el universo tiene $N$ objetos y queremos contar los que satisfacen una propiedad $P$ , podemos en cambio contar los que no satisfacen $P$ y restar.

Formalmente: $|P| = N - |\overline{P}|$ , donde $\overline{P}$ denota el conjunto de objetos que no tienen la propiedad $P$ . La clave es encontrar un universo $N$ que sea fácil de calcular y un complemento $\overline{P}$ que también sea fácil.

Ejemplo: ¿cuántas cadenas de 5 bits tienen al menos dos ceros? El complemento es "ningún cero o exactamente un cero". Cadenas sin ceros: $1$ . Cadenas con exactamente un cero: hay $\binom{5}{1} = 5$ posiciones donde puede estar el cero. Total complemento: $1 + 5 = 6$ . Total universo: $2^5 = 32$ . Respuesta: $32 - 6 = 26$ .

|P| = N - |\overline{P}|

El complemento en acción: problemas típicos ONEM

Contraseñas con restricción: ¿Cuántas contraseñas de 4 dígitos (del 0 al 9, con repetición) tienen al menos un dígito repetido? Total de contraseñas: $10^4 = 10\,000$ . Complemento (todas distintas): $10 \times 9 \times 8 \times 7 = 5\,040$ . Respuesta: $10\,000 - 5\,040 = 4\,960$ .

Rutas con obstáculo: Supón que quieres contar rutas de una cuadrícula que evitan cierto punto. A menudo es más fácil contar todas las rutas y restar las que pasan por ese punto. Esta técnica aparece frecuentemente en olimpiadas de nivel 2.

Cuándo usar complemento: Usa complemento cuando la condición del problema es "al menos uno", "al menos dos", "algún...", o equivalentemente cuando el enunciado incluye la palabra "al menos". Estas formulaciones suelen tener complementos sencillos del tipo "ninguno" o "a lo más $k-1$ ".

El doble conteo: la misma cantidad, dos perspectivas

El doble conteo es una de las técnicas más elegantes de la combinatoria. La idea es contar el mismo conjunto de dos maneras distintas y obtener una igualdad útil. Si contamos correctamente los elementos de un conjunto $S$ desde la perspectiva de los objetos $A$ y obtenemos $X$ , y desde la perspectiva de los objetos $B$ obtenemos $Y$ , entonces $X = Y$ .

El ejemplo más clásico: considera todos los pares (estudiante, club) donde el estudiante es miembro del club. Si contamos por estudiantes: cada estudiante $i$ aporta $d_i$ pares (donde $d_i$ es el número de clubes al que pertenece), y la suma total es $\sum_i d_i$ . Si contamos por clubes: cada club $j$ aporta $|C_j|$ pares (donde $|C_j|$ es su tamaño), y la suma es $\sum_j |C_j|$ . Por tanto $\sum_i d_i = \sum_j |C_j|$ .

Esta igualdad no es trivial a primera vista, pero se demuestra instantáneamente con doble conteo. Esta es la potencia del método: convierte identidades aparentemente difíciles en observaciones inmediatas.

El lema del apretón de manos

El lema del apretón de manos (handshaking lemma) es el doble conteo más famoso. En una reunión de $n$ personas donde algunas se saludan (cada par se saluda a lo más una vez), la suma de los saludos recibidos por cada persona es igual al doble del número de saludos totales.

Formalmente: si $d_i$ es el número de saludos que recibe la persona $i$ , y $m$ es el número total de saludos, entonces $\sum_{i=1}^{n} d_i = 2m$ .

La prueba es doble conteo: contamos los pares (persona, saludo en el que participa). Por personas: cada persona $i$ aporta $d_i$ pares, total $\sum d_i$ . Por saludos: cada saludo involucra a exactamente 2 personas, así que aporta 2 pares, total $2m$ . Igualando: $\sum d_i = 2m$ . Una consecuencia inmediata: el número de personas con un número impar de saludos es siempre par (porque la suma $\sum d_i$ es par).

\sum_{i=1}^{n} d_i = 2m

Doble conteo en problemas de competencia

Problema tipo ONEM: En un torneo de 8 jugadores (todos contra todos, sin empates), demuestra que el número de victorias total es igual al número de derrotas total. Solución por doble conteo: cada partido produce exactamente 1 victoria y 1 derrota. Si hay $m$ partidos, el total de victorias es $m$ y el total de derrotas es $m$ . Son iguales. (También: $m = \binom{8}{2} = 28$ partidos, con 28 victorias y 28 derrotas en total.)

Identidad combinatoria por doble conteo: Demuestra que $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ . Doble conteo de subconjuntos de un conjunto de $n$ elementos. Por la derecha: hay $2^n$ subconjuntos en total. Por la izquierda: agrupamos los subconjuntos por tamaño; los de tamaño $k$ son $\binom{n}{k}$ , y la suma sobre todos los tamaños posibles (de 0 a $n$ ) da el total.

Problema con diagonales: ¿Cuántas diagonales tiene un polígono convexo de $n$ lados? El total de segmentos entre vértices es $\binom{n}{2}$ . De esos, $n$ son lados del polígono. El resto son diagonales: $\binom{n}{2} - n = \frac{n(n-1)}{2} - n = \frac{n(n-3)}{2}$ . El doble conteo (contar todos los segmentos y restar los lados) da la fórmula directamente.

Cuándo elegir cada técnica

Las cuatro técnicas del capítulo 1 (paloma, adición/multiplicación, inclusión-exclusión, complemento/doble conteo) no son competidoras sino complementarias. La clave es reconocer qué estructura tiene el problema.

Usa complemento cuando la condición del problema dice "al menos" o cuando los casos favorables son complicados pero el complemento es simple. Usa doble conteo cuando quieres demostrar una identidad o cuando hay dos maneras naturales de contar la misma colección de objetos (especialmente en problemas con grafos o relaciones).

Un buen olímpico domina las cuatro técnicas y, ante un problema nuevo, las prueba mentalmente: ¿puedo aplicar la paloma? ¿los casos son disjuntos (suma) o secuenciales (multiplicación)? ¿hay traslape que requiera PIE? ¿es más fácil contar el complemento? Con práctica, la elección correcta se vuelve instintiva.

Complemento y doble conteo