Módulo 3 - Principio de Inclusión-Exclusión

A lo largo de los entrenamientos, nos hemos topado con varios problemas de conteo. Hemos visto, sin embargo, un tipo peculiar de estos problemas, en donde al hacer nuestras cuentas nos dábamos cuenta (jaja, valga la redundancia) de que estábamos contando de más, a lo cual teníamos que realizar una resta. Inclusive, hay uno que otro problema del Módulo 2 - Separadores que necesita de esta idea de restar lo que estamos contando de más. En este pequeño módulo veremos ejemplos, ejercicios y problemas de ese estilo, cuya solución se basará en un principio de combinatoria básico pero útil en este tipo de situaciones. Este se llama Principio de Inclusión-Exclusión.

1. Repaso de Notación de Conjuntos

Antes de empezar, hagamos un recordatorio de notación básica de conjuntos. Decíamos que un conjunto era una colección de objetos. Si A era un conjunto, y x era un elemento de él, entonces escribíamos \(x \in A\). Cuando tenemos dos conjuntos, podemos hacer dos operaciones básicas, que son la unión y la intersección. Si A y B son conjuntos, entonces:

• \(A \cup B\) es el conjunto de los elementos que están en A ó en B. Esta es la unión de A y B.
• \(A \cap B\) es el conjunto de los elementos que están en A y en B. Esta es la intersección de A y B.

Como ejemplo breve: Sean \(A = \{a, b ,c\}\) y \(B = \{b, c, d\}\), entonces:

• \(A \cup B = \{a, b, c, d\}\).
• \(A \cap B = \{b, c\}\).

Cuando dos conjuntos A y B no tienen elementos en común, entonces se dice que son disjuntos o mutuamente excluyentes. Matemáticamente se suele escribir así: \(A \cap B = \varnothing\), donde \(\varnothing\) es el conjunto vacío, o sea el conjunto que no tiene elementos. (Sólo como aclaración: Si A y B son disjuntos, está mal escribir \(A \cap B = \{\varnothing\}\), ¿por qué?)

Por último, se mencionan otras dos notaciones de conjuntos:

• Si A es un conjunto, entonces denotamos por \(|A|\) a la cardinalidad de A, es decir, la cantidad de elementos que tiene A.
• Si A es un conjunto que está dentro de un conjunto universo U, entonces denotamos por \(A^c\) ó \(\overline{A}\) al complemento de A. Este se define como el conjunto formado por todos los elementos que no están en A (pero que sí están en el universo U).

Otros ejemplos breves: Si el conjunto universo es \(U = \{1, 2, 3, 4, 5\}\) y \(A = \{1, 3, 5\}\), entonces:

• \(|A|=3\).
• \(\overline{A} = \{2, 4\}\).

(Sólo como aclaración: Hay veces donde el conjunto universo U no se especifica, porque se supone que queda implícito. Hay que tener cuidado en estas ocasiones.)

Bien, si ya eres todo un experto en la notación de conjuntos, pasemos a lo que vinimos. (¡Geniaaal!)

2. Principio de Inclusión-Exclusión

Empecemos con un ejemplo súper básico (¿Quién no ha hecho de estos problemas?).

Ejemplo.

En una escuela hay tres tipos actividades extracurriculares: entrenamientos de olimpiada de matemáticas, entrenamientos de fútbol americano, y clases de actuación. Todos los estudiantes sin excepción deben de llevar al menos una actividad extracurricular, pero pueden inscribirse en todas las que quieran al mismo tiempo. Se sabe lo siguiente respecto al número de estudiantes en las actividades:

• Hay 50 en la de matemáticas, 50 en la de actuación, y 100 en la de fútbol.
• Hay 15 que son tanto de matemáticas como de actuación, 10 que son tanto de actuación como de fútbol, y 30 que son tanto de fútbol como de matemáticas.
• Hay 5 personas que son tanto de matemáticas, como de actuación y fútbol.

¿Cuántas personas hay en la escuela?

Solución

Podemos hacer un diagrama de Venn para facilitarnos las cosas y ver un poco mejor qué es lo que pasa aquí:

Sea T el total de estudiantes que hay en la escuela. Usando la primera pista, tendríamos que

\[ T = 50 + 50 + 100 = 200 \]

pero hay estudiantes que estamos contando de más. Para quitar las repeticiones, utilizamos la segunda pista. Por ejemplo, hay 15 personas que son tanto de matemáticas como de actuación, así que esa cantidad de personas la estamos considerando doble en nuestra primera suma, por lo que hay que restarla una vez para equilibrar nuestras cuentas. Usando el mismo razonamiento para el resto de la información de la segunda pista, tenemos nuestra nueva cuenta como

\[ T = (50 + 50 + 100) - (15 + 10 + 30) = 200 - 55 = 145 \]

pero aun estamos haciendo algo incorrecto. Pensemos: Utilizando la primera pista hicimos la suma de tres cantidades, y dentro de esas cantidades contamos tres veces un grupo de personas: el que va a las tres actividades. Ahora, al usar la segunda pista hicimos la resta de tres cantidades, en las cuales de nueva cuenta se encuentra este peculiar grupo. ¿Qué quiere decir? Que en el resultado nuevo que obtuvimos, no hemos sumado al grupo que va a las tres actividades. Es donde sale al rescate la tercera pista, con cual ahora sí obtenemos el resultado correcto:

\[ T = (50 + 50 + 100) - (15 + 10 + 30) + (5) = 200 - 55 + 5 = 150. \]

Por lo tanto, el resultado es 150 estudiantes. \(\square\)

Ejercicio.

De un grupo de programadores, 35 están familiarizados con ordenadores del tipo A, 41 con ordenadores del tipo B y 46 con algunos de los dos. ¿Cuántos están familiarizados con ambos?

En lo sucesivo, se trabajarán exclusivamente con conjuntos finitos, a menos que se diga lo contrario. De otra manera entraríamos en contradicciones y cosas chistosas que no queremos mencionar por ahora. ;)

Principio de Inclusión-Exclusión, Versión Novato.

Dados dos conjuntos A y B, se tiene que

\[ |A \cup B| = |A| + |B| - |A \cap B|. \]

De igual manera, dado otro conjunto C, se tiene que

\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|. \]

Demostración

(Se deja como problema 1 de la lista de problemas) \(\square\)

¿Por qué se llama "de inclusión-exclusión"? Porque para conocer el total de elementos, primero incluímos cierta cantidad, luego restamos otras cantidades porque estamos contando de más, pero luego volvemos a sumar otras cantidades para contrarrestar lo hecho justo anteriormente, y así sucesivamente. Se van incluyendo y excluyendo cantidades que hacen falta y se repiten, respectivamente. Cuando se incluyen se hace una suma, y cuando se excluyen se hace una resta.

Por lo general, con saber el principio de inclusión-exclusión en su versión novato (las fórmulas antes mostradas) es suficiente para los problemas de concurso. Sin embargo, se presenta su formulación general, que a primera vista parece muy enredosa y sin sentido, pero es cuestión de prestarle atención a la notación para percatarse de que en efecto se cuenta exactamente el total de elementos de esa manera, ni más ni menos.

Principio de Inclusión-Exclusión, Versión General.

Dados n conjuntos \(A_1, A_2, \ldots, A_n\), se tiene que

\[ |A_1 \cup A_2 \cup \cdots \cup A_n| = \]
\[|A_1| + |A_2| + \cdots + |A_n| - |A_1 \cap A_2| - |A_1 \cap A_3| - \cdots - |A_{n-1} \cap A_n| \]
\[+ \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n| \]

o dicho de otra manera

\[ |A_1 \cup A_2 \cup \cdots \cup A_n| = \]

\[\sum_{i}|A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_n| \]

Demostración

¿Se podrá hacer por inducción? ¿Y qué tal si se usa el binomio de Newton? Se deja como ejercicio para el lector. \(\square\)

En la fórmula anterior sólo tenemos que recordar que los signos se van alternando conforme vamos aumentando la cantidad de conjuntos que estamos considerando. Y listo. Ahora pasemos a la parte interesante, la parte sabrosa de los módulos (y los entrenamientos y los exámenes): ¡Los Problemas!

3. Lista de Problemas

1. Demuestra la "versión novato" del principio de inclusión-exclusión.
   
   
2. ¿Cuántos números entre el 1 y el 100 (inclusive) hay tales que son múltiplos de 4, 5 ó 6?
   
   
3. ¿Cuántas soluciones enteras hay para la ecuación \(x_1 + x_2 + x_3 = 12\), de tal forma que \(0 \leq x_i \leq 5\)?
   
   
4. A la Fiesta Secreta de Santa asistieron n personas. Cada una de ellas llevó un regalo, los cuales se juntan y se redistribuyen al azar entre los invitados, de manera que cada uno reciba exactamente un regalo. ¿Cuál es la probabilidad de que a ninguna persona le toque el regalo que llevó inicialmente?
   
   
5. Cuenta la cantidad de impares positivos menores que 120 que no sean múltplos de 3, 5 ó 7.
   
   
6. Un panadero vende tres tipos de panes, a saber: donas, conchas y trenzas, y le quedan 9, 3 y 5 respectivamente de cada uno. ¿De cuántas maneras se puede ordenar una docena de panes?
   
   
7. En cierto juego, se tiene un dado de seis caras. El juego consiste en tirar el dado 5 veces, y el jugador gana si en la última tirada salió el mismo número que en la penúltima tirada. ¿Cuál es la probabilidad de ganar en este juego?
   
   
8. ¿De cuántas maneras se pueden ordenar los números del 1 al 10 en fila, de tal manera que los números 1, 2, 3, 4, 5 no queden en su mismo lugar?
   
   
9. ¿De cuántas maneras se pueden distribuir m pelotas distinguibles en n cajas distinguibles, de manera que en cada caja haya al menos una pelota? (Nota: "Distinguible" significa que se puede saber cuál pelota es cuál, y cuál caja es cuál. Se puede pensar, por ejemplo, que las pelotas tienen distintos colores, y que por eso se pueden identificar, se pueden distinguir del resto.)
   
   
10. A un baile de graduación asisten n parejas. En cierta canción, cada pareja se debe de separar, y después se vuelven a formar n parejas de manera que a ninguna persona le tocó su pareja original. ¿De cuántas maneras puede pasar esto?
    
    
11. ¿Cuántas permutaciones de los números 1, 2, ..., n hay, tales que el número k no está junto al número k+1? (En otras palabras, no hay números adyacentes que sean consecutivos.)
    
    
12. ¿Cuántas manos de póker (5 cartas) hay, tales que se tiene al menos una carta de cada palo?
    
    
13. Encuentra el número de permutaciones de los números 1, 2, ..., 7, de tal manera que queden exactamente tres números fijos. (Por ejemplo, una de dichas permutaciones es 1, 2, 4, 3, 6, 5, 7, porque se quedan fijos el 1, 2 y 7.)
    
    
14. ¿De cuántas formas se pueden colocar todas las letras de la palabra "INFORMATION" de tal manera que ningún par de letras consecutivas aparezca más de una vez? (Por ejemplo, "IINNOOFRMTA" y "FORTMAIINON" son palabras válidas, pero "INFORINMOTA" (donde “IN” aparece dos veces) y "NORTFNOIAMI" (donde “NO” aparece dos veces) no son válidas.)
    
    
15. ¿De cuántas formas se pueden colocar tres a, tres b y tres c de modo que no aparezca la misma letra tres veces consecutivas?
    
    
16. ¿Cuántos números existen entre 1 y 1000, ambos inclusive, que no sean ni cuadrados perfectos, ni cubos perfectos ni cuartas potencias?
    
    
17. ¿De cuántas maneras pueden tres matrimonios sentarse en seis sillas a lo largo de una fila, de tal manera que se alternen hombre-mujer y que ninguna persona quede junto a su pareja?
    
    
18. Determina la cantidad de números primos menores que 111, sin hacer la lista de números primos.
    
    
19. Cada cuadrito de un tablero de \(3 \times 3\) se pintará de rojo o azul. Cada cuadrito tiene la misma probabilidad de ser pintado tanto de rojo como de azul. ¿Cuál es la probabilidad de que en el tablero no haya cuadrados de \(2 \times 2\) rojos?
    
    
20. (IMO 1989) Una permutación \( (x_1, x_2, \ldots, x_{2n}) \) del conjunto \( \{1, 2, \ldots, 2n\} \), donde n es un entero positivo, se dice que tiene la Propiedad P si
    \[ |x_i - x_{i+1}| = n \]
    para alguna i que vaya desde 1 hasta 2n-1. Demuestra que para cualquier n, hay más permutaciones con la Propiedad P que sin ella.

Recompensa:

100 EXP incompleto

500 EXP resolviendo al menos 10 problemas

1000 EXP resolviendo al menos 15 problemas