Sol Ex Febrero

1
Matem atica Discreta I Soluci on examen 5 de febrero de 2013

Ejercicio 1. Calcular el coeciente de x15 en f (x) = Soluci on: Recordar que (1 x)3 = (1 + x + x2 + . . .)3 Entonces f (x) = x3 (1 + x + x2 + . . .)3 5x(1 + x + x2 + . . .)3 Por lo tanto basta conocer el coeciente en x12 del primer sumando y el de x14 en el 3 3 respectivamente. Entonces el coeciente de x15 en y CR14 segundo, los cuales son CR12 16 14 3 3 . 5C14 = C12 5CR14 f (x) es CR12 Ejercicio 2. Si (G, V ) es un grafo no dirigido sin lazos, se consideran las armaciones: (I) Si existe un u nico camino entre dos v ertices cualesquiera de G, entonces G es un a rbol. (II) Si |V | = |E | + 1, entonces G es un a rbol. (III) Si G es conexo, y si e = {a, b} es una arista de G que es parte de un ciclo, entonces si la eliminamos (manteniendo los v ertices a y b) G e sigue siendo conexo. Soluci on: La armaci on (I ) es verdadera: si existe un u nico camino simple entre cada par de v ertices de G, entonces G es conexo. Si G contiene un ciclo, entonces existen x e y v ertices con dos caminos simples distintos que los unen. Entonces, G resulta un grafo no dirigido, conexo, sin lazos y sin ciclos, y entonces es un a rbol. La armaci on (II ) es falsa: el grafo de la gura cumple |V | = |E | + 1 y no es un a rbol.
x3 5x . (1x)3
La armaci on (III ) es verdadera: como G es conexo, G e tiene lo sumo dos componentes conexas que contienen a a y a b. Para ver que G e es conexo basta ver que a y b est an en la misma componente conexa. Como e es parte de un ciclo en G, existe un camino alternativo que conecta a a y a b sin pasar por la arista e, de modo que es un camino en G e que conecta a a y a b. Por lo tanto, solo (I ) y (III ) son verdaderas.
2 Ejercicio 3. Calcular el n umero crom atico y el polinomio crom atico del grafo G: t
Calculemos primero la cantidad de coloraciones posibles usando colores: el v ertice w puede colorearse de maneras. Una vez jado su color, el v ertice x puede colorearse de 1 maneras (todos los colores excepto el color de w). Ahora, el v ertice y puede colorearse de 1 maneras. El v ertice t puede colorearse de 2 maneras (todos los colores excepto los de x e y que necesariamente son distintos). Finalmente, el v ertice z puede colorearse de 2 maneras. Por la regla del producto, resulta que la cantidad de coloraciones posibles resulta ( 1)2 ( 2)2 . El n umero crom atico es el menor entero positivo que no es ra z del polinomio crom atico, en este caso 3. En suma, (G) = 3 y P (G, ) = ( 1)2 ( 2)2 . Ejercicio 4. De cu antas formas se pueden colocar 24 libros distintos en 4 repisas de modo que haya al menos un libro en cada repisa? Soluci on: Debemos distribuir 24 elementos distinguibles en 4 cajas distinguibles sin que quede ninguna caja vac a. Podemos resolver el problema de distribuir 24 elementos indistinguibles en 4 cajas distinguibles sin que quede ninguna caja vac a y multiplicarlo por 24!. La soluci on de dicho problema es la misma que la de distribuir 20 elementos indistinguibles en 4 cajas 23 23 4 24!. . Luego el resultado es C20 = C20 distinguibles: CR20 Ejercicio 5. Se consideran los conjuntos A = {a, b, c, d, e} y B = {1, 2, 3, 4, 5, 6, 7}. Cu antas funciones f : A B hay tales que f 1 ({1, 2, 3}) = {a, b}? Soluci on: Debemos calcular la cantidad de funciones que cumplen f ({a, b}) {1, 2, 3} y f ({c, d, e}) {4, 5, 6, 7}. Por lo tanto tenemos 3 posibles im agenes para a y para b, y 4 posibles im agenes 2 3 para c, d y e. El resultado es entonces 3 4 .
3 Ejercicios de desarrollo. Ejercicio 1. Demostrar por inducci on completa que n 2 < Soluci on: Paso base: n = 11. 11 2 = 9, por otro lado, desigualdad para n = 11. Hip otesis inductiva: n2< n(n 1) 12
11(111) 12 n(n1) , 12
n Z+ , n 11.
115 6
55 . 6
Como 6 9 = 54 < 55, se cumple la
Tesis inductiva: (n + 1) 2 < Demostraci on: Por hip otesis inductiva (n + 1) 2 = (n 2) + 1 <
(n + 1)n 12
n(n 1) + 12 n(n 1) +1= . 12 12
Como n 11, se cumple 12 < 2n, entonces n(n 1) + 12 n(n 1) + 2n (n + 1)n < = . 12 12 12 Juntando las dos desigualdades de arriba resulta que (n + 1) 2 < como quer amos probar. Ejercicio 2. Resolver la siguiente ecuaci on de recurrencia: an+2 5an+1 + 6an = 2n+1 , con a0 = 3 y a1 = 8. Soluci on: Primero se busca una soluci on a la ecuaci on homog enea an+2 5an + 1 + 6an = 0. Esta ecuaci on tiene como ecuaci on caracter stica a r2 5r + 6 = 0 que tiene soluciones en r = 3 y r = 2. Por lo tanto las soluciones a la ecuaci on homog enea anterior son de la forma n n c1 3 + c2 2 . Luego se busca una soluci on particular de an+2 5an + 1 + 6an = 2n+1 . Como 2n+1 es soluci on de la ecuaci on homog enea, entonces se buscan soluciones de la forma B n 2n donde B es real. Sustituyendo en la ecuaci on de recurrencia B (n + 2)2n+2 5B (n + 1)2n+1 + 6Bn2n = 2n+1 (n + 1)n 12
4 y entonces 4B (n + 2) 10B (n + 1) + 6nB = 2 por lo que B = 1. En suma las soluciones a an+2 5an + 1 + 6an = 2n+1 son de la forma c1 3n + c2 2n n 2n . Como a0 = 3 y a1 = 8, entonces an = 4 3n 2n n 2n . Ejercicio 3. 1. Sea (A, R) un conjunto parcialmente ordenado.
i) Demostrar que si (A, R) es un orden total, entonces es un ret culo. ii) Vale el rec proco de la parte i? (Justique su respuesta con una demostraci on o con un contraejemplo). 2. Sea X = {0, 1, 2} y A = X X . Denimos la siguiente relaci on R sobre A: (a, b) R (c, d) si y solo si i) Demostrar que R es un orden parcial en A. ii) Dibujar el diagrama de Hasse e indicar si es o no un ret culo. iii) Determinar todos los elementos maximales y minimales. iv) Existe elemento m nimo? Existe elemento m aximo? v) Es R un orden total? Soluci on: 1. i) Como R es un orden total, dados x, y A sabemos que est an relacionados, y por lo tanto sup{x, y } existe y es m ax{x, y }. An alogamente para el nmo. ii) El rec proco no es v alido y un contraejemplo puede ser el siguiente: sean U = {1, 2}, A = P (U ) y R la inclusi on. Entonces (A, R) es un ret culo tal que, para cada S, T A, nf {S, T } = S T y sup{S, T } = S T pero {1} y {2} no est an relacionados por lo tanto (A, R) no es un orden total. 2. i) La relaci on es claramente reexiva porque todo par (x, y ) A se cumple que (x, y )R(x, y ) ya que a = c = x y b = d = y . Si (x, y )R(s, t) y (s, t)R(w, z ) entonces se da (1) x < s o (2) x = s e y t. Por otro lado, tenemos que se da (3) s < w o (4) s = w y t z . Si se da (1) y (3), tenemos que x < s < w, por lo tanto x < w. Si se da (1) y (4), tenemos que x < s = w, por lo tanto x < w. Si se da (2) y (3), tenemos que x = s < w e a<c o a=c y bd
5 y t por lo tanto x < w y nalmente, si se da (2) y (4), tenemos que x = s = w e y t z por lo tanto x = w e y z . Luego, en todos los casos mencionados (x, y )R(w, z ) por lo tanto se cumple la propiedad transitiva. Por u ltimo, si (x, y )R(s, t) y (s, t)R(x, y ), entonces debe ser x = s e y = t por lo tanto (x, y ) = (s, t) por lo cual la relaci on es antisim etrica. Concluimos entonces que R es un orden parcial. ii) El diagrama de Hasse es el de la gura: (2,2) (2,1) (2,0) (1,2) (1,1) (1,0) (0,2) (0,1) (0,0) Es un ret culo. iii) Podemos observar que (0, 0) es el u nico elemento minimal y (2, 2) el u nico maximal. iv) El elemento m nimo es el (0, 0) y el elemento m aximo el (2, 2). v) Es un orden total.

Sol Ex Febrero

Cargado por

Copyright:

Formatos disponibles

Sol Ex Febrero

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Sol Ex Febrero

Cargado por

Copyright:

Formatos disponibles

1

Matem atica Discreta I Soluci on examen 5 de febrero de 2013

Como 6 9 = 54 < 55, se cumple la

n(n 1) + 12 n(n 1) +1= . 12 12

También podría gustarte