Principio de inclusión-exclusión

El problema del traslape

En un grupo de 30 estudiantes, 18 juegan fútbol y 15 juegan básquetbol. Si simplemente sumamos $18 + 15 = 33$, obtenemos un número mayor que el tamaño del grupo. ¿Qué salió mal?

El problema es que algunos estudiantes juegan ambos deportes. Los estamos contando dos veces: una como futbolistas y otra como basquetbolistas. Para corregir el error, necesitamos restar los que están en ambos grupos.

Si 7 estudiantes juegan ambos deportes, el número que juega fútbol o básquetbol (o ambos) es $18 + 15 - 7 = 26$. Este razonamiento es el núcleo del principio de inclusión-exclusión (PIE).

La fórmula para dos conjuntos

Para dos conjuntos $A$ y $B$ dentro de un universo finito, la fórmula es:

$$|A \cup B| = |A| + |B| - |A \cap B|$$

La justificación es directa: cuando sumamos $|A| + |B|$, los elementos que están en $A \cap B$ se cuentan exactamente dos veces (una por $|A|$ y otra por $|B|$). Al restar $|A \cap B|$ una vez, cada elemento de $A \cup B$ queda contado exactamente una vez.

Esta fórmula es tan útil que la usarás en casi todos los problemas que mezclan dos condiciones. Aprenderla de memoria te ahorrará mucho tiempo en competencia.

La fórmula para tres conjuntos

Para tres conjuntos $A$, $B$, $C$, la fórmula se extiende a:

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

La intuición detrás de los signos: sumamos los individuales, pero hemos sobrecontado las intersecciones de dos conjuntos (cada elemento en dos conjuntos fue sumado dos veces, así que lo restamos). Pero al restar las intersecciones de pares, hemos subcontado los elementos que están en los tres conjuntos simultáneamente (los restamos tres veces pero los sumamos tres veces, quedando en cero), así que hay que volver a sumarlos.

El patrón de signos es $+, -, +$: suma los individuales, resta las intersecciones de pares, suma las intersecciones triples. Para cuatro conjuntos continuaría: resta las de cuádruples, etc. Alternamos signos.

El patrón general y problemas con divisores

Para $n$ conjuntos $A_1, A_2, \ldots, A_n$, el principio de inclusión-exclusión establece que $|A_1 \cup \cdots \cup A_n|$ es igual a la suma de los tamaños individuales, menos la suma de las intersecciones de todos los pares posibles, más la suma de las intersecciones de todos los triples posibles, y así sucesivamente, alternando signos hasta la intersección de los $n$ conjuntos.

Problema con divisores (nivel ONEM): ¿Cuántos enteros del 1 al 100 son divisibles por 2 o por 3? Sea $A$ = múltiplos de 2, $B$ = múltiplos de 3. Entonces $|A| = \lfloor 100/2 \rfloor = 50$, $|B| = \lfloor 100/3 \rfloor = 33$, $|A \cap B|$ = múltiplos de $\text{mcm}(2,3) = 6$: $|A \cap B| = \lfloor 100/6 \rfloor = 16$. Respuesta: $50 + 33 - 16 = 67$.

Problema con tres divisores: ¿Cuántos enteros del 1 al 120 son divisibles por 2, 3 o 5? $|A_2| = 60$, $|A_3| = 40$, $|A_5| = 24$. Intersecciones: $|A_6| = 20$, $|A_{10}| = 12$, $|A_{15}| = 8$. Triple: $|A_{30}| = 4$. Total $= 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88$.

Problemas con letras y palabras

¿Cuántas palabras de 4 letras (del abecedario de 26) tienen al menos una letra A o al menos una letra B? Es más fácil por complemento, pero ilustremos con PIE: sea $A$ = palabras con al menos una A, $B$ = palabras con al menos una B. La fórmula directa requiere contar por complemento dentro del PIE.

Contemos por complemento de la unión: palabras sin ninguna A ni ninguna B son palabras sobre las $24$ letras restantes: $24^4 = 331\,776$. El total de palabras de 4 letras es $26^4 = 456\,976$. Palabras con al menos una A o al menos una B: $456\,976 - 331\,776 = 125\,200$.

Problema tipo ONEM: En una clase de 40 alumnos, 25 estudian Matemáticas, 20 estudian Física, 18 estudian Química, 12 estudian Matemáticas y Física, 10 estudian Matemáticas y Química, 9 estudian Física y Química, y 5 estudian las tres materias. ¿Cuántos alumnos no estudian ninguna de las tres materias? Total estudiando al menos una: $25+20+18-12-10-9+5 = 37$. Los que no estudian ninguna: $40 - 37 = 3$ alumnos.

Conexión con la fórmula de complemento

Una aplicación poderosa del PIE es calcular el complemento de una unión: los elementos que no están en ninguno de los conjuntos $A_1, \ldots, A_n$. Si el universo tiene tamaño $N$, entonces:

$$|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}| = N - |A_1 \cup \cdots \cup A_n|$$

Esta combinación (PIE + complemento) aparece con mucha frecuencia en problemas de la ONEM. La estrategia típica es: (1) identificar las "propiedades malas" que no queremos, (2) aplicar PIE para contar los elementos con al menos una propiedad mala, (3) restar del total. En la lección 1.4 profundizaremos en el principio de complemento como técnica propia.