Univ. Nacional de Colombia, Medellın – Escuela de MatematicasMatematicas Discretas – Abril 6, 2010

Soluciones Taller 7

1. Pruebe el principio de inclusion-exclusion para tres conjuntos

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|,

usando el caso de dos conjuntos.

Solucion: Tenemos que

|A ∪ B ∪ C| = |(A ∪ B) ∪ C|

= |A ∪ B| + |C| − |(A ∪ B) ∩ C| usando el principio de IE con los

conjuntos A ∪ B y C

= |A| + |B| − |A ∩ B| − |(A ∩ C) ∪ (B ∩ C)|

= |A| + |B| − |A ∩ B| − (|A ∩ C| + |B ∩ C| − |(A ∩ C) ∩ (B ∩ C)|)

usando el principio de IE con los conjuntos A ∩ C y B ∩ C

= |A| + |B| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

2. Determine el numero de enteros entre 1 y 1000 divisibles por 2 o 3 o 5.

Solucion: Usando el principio de inclusion exclusion con conjuntosA, B,C igual a los enteros entre 1 y 1000 divisibles por 2, 3 y 5 respec-tivamente, y que las intersecciones de estos es el conjunto de los enterosdivisibles por los respectivos productos, obtenemos⌊1000

2

⌋+

⌊1000

3

⌋+

⌊1000

5

⌋−

⌊1000

2 · 3

⌋−

⌊1000

2 · 5

⌋−

⌊1000

3 · 5

⌋+

⌊1000

2 · 3 · 5

⌋= 500 + 333 + 200 − 166 − 100 − 66 + 33 = 734

3. Sea A el conjunto de cadenas binarias (0/1) de longitud n, y B el conjuntode cadenas binarias de longitud n + 1 con un numero par de 1’s. Muestreque ambos conjuntos tienen el mismo tamano por medio de una funcionbiyectiva f : A→ B. Verifique que f es una biyeccion.

1

Solucion: Definimosf : A→ B

de la siguiente manera. Para la cadena w ∈ A

f(w) =

{w0 si w tiene un numero par de 1’sw1 si w tiene un numero impar de 1’s

Por la definicion, f(w) es una cadena binaria de longitud n + 1 con numeropar de 1’s y por lo tanto realmente pertenece a B. La funcion f es uno a unoporque si w, w ′ ∈ A con w 6= w ′, entonces f(w) 6= f(w ′) porque al ser w, w ′

diferentes, las imagenes tambien los son por tener w y w ′ como prefijos queya son diferentes. f tambien es sobre: si z ∈ B entonces z = w0 o z = w1,y en ambos casos f(w) = z. Por lo tanto, f es una biyeccion.

4. Un comite compuesto por A, B,C, D, E, F va a seleccionar entre ellos unpresidente, un secretario y un tesorero.

(a) Cuantas selecciones excluyen C ?

Solucion: 5 · 4 · 3(b) Cuantas selecciones excluyen B y F ?

Solucion: 4 · 3 · 2(c) Cuantas selecciones incluyen B y F ?

Solucion: Primero se selecciona el cargo de B y de F, y luego lapersona con el otro cargo: (3 · 2) · 4

(d) Cuantas selecciones incluyen D y excluyen F ?

Solucion: Primero se selecciona el cargo de D y luego las personaspara los otros dos cargos: 3 · (4 · 3)

(e) Cuanas selecciones incluyen D como presidente o no lo incluyen ?

Solucion: Las selecciones que tienen a D como presidente y lasselecciones que no lo incluyen son conjuntos disyuntos: 5 · 4 + 5 · 4 · 3

(f) Cuantas selecciones incluyen B como presidente o tesorero ?

Solucion: Primero se selecciona el cargo de B y luego las personasen los otros dos cargos: 2 · (5 · 4)

(g) Cuantas selecciones tienen B como presidente o A como secretario ?

Solucion: Usando el principio de inclusion/exclusion:

5 · 4 + 5 · 4 − 4 = 36

(h) Cuantas selecciones tienen C como presidente o A en un cargo ?

Solucion: Usando el principio de inclusion/exclusion:

5 · 4 + 3 · (5 · 4) − 2 · 4 = 72

2

5. (a) Cuantos numeros telefonicos de 7 dıgitos (cada dıgito es 0, 1, 2, . . . , 9)son posibles ? Cuantos numeros de estos tienen al menos un dıgitorepetido ?

Solucion: El numero que se quiere se puede obtener como

todas los numeros − numeros sin dıgitos repetidos

El numero de numeros telefonicos posibles es 107 y el numero de estossin dıgitos repetidos es

10 · 9 · 8 · 7 · 6 · 5 · 4.

Por lo tanto, el numero deseado es

107 − 10 · 9 · 8 · 7 · 6 · 5 · 4

(b) Cuantas cadenas de 6 letras con las letras a, b, c contienen al menos unpar de letras consecutivas iguales ? (por ejemplo, la cadena ababac

no tiene letras consecutivas iguales, pero abccba tiene la repeticionconsecutiva cc).

Solucion: El numero que se quiere se puede obtener como

todas las cadenas − cadenas sin letras consecutivas iguales

El numero de todas las cadenas es 36 (cada letra en la cadena puede seruna cualquiera de las tres), y el numero de cadenas sin letras consecu-tivas iguales es 3 · 25 porque la primera letra puede ser una cualquierade las tres y las otras letras puden ser una de las dos letras diferentesde la letra anterior. Por lo tanto, el numero deseado es

36 − 3 · 25.

6. (a) Cuantas cadenas binarias (0/1) de longitud 50 comienzan con 11 oterminan con 0 ?

Solucion: Usando inclusion/exclusion, es el numero de cadenas quecomienzan con 11, mas el numero de las que terminan con 0, menos elnumero de las que tienen ambas propiedades. Entonces el numero es248 + 249 − 247.

(b) De cuantas maneras se puede seleccionar un comite de 4 mujeres y 2hombres de un grupo de 20 mujeres y 10 hombres?

Solucion: El numero de formas de escoger las 4 mujeres por el

numero de formas de escoger los 2 hombres:

(20

4

)·(

10

2

).

3

(c) De cuantas maneras se puede seleccionar un comite de 6 personas deun grupo de 20 mujeres y 10 hombres, si debe contener al menos 2mujeres ?

Solucion: El numero total de formas de seleccionar 6 de 20 menoslas formas de seleccionar 0 mujeres y 6 hombres, y de seleccionar 1

mujer y 5 hombres;

(30

6

)−

(10

6

)−

(20

1

)·(

10

5

).

(d) De cuantas maneras se pueden distribuir 100 libros identicos entre 11estudiantes?

Solucion: Entre las posiciones de 100 libros y 10 “separadores”entre los libros, se debe escoger cuales 10 posiciones corresponden a los

separadores:

(110

10

).

7. (Ejs. 10-17, sec 6.2, JB 6a ed) Determine cuantas cadenas se pueden formarordenando las letras ABCDE sujetas a las condiciones dadas.

(a) Contiene la subcadena ACE (por ejemplo BDACE; ACE debe aparecerconsecutivemente)

Solucion: ACE se puede considerar como una sola letra compuesta.Asi que el resultado es 3! = 6.

(b) Contiene las letras ACE consecutivas pero en cualquier orden.

Solucion: En cada una de las cadenas del caso anterior, se puederealizar cualquiera de las permutaciones de ACE. Por lo tanto el resul-tado es 3! · 3! = 36

(c) Contiene las subcadenas DB y AE.

Solucion: Equivalente a la permutacion de 3 elementos: 3! = 6.

(d) Contiene la subcadena AE o la subcadena EA.

Solucion: Para cada una de AE y EA se tiene una permutacion de4 elementos: 2 · 4! = 48.

(e) A aparece antes de D. Por ejemplo, BCAED, BCADE.

Solucion: Cada una de las 5! permutaciones de ABCDE con A

antes que D tiene una permutacion correspondiente con D antes queA (simplemente intercambie A y D). Por lo tanto el numero deseadoes 1/2 de 5!. Esto es 5!/2 = 60. Solucion alternativa: Comenzandocon AD, la letra B se puede colocar en 3 posiciones, luego la letra C sepuede colocar en 4 posiciones, y finalmente la letra E se puede colocaren 5 posiciones. Se obtiene 3 · 4 · 5 = 60.

4

(f) No contiene ni la subcadena AB, ni la subcadena BE.

Solucion: Contamos el numero N de cadenas con AB o con BE

y restamos esto de 5!. Para determinar N usamos el principio de in-clusion/exclusion: cadenas con AB mas cadenas con BE menos cadenascon ABE (si se tiene la subcadena AB y la subcadena BE entonces setiene la subcadena ABE). Por lo tanto N = 4! + 4! − 3! = 42. Y elreultado final es 5! − 42 = 78.

(g) A aparece antes de C y C aparece antes de E

Solucion: Para las letras A, C y E existen 3! = 6 permutacionesposibles y una de ellas es la que interesa con A, C, y E en ese orden. Porlo tanto el numero de cadenas con A, C y E en ese orden es el numerototal de permutaciones 5! dividido por 3!. Esto es 5!/3! = 5 · 4 = 20.Solucion alternativa: con A, C y E fijas en ese orden, A se puede colocaren 4 posiciones diferentes, y B en 5 posiciones diferentes.

8. (Ejs. 31-36, sec 6.2, Johnsonbaugh, 6a ed) Se tiene un club de 6 hombresdistintos y 7 mujeres distintas. De cuantas maneras se puede formar uncomite con la restriccion especificada.

Solucion: Nota: Aquı C(n, k) denota el numero de k-combinaciones ok-subconjuntos con n elementos:

C(n, k) =n!

(n − k)!k!=

(n

k

)

(a) De 5 personas ?

Solucion: No importa la distincion entre hombres y mujeres:C(13, 5)

(b) De 3 hombres y 4 mujeres ?

Solucion: C(6, 3) · C(7, 4)

(c) De 4 personas con al menos una mujer ?

Solucion:

Alternativa 1: Contamos los comites con 1, 2, 3 y 4 mujeres exacta-mente. Estos son conjuntos disyuntos y por lo tanto podemos usar laregla de la suma. Ademas si se escogen i mujeres entonces se debenescoger 4 − i hombres. Entonces el numero de posibilidades es

C(7, 1) · C(6, 3) + C(7, 2) · C(6, 2) + C(7, 3) · C(6, 1) + C(7, 4) · C(6, 0)

Alternativa 2: Contamos los comites sin mujeres y restamos esto detodos los posibles comites:

C(13, 4) − C(6, 4).

5

Los dos numeros obtenidos deben ser iguales:

C(13, 4)−C(6, 4) = C(7, 1)·C(6, 3)+C(7, 2)·C(6, 2)+C(7, 3)·C(6, 1)+C(7, 4)·C(6, 0)

o, usando C(7, 0) = 1:

C(13, 4) = C(7, 0) · C(6, 4) + C(7, 1) · C(6, 3) + C(7, 2) · C(6, 2) +

C(7, 3) · C(6, 1) + C(7, 4) · C(6, 0).

Esto es cierto porque el numero de formas de seleccionar 4 personas es iguala la suma sobre i de los casos en que se escogen i mujeres y 4 − i hombres,para i = 0, 1, 2, 3, 4. Esta igualdad es un caso particular de

C(n, k) =

k∑i=0

C(n1, i) · C(n2, k − i)

para n1, n2 con n = n1 + n2 y k ≤ n1, k ≤ n2.

(d) De 4 personas con a lo mas un hombre ?

Solucion: Sin hombres o con un hombre: C(7, 4) + 6 ·C(7, 3)

(e) De 4 personas con al menos un hombre y con al menos una mujer ?

Solucion: Todas menos aquellas con solo hombres o solo mujeres:C(13, 4) − C(6, 4) − C(7, 4)

(f) De 4 personas de tal forma que Mabel y Roberto (que son incompati-bles) no son elegidos al mismo tiempo ?

Solucion: Todas las posibilidades menos aquellas con Mabel yRoberto: C(13, 4) − C(11, 2)

9. Determine el numero de maneras en que se pueden reordenar las letras de lapalabra TABLERO de acuerdo con las siguientes restricciones adicionales:

(a) Las sılabas TA, BLE y RO deben preservarse (las letras correspondi-entes aparecen consecutivas y en el mismo orden).

Solucion: Es el numero de permutaciones de 3 objetos distintos:3!

(b) Las letras T, B y R deben aparecer en ese orden.

Solucion: Alternativa 1: Sin restringir se tienen 7! ordenamientos(permutaciones). Estas se pueden dividir en grupos de 3! que provienende un ordenamiento con T, B, R en orden al permutar estas 3 letras. Porlo tanto el numero que se pregunta es 7!/3! = 7 · 6 · 5 · 4 = 840

Alternativa 2: Comenzando con T, B, R en orden, para las restantes4 letras se tienen 4, 5, 6 y 7 posibilidades para ponerlas (inicialmenteT, B, R determianan 4 posibilidades y el numero de estas aumenta por1 despues de cada letra que es agregada. Por lo tanto, la respuesta es4 · 5 · 6 · 7 = 840.

6

(c) Comienza con consonante y termina con vocal.

Solucion: Se tienen 4 posibilidades para la consonante al comienzo y3 para la vocal al final. Las 5 letras restantes se pueden permutar entrela primera y ultima letras, Por lo tanto, el numero de ordenamientoses 4 · 3 · 5! = 1440.

(d) Comienza con TA, BLE o RO

Solucion: Si comienza con TA, BLE o RO, entonces las otras 5,4y 5 letras respectivamente se pueden permutar. Entonces el numero es

5! + 4! + 5! = 264.

10. (a) (Ejemplo 6.1.16, Johnsonbaugh 6a ed) Sea X un conjunto de n elemen-tos. De cuantas formas se puede selecionar pares (A, B) que satisfacenA ⊆ B ⊆ X ?

Solucion: Cada elemento de X puede estar en A, en B − A o enX−B. La seleccion entre estas tres posibilidad para cada x ∈ X resultaen un par (A, B) diferente, y cualquier par (A, B) se obtiene de estamanera. Por lo tanto el numero de tales pares es 3n.

(b) (Esquina de solucion de problemas, sec 6.1, Johnsonbaugh 6a ed) SeaX un conjunto de n elementos. De cuantas formas se puede seleccionaruna tripleta ordenada de conjuntos X1, X2, X3 subconjuntos de X talque

X1 ∪ X2 ∪ X3 = X y X1 ∩ X2 ∩ X3 = ∅

Solucion: Los tres conjuntos X1, X2, X3 determinan 8 subconjuntosdisyuntos de X: X1∩X2∩X3, X1∩X2∩X3, . . ., X1∩X2∩X3 cuya uniones X (forman una particion). La unicas restricciones sobre X1, X2, X3 esque X1 ∩ X2 ∩ X3 = ∅ y X1 ∩ X2 ∩ X3 = ∅. Por lo tanto cada elementode X puede estar en seis de los ocho conjuntos de la particion. Por lotanto, el numero de selecciones posibles es

6 · 6 · · · · · 6︸ ︷︷ ︸n veces

= 6n.

7