10.2: Inclusión-Exclusión

Última actualización
Guardar como PDF

Page ID: 114501

Joy Morris
University of Lethbridge

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

En la escuela, probablemente viste diagramas de Venn a veces, mostrando grupos que se superponían entre sí. Podríamos dibujar un diagrama de Venn muy básico que muestre los tipos de árboles que están creciendo en las diversas casas de mi calle:

$clipboard_e61c8492992aee3ab2cbb51126db6b62d.png$

Mirar el diagrama de Venn puede ayudarnos a averiguar los valores de algunas de las piezas a partir de conocer los valores de otras. Supongamos que sabemos cuántas casas tienen árboles caducifolios, y cuántas casas tienen árboles de hoja perenne. Ingenuamente, se podría pensar que sumar estos juntos nos daría el número total de casas con árboles. No obstante, al observar el diagrama de Venn, vemos que si simplemente sumamos los valores juntos, entonces cualquier casa que tenga ambos tipos de árboles se ha contado dos veces (una vez como una casa con un árbol caducifolio, y nuevamente como una casa con un árbol siempreverde). Entonces, para calcular el número de casas que tienen árboles, podemos sumar el número que tienen árboles caducifolios al número que tienen árboles de hoja perenne y luego restar el número que tienen ambos tipos de árboles. Esta es la idea de “inclusión-exclusión”.

Específicamente, si dos conjuntos$A$ y$B$ son disjuntos, entonces$|A ∪ B| = |A|+|B|$. Sin embargo, si$A$ y no$B$ son disjuntos, entonces$|A| + |B|$ cuenta los elementos de$A ∩ B$ dos veces (tanto como elementos de$A$ y como elementos de$B$). Al restar este exceso se obtiene la respuesta correcta:

Proposición$\PageIndex{1}$: Inclusion-Exclusion For $2$ Sets

Para cualquier conjunto finito$A$ y$B$, tenemos

\[|A ∪ B| = |A| + |B| − |A ∩ B|\]

Prueba

Vamos$A_0 = A \setminus B$ y$B_0 = B \setminus A$, entonces

$A$es la unión disjunta de$A_0$ y$A ∩ B$,
$B$es la unión disjunta de$B_0$ y$A ∩ B$, y
$A ∪ B = (A_0 ∪ (A ∩ B)) ∪ (B_0 ∪ (A ∩ B))$es la unión disjunta de$A_0$,$B_0$, y$A ∩ B$.

Entonces

\[ \begin{equation} \begin{split} |A| + |B| &= (|A_0| + |A ∩ B|) + (|B_0| + |A ∩ B|) \\ &= (|A_0| + |B_0| + |A ∩ B|) + |A ∩ B| \\ &= |A ∪ B| + |A ∩ B| \end{split} \end{equation} \]

Ejemplo$\PageIndex{1}$

Dejar$A = \{p,r, o, n, g\}$ y$B = \{h, o,r, n,s\}$. Entonces,

$|A| = 5$,$|B| = 5$, y$|A ∩ B| = |\{r, o, n\}| = 3$,

por lo que la inclusión-exclusión nos dice que

$|A ∪ B| = |A| + |B| − |A ∩ B| = 5 + 5 − 3 = 7$

Esto es correcto, ya que

$|A ∪ B| = |\{p,r, o, n, g, h,s\}| = 7$.

Ejemplo$\PageIndex{2}$

Cada uno de los$4000$ estudiantes de Modern U posee ya sea una tableta o un reloj inteligente (o ambos). Las encuestas muestran que:

$3500$los estudiantes poseen una tableta, y
$1000$los estudiantes poseen un reloj inteligente.

¿Cuántos alumnos poseen tanto una tableta como un reloj inteligente?

Solución

Let

$S$ser el conjunto de todos los estudiantes de Modern U,
$T$ser el conjunto de alumnos que poseen una tableta, y
$W$ser el conjunto de estudiantes que poseen un reloj inteligente.

Entonces, por suposición,

$|S| = 4000$,$|T| = 3500$,$|W| = 1000$.

Como cada estudiante posee ya sea una tableta o un reloj inteligente, nosotros tenemos$S = T ∪ W$. Por lo tanto, Inclusión-Exclusión nos dice que

$|S| = |T ∪ W| = |T| + |W| − |T ∩ W|$,

por lo

$|T ∩ W| = |T| + |W| − |S| = 3500 + 1000 − 4000 = 500$.

De ahí que haya exactamente$500$ estudiantes que poseen tanto una tableta como un reloj inteligente.

El siguiente ejercicio proporciona una fórmula para la unión de tres conjuntos$A$,$B$, y$C$. La idea es que$A ∩ B$,$A ∩ C$, y todos$B ∩ C$ han sido sobrecontados. No obstante, restando todos estos sobrecompensará, porque los elementos de se$A ∩ B ∩ C$ han restado demasiadas veces, por lo que hay que volver a agregarlos.

Ejercicio$\PageIndex{1}$

Supongamos$A$$B$,, y$C$ son conjuntos finitos. Mostrar

$|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|$.

[Sugerencia: Tenemos fórmulas para$|(A ∪ B) ∪ C|$ y$|A ∪ B|$. La igualdad$(A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)$ proporciona otra fórmula útil.

La siguiente fórmula general calcula la cardinalidad de la unión de cualquier número de conjuntos, sumando o restando la cardinalidad de cada intersección posible de los conjuntos. Se llama fórmula Inclusión-Exclusión, porque funciona sumando (o “incluyendo”) las cardinalidades de ciertos conjuntos, y restando (o “excluyendo”) las cardinalidades de ciertos otros conjuntos.

Teorema$\PageIndex{1}$: Inclusion-Exclusion

Dejar$A_1, . . . , A_n$ que sean conjuntos finitos. Entonces

\[|A_1 ∪ . . . ∪ A_n| = \left( \sum_{i=1}^{n} |A_i| \right) - \left( \sum_{1≤i<j≤n}^{n} |A_i ∩ A_j | \right) + ... + ((−1)^{n+1} |A_1 ∩ . . . ∩ A_n|) \]

Por supuesto, podemos averiguar el valor de cualquiera de los términos en la fórmula de inclusión-exclusión, si conocemos los valores de todos los demás términos

Ejemplo$\PageIndex{3}$

La clase de Sandy es en Calaway Park. Hay$21$ alumnos en la clase. Al final del día, el maestro hace algunas preguntas y determina lo siguiente:

Cada estudiante viajó al menos en una de las montañas rusas, el tren, el viaje de troncos o los autos chocadores;
$13$los estudiantes montaron en la montaña rusa;
$6$los estudiantes viajaron en el tren;
$12$los estudiantes montaron en el paseo de troncos;
$15$estudiantes montaron los autos chocadores;
$2$los estudiantes montaron los cuatro paseos; y
$10$los estudiantes montaron al menos$3$ de estos$4$ paseos.

¿Cuántos estudiantes montaron exactamente dos de los cuatro paseos?

Solución

Comenzamos por establecer alguna notación. $A_1$Sea el conjunto de estudiantes que montaron en la montaña rusa;$A_2$ será el conjunto de estudiantes que viajaron en el tren;$A_3$ será el conjunto de estudiantes que montaron el paseo de troncos; y$A_4$ será el conjunto de estudiantes que montaron los autos chocadores.

Haciendo caso omiso de la última información por un momento, el resto de nosotros nos han dado nos dice que:

$|A_1 ∪ A_2 ∪ A_3 ∪ A_4| = 21$;
$|A_1| = 13$;
$|A_2| = 6$;
$|A_3| = 12$;
$|A_4| = 15$; y
$|A_1 ∩ A_2 ∩ A_3 ∩ A_4| = 2$.

La última información es un poco más complicada de codificar. Observe que si tomamos$|A_1 ∩A_2 ∩A_3|+|A_1 ∩A_2 ∩A_4|+|A_1 ∩A_3 ∩A_4|+|A_2 ∩A_3 ∩A_4|$, usando ideas similares a inclusión-exclusión (o dibujando el diagrama de Venn) vemos que hemos encontrado el número de alumnos que montaron al menos$3$ de los$4$ paseos, excepto que hemos contado el número de alumnos que montaron todos los$4$ paseos en cada uno de los cuatro summands, en lugar de contarlo sólo una vez. Entonces necesitamos$|A_1 ∩ A_2 ∩ A_3 ∩ A_4|$ restar tres veces para obtener el número de estudiantes que montaron al menos$3$ de los$4$ paseos. Ya que sabemos eso$|A_1 ∩ A_2 ∩ A_3 ∩ A_4| = 2$, esto nos dice que

$|A_1 ∩ A_2 ∩ A_3| + |A_1 ∩ A_2 ∩ A_4| + |A_1 ∩ A_3 ∩ A_4| + |A_2 ∩ A_3 ∩ A_4| − 6 = 10$,

por lo

$|A_1 ∩ A_2 ∩ A_3| + |A_1 ∩ A_2 ∩ A_4| + |A_1 ∩ A_3 ∩ A_4| + |A_2 ∩ A_3 ∩ A_4| = 16$.

Así, la fórmula inclusión-exclusión nos dice que

$21 = (13 + 6 + 12 + 15) − \sum_{1≤i<j≤4} | A_i ∩ A_j | + 16 − 2$,

así$\sum_{1≤i<j≤4} |A_i ∩ A_j | = 39$. Desafortunadamente, esto todavía no es exactamente lo que estamos buscando. El valor que queremos es el número de alumnos que montaron exactamente dos de los cuatro paseos. Nuevamente, razonamiento similar muestra que el número de estudiantes que viajaron en la montaña rusa y el tren pero ninguno de los otros dos paseos, estará dado por:

$|A_1 ∩ A_2| − |A_1 ∩ A_2 ∩ A_3| − |A_1 ∩ A_2 ∩ A_4| + |A_1 ∩ A_2 ∩ A_3 ∩ A_4|$.

Se pueden elaborar fórmulas similares para cada uno de los otros cinco pares que se pueden formar a partir de las cuatro atracciones. Lo que se nos ha pedido, es la suma de estas seis fórmulas. Esto funciona para

$ \sum_{1≤i<j≤4} |A_i ∩ A_j | - 3 \left( \sum_{1≤i<j<k≤4} |A_i ∩ A_j ∩ A_k| \right) + 6|A_1 ∩A_2 ∩A_3 ∩A_4| = 39−3(16)+ 6(2) = 3 $.

Sólo tres de los estudiantes montaron exactamente dos de los cuatro paseos.

Este fue un ejemplo muy complicado. No debes esperar tener que elaborar ejemplos que son tan complicados, pero esto te da una idea del poder de la inclusión-exclusión. Aquí hay una aplicación más sencilla.

Ejemplo$\PageIndex{4}$

En la Facultad de Artes y Ciencias, el método de votación utilizado es la “aprobación”; es decir, independientemente del número de puestos disponibles, cada elector puede marcar tantas casillas como desee en su boleta.

Imagínese que el Prof. Li, el Prof. Cheng y el Prof. Osborn fueron todos nominados para dos puestos de informática en el comité de búsqueda del departamento. Barb Hodgson señala los siguientes hechos al contar las boletas:

El Prof. Cheng recibió$18$ votos; el Prof. Osborn recibió$15$ votos y el Prof. Li recibió 10 votos.
Sólo una boleta tenía marcadas las tres urnas.
Cinco de las boletas se marcaron tanto para el Prof. Osborn como para el Prof. Li.
Diez de las boletas electorales fueron marcadas para el Prof. Cheng y el Prof. Osborn.
Seis de las boletas se marcaron para el Prof. Cheng y el Prof. Li.

¿Cuántos integrantes del departamento votaron en la elección?

Solución

Nuevamente, comenzamos por establecer alguna notación. $C$Sea el conjunto de boletas que se marcaron para el Prof. Cheng; que$O$ sea el conjunto de boletas que se marcaron para el Prof. Osborn; y que$L$ sea el conjunto de boletas que se marcaron para el Prof. Li. Entonces lo que queremos es$|C ∪ O ∪ L|$: el número de boletas que se marcaron para al menos uno de los tres candidatos; esto es lo mismo que el número de personas que votaron.

Inclusión-Exclusión nos dice que

$|C ∪ O ∪ L| = |C| + |O| + |L| − |C ∩ O| − |C ∩ L| − |O ∩ L| + |C ∩ O ∩ L|$.

Se nos ha dado todos los valores en el lado derecho de esta ecuación, así vemos que

$|C ∪ O ∪ L| = 18 + 15 + 10 − 10 − 6 − 5 + 1 = 23$.

Hubo diputados$23$ departamentales que votaron en la elección.

De hecho, la información que nos han dado es suficiente para que rellenemos los valores en cada pieza del diagrama de Venn.

$clipboard_e477ccf34e544780d770258393eb8e7bd.png$

El$9$ pueblo que votó por el Prof. Cheng y el Prof. Osborn pero no por el Prof. Li está determinado por el hecho de que la$10$ gente votó por los profesores Cheng y Osborn, y sólo uno de ellos votó por los tres profesores. De igual manera, la$4$ gente que votó por el Prof. Li y el Prof. Osborn pero no por el Prof. Cheng está determinada por el hecho de que la$5$ gente votó por los profesores Li y Osborn, y solo uno de ellos votó por los tres profesores; también, la$5$ gente que votó por el Prof. Cheng y el Prof. Li pero no El profesor Osborn está determinado por el hecho de que la$6$ gente votó por los profesores Cheng y Li, y sólo uno de ellos votó por los tres profesores.

De las deducciones anteriores, vemos que de los$18$ votos que recibió el Prof. Cheng, se marcó una boleta para todos los$3$ candidatos;$9$ se marcaron para los profesores Cheng y Osborn (pero no Li); y$5$ se marcaron para los profesores Cheng y Li (pero no Osborn). Los$3$ votos restantes debieron haber sido solo para el Prof. Cheng, permitiéndonos llenar ese lugar. De igual manera, de los$15$ votos que recibió el Prof. Osborn, se marcó una boleta para todos los$3$ candidatos;$9$ se marcaron para los profesores Cheng y Osborn (pero no Li); y$4$ se marcaron para los profesores Osborn y Li (pero no Cheng). El voto restante debió haber sido solo para el Prof. Osborn, permitiéndonos llenar ese lugar. Por último, todos los$10$ votos del profesor Li se contabilizan entre el$5$ que votó por los profesores Cheng y Li (pero no Osborn), el$4$ que votó por los profesores Li y Osborn (pero no Cheng) y el que votó por los tres, así que pusimos$0$ a en el lugar final.

Ejercicio$\PageIndex{2}$

De$15$ los estudiantes en una clase de estadísticas,$8$ son carreras de matemáticas,$6$ son carreras de CS y$7$ están en educación. Ninguno está en los tres, y ninguno tiene otras especialidades. Hay dos carreras conjuntas de matemáticas/CS, y las carreras de$3$ CS que están en educación. ¿Cuántas carreras de matemáticas hay en educación? ¿Cuántas de las carreras de matemáticas no están en CS ni en educación?
Kevin tiene$165$ aplicaciones en su teléfono. Cada uno de estos que no es un juego y no era gratuito, requiere acceso a internet. De estos,$78$ eran libres. El acceso a Internet es necesario para$124$ que las aplicaciones funcionen completamente. De las apps en su teléfono,$101$ son juegos. Kevin tiene$62$ juegos en su teléfono que requieren acceso a internet;$48$ de estos eran gratuitos. De todos los juegos en su teléfono,$58$ eran gratis. ¿Cuántas de las apps gratuitas en el teléfono de Kevin que no son juegos, requieren acceso a internet?
¿Cuántos números enteros entre$1$ y$60$ son divisibles por al menos uno de$2$,$3$, y$5$?
En el código de$403$ área, ¿cuántos de los números de teléfono posibles$10$ -dígitos (donde se permite cualquier combinación de dígitos) contienen al menos uno de cada dígito impar?
Supongamos$|U| = 15$$|V | = 12$,, y$|U ∩ V | = 4$. Encuentra$|U ∪ V |$.
Supongamos$|R| = 13$$|S| = 17$,, y$|R ∪ S| = 25$. Encuentra$|R ∩ S|$.
Supongamos$|J| = 300$$|J ∪ L| = 500$,, y$|J ∩ L| = 150$. Encuentra$|L|$.
En una universidad pequeña, hay$90$ estudiantes que están tomando Cálculo o Álgebra Lineal (o ambos). Si la clase de Cálculo tiene$70$ alumnos, y la clase de Álgebra Lineal tiene$35$ alumnos, entonces ¿cuántos estudiantes están tomando tanto Cálculo como Álgebra Lineal?
¿Cuántos números de$1$ a$5000$ son divisibles por cualquiera$3$ o$17$?
¿Cuántos números$12$ -dígitos (en los que no está el primer dígito$0$) tienen o no$0$ o no$5$?

Search

Text Color

Text Size

Margin Size

Font Type