Taller 7 Matem aticas Discretas

1. Pruebe que para todo entero n 1, alguno de los n umeros , 2, 3, . . . , n est a dentro de 1/n de un entero. M as precisamente, existe entero J, 1 J n, y un entero N tal que |J N| 1/n. Sugerencia: Use el principio del palomar con los intervalos [i/n, (i + 1)/n), i = 0, . . . , n 1, como cajas y la parte fraccionaria de los n umeros j, j = 1, . . . , n, como bolas. Soluci on. Por conveniencia de notaci on, denotamos la parte fraccional de x por medio de fr(x), es decir fr(x) = x x . Si alguno de las partes fraccionarias fr(J) est a en el primer intervalo, entonces |J J | < 1/n, y de aqu que J est a dentro de 1/n del entero N = J . De lo contrario tenemos los n n umeros fr(j) en los restantes n 1 intervalos y por lo tanto hay dos, digamos fr(k) y fr( ) con k > , en el mismo intervalo [i/n, (i + 1)/n). Por lo tanto 0 |fr(k) fr( )| < Entonces 0 |(k k ) ( y 1 n Por lo tanto J con J = k est a dentro de 1/n del entero N = k . Note que J es un entero entre 1 y n 1. 0 |(k ) ( k )| < 2. Pruebe el principio de inclusi on-exclusi on para tres conjuntos |A B C| = |A| + |B| + |C| |A B| |A C| |B C| + |A B C|, usando el caso de dos conjuntos. Soluci on. 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| 1 )| < 1 n 1 n

3. Determine el n umero de enteros entre 1 y 1000 divisibles por 2 o3 o 5. Soluci on. Usando el principio de inclusi on exclusi on con conjuntos A, B, C igual a los enteros entre 1 y 1000 divisibles por 2, 3 y 5 respectivamente, y que las intersecciones de estos es el conjunto de los enteros divisibles por los respectivos productos, obtenemos 1000 1000 1000 1000 1000 1000 1000 + + + 2 3 5 23 25 35 235 = 500 + 333 + 200 166 100 66 + 33 = 734 4. (a) Cu antos n umeros telef onicos de 7 d gitos (cada d gito es 0, 1, 2, . . . , 9) son posibles ? Cu antos n umeros de estos tienen al menos un d gito repetido ? Soluci on. El n umero que se quiere se puede obtener como todas los n umeros n umeros sin d gitos repetidos El n umero de n umeros telef onicos posibles es 107 y el n umero de estos sin d gitos repetidos es 10 9 8 7 6 5 4. Por lo tanto, el n umero deseado es 107 10 9 8 7 6 5 4 (b) Cu antas cadenas de 6 letras con las letras a, b, c contienen al menos un par de letras consecutivas iguales ? (por ejemplo, la cadena ababac no tiene letras consecutivas iguales, pero abccba tiene la repetici on consecutiva cc). Soluci on. El n umero que se quiere se puede obtener como todas las cadenas cadenas sin letras consecutivas iguales El n umero de todas las cadenas es 36 (cada letra en la cadena puede ser una cualquiera de las tres), y el n umero de cadenas sin letras consecutivas iguales es 3 25 porque la primera letra puede ser una cualquiera de las tres y las otras letras puden ser una de las dos letras diferentes de la letra anterior. Por lo tanto, el n umero deseado es 36 3 25 . 5. Cu antas permutaciones hay de abcde en las cuales la primera letra es a, b o c, y la u ltima letra es c, d oe? Soluci on. Podemos obtener estas permutaciomes como uni on disyunta de (1) permutaciones que comienzan con a, b o c y terminan con d o e y (2) permutaciones que comienzan con a o b y terminan con c. Los n umeros son respectivamente 3 2 (3 2 1) y 2 (3 2 1). (Note que 3 2 1 es el n umero de selecciones posibles para las otras tres posiciones.) 2

6. Un comit e compuesto por A, B, C, D, E, F va a seleccionar entre ellos un presidente, un secretario y un tesorero. (a) Cu antas selecciones excluyen C ? Soluci on. 5 4 3 (b) Cu antas selecciones excluyen B y F ? Soluci on. 4 3 2 (c) Cu antas selecciones incluyen B y F ? Soluci on. Primero se selecciona el cargo de B y de F, y luego la persona con el otro cargo: (3 2) 4 (d) Cu antas selecciones incluyen D y excluyen F ? Soluci on. Primero se selecciona el cargo de D y luego las personas para los otros dos cargos: 3 (4 3) (e) Cu anas selecciones incluyen D como presidente o no lo incluyen ? Soluci on. Las selecciones que tienen a D como presidente y las selecciones que no lo incluyen son conjuntos disyuntos: 5 4 + 5 4 3 (f) Cu antas selecciones incluyen B como presidente o tesorero ? Soluci on. Primero se selecciona el cargo de B y luego las personas en los otros dos cargos: 2 (5 4) (g) Cu antas selecciones tienen B como presidente o A como secretario ? Soluci on. Usando el principio de inclusi on/exclusi on: 5 4 + 5 4 4 = 36 (h) Cu antas selecciones tienen C como presidente o A en un cargo ? Soluci on. Usando el principio de inclusi on/exclusi on: 5 4 + 3 (5 4) 2 4 = 72 7. (a) (Ejemplo 6.1.16, JB 6a ed) Sea X un conjunto de n elementos. De cu antas formas se puede selecionar pares (A, B) que satisfacen A B X ? Soluci on. Cada elemento de X puede estar en A, en B A o en X B. La selecci on entre estas tres posibilidad para cada x X resulta en un par (A, B) diferente, y cualquier par (A, B) se obtiene de esta manera. Por lo tanto el n umero de tales pares es 3n . (b) (Esquina de soluci on de problemas, sec 6.1, JB 6a ed) Sea X un conjunto de n elementos. De cuantas formas se puede seleccionar una tripleta ordenada de conjuntos X1 , X2 , X3 subconjuntos de X tal que X1 X2 X3 = X 3 y X1 X2 X3 =

Soluci on. Los tres conjuntos X1 , X2 , X3 determinan 8 subconjuntos disyuntos de X: X1 X2 X3 , X1 X2 X3 , . . ., X1 X2 X3 cuya uni on es X (forman una partici on). La u nicas restricciones sobre X1 , X2 , X3 es que X1 X2 X3 = y X1 X2 X3 = . Por lo tanto cada elemento de X puede estar en seis de los ocho conjuntos de la partici on. Por lo tanto, el n umero de selecciones posibles es 6 6 6 = 6n . n veces 8. (Ejs. 71,72, sec 6.1, JB 6a ed) (a) Cu antos operadores binarios existen sobre el conjunto X = {1, 2, 3, . . . , n} ? En otras palabras, cu antas funciones f : X X X existen ? (b) Cu antos de estos operadores son conmutativos ? (es decir, tales que f(x, y) = f(y, x)) Soluci on. Existen n posibilidades para el valor de f(x, y), para cada uno de los n2 posibles pares (x, y). Por lo tanto, el n umero de operadores binarios es 2 n n n = nn . n2 veces Para un operador conmutativo y un par x, y con x < y, se tiene que f(x, y) = f(y, x) y por lo tanto para x = y s olo se necesita especicar f(x, y) para x < y. Adem as es necesario especicar los valores f(x, x) (en la diagonal). El n umero de pares x y es 1 n(n + 1). 2 (Esto se puede obtener como la mitad de pares que no est an en la diagonal, 1 m as los pares en la diagonal: 2 (n2 n) + n.) Por lo tanto, el n umero de operadores conmutativos es n n n n(n + 1)/2 veces 9. (Ejs. 10-17, sec 6.2, JB 6a ed) Determine cu antas cadenas se pueden formar ordenando las letras ABCDE sujetas a las condiciones dadas. (a) Contiene la subcadena ACE (por ejemplo BDACE; ACE debe aparecer consecutivemente) Soluci on. 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. Soluci on. En cada una de las cadenas del caso anterior, se puede realizar cualquiera de las permutaciones de ACE. Por lo tanto el resultado es 3! 3! = 36 4 = n 2 n(n+1) .
1

(c) Contiene las subcadenas DB y AE. Soluci on. Equivalente a la permutaci on de 3 elementos: 3! = 6. (d) Contiene la subcadena AE o la subcadena EA. Soluci on. Para cada una de AE y EA se tiene una permutaci on de 4 elementos: 2 4! = 48. (e) A aparece antes de D. Por ejemplo, BCAED, BCADE. Soluci on. Cada una de las 5! permutaciones de ABCDE con A antes que D tiene una permutaci on correspondiente con D antes que A (simplemente intercambie A y D). Por lo tanto el n umero deseado es 1/2 de 5!. Esto es 5!/2 = 60. Soluci on alternativa: Comenzando con AD, la letra B se puede colocar en 3 posiciones, luego la letra C se puede colocar en 4 posiciones, y nalmente la letra E se puede colocar en 5 posiciones. Se obtiene 3 4 5 = 60. (f) No contiene ni la subcadena AB, ni la subcadena BE. Soluci on. Contamos el n umero N de cadenas con AB o con BE y restamos esto de 5!. Para determinar N usamos el principio de inclusi on/exclusi on: cadenas con AB m as cadenas con BE menos cadenas con ABE (si se tiene la subcadena AB y la subcadena BE entonces se tiene la subcadena ABE). Por lo tanto N = 4! + 4! 3! = 42. Y el reultado nal es 5! 42 = 78. (g) A aparece antes de C y C aparece antes de E Soluci on. Para las letras A, C y E existen 3! = 6 permutaciones posibles y una de ellas es la que interesa con A, C, y E en ese orden. Por lo tanto el n umero de cadenas con A, C y E en ese orden es el n umero total de permutaciones 5! dividido por 3!. Esto es 5!/3! = 5 4 = 20. Soluci on alternativa: con A, C y E jas en ese orden, A se puede colocar en 4 posiciones diferentes, y B en 5 posiciones diferentes. 10. (Ejs. 31-36, sec 6.2, JB 6a ed) Se tiene un club de 6 hombres distintos y 7 mujeres distintas. De cu antas maneras se puede formar un comit e con la restricci on especicada. Nota: Aqu C(n, k) denota el n umero de k-combinaciones o k-subconjuntos con n elementos: Si P(n, k) denota el n umero de k-permutaciones de n elementos, entonces n! P(n, k) = n(n 1)(n 1) (n k + 1) = (n k)! y P(n, k) n! C(n, k) = = k! (n k)!k! Esto tambi en se escribe con la notaci on n k (a) De 5 personas ? 5 = n! . (n k)!k!

Soluci on. No importa la distinci on entre hombres y mujeres: C(13, 5) (b) De 3 hombres y 4 mujeres ? Soluci on. C(6, 3) C(7, 4) (c) De 4 personas con al menos una mujer ? Soluci on. Se escoge primero una mujer, y luego 3 personas entre los restantes: 7 C(12, 3) Alternativa 1: Contamos los comit es con 1, 2, 3 y 4 mujeres exactamente. Estos son conjuntos disyuntos y por lo tanto podemos usar la regla de la suma. Adem as si se escogen i mujeres entonces se deben escoger 4i hombres. Entonces el n umero 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 comit es sin mujeres y restamos esto de todos los posibles comit es: C(13, 4) C(6, 4). Los dos n umeros 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 n umero de formas de seleccionar 4 personas es igual a 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
k

C(n, k) =
i=0

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

para n1 , n2 con n = n1 + n2 y k n1 , k n2 . Por qu e est a mal la soluci on original (cruzada arriba) ? Porque al seleccionar una de las 7 mujeres como una primera mujer en el comit e, se est a poniendo un orden entre las mujeres seleccionadas (cuando no debe haberlo). (d) De 4 personas con a lo m as un hombre ? Soluci on. 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 ? Soluci on. Todas menos aquellas con s olo hombres o s olo mujeres: C(13, 4) C(6, 4) C(7, 4) (f) De 4 personas de tal forma que Mabel y Roberto (que son incompatibles) no son elegidos al mismo tiempo ? Soluci on. Todas las posibilidades menos aquellas con Mabel y Roberto: C(13, 4) C(11, 2)