Ejercicios matemática discretas

EJERCICIOS PROPUESTOS PARA LAS UNIDADES 1, 2, 3 y 4

[pic 1]

Consideremos las temporadas 1, 2 y 3 (a las que respectivamente llamamos A, B y C) de la serie de TV Juego de Tronos. Según transcurre la acción algunos personajes mueren y aparecen otros de tal modo que en las tres temporadas 40 personajes principales aparecen al menos en una de las temporadas. En la primera temporada aparecen 23 personajes principales, en la segunda 22 y en la tercera 25. Que aparezcan en la primera y en la segunda son 13, los mismos que aparecen en la primera y la tercera, pero en la segunda y tercera aparecen 10.

¿Cuántos de los personajes principales aparecen en las tres temporadas? Solución:

Temporada 1= A

Temporada 2= B

Temporada 3= C

Lo que tenemos que calcular el la unión de los 3 conjuntos, por el principio de inclusión exclusión se trata de calcular el cardinal de dicho conjunto pedido.

[pic 2]

Si despejamos X , nos da como resultado 6.

Problema 2:

Sea la relación, en el conjunto de los números enteros, definida como

que dos números a e b están relacionados, a R b, si el valor absoluto de su   [pic 3] resta es Demostrar que es una relación de equivalencia y hallar las clases de equivalencias.

Solución:

Para el primer punto basta con demostrar que es reflexiva, simétrica y transitiva. Es reflexiva pues [pic 4] = 0 y 0 es par. Así que        .[pic 5]

Es simétrica, ya que si        significa que [pic 6] es par, que es igual a [pic 7], asi que        .[pic 8][pic 9]

Si        y        entonces [pic 10] es par y también lo es [pic 11]. Hay dos posibilidades: que a sea impar y que lo sea también b, o que a sea par y lo sea por tanto b. Para el primer caso a es impar y lo es b y por consiguiente, lo tiene que ser c. Como a y c son impares [pic 12]   es par y esto implica a R c. Para el segundo caso a es par y lo es b y por consiguiente, lo tiene que ser necesariamente también c. Como a y c son pares [pic 13] es par y esto implica que a R c.[pic 14][pic 15]

Como podemos ver los enteros solo podrán ser pares e impares, así que el conjunto cociente está formada por estas dos clases:

[pic 16]

Problema 3

Considérese la orden parcial  [pic 17] definida por el conjunto D de los divisores positivos de 66, excluyendo el 1, mediante

[pic 18]  a divide a b.

1. Dibujar el diagrama de Hasse del orden parcial [pic 19]
2. Dar si existen, los elementos maximales y minimales, así como el máximo y mínimo de [pic 20] .
3. Proporcionar las cotas inferiores del conjunto C={6,22,26} Solución:

[pic 21]

Minimales son 2,3 y 11.No hay mínimo. Maximal es el 66, por lo que podemos decir que el máximo el 66. La única cota inferior es 2.

Problema 4:

Considérese la relación de orden parcial ≤ definida por la relación de divisibilidad siguiente. [pic 22]   a divide a b.

Bajo esta relación dibujar el diagrama de Hasse considerando solamente el conjunto de los

números naturales hasta el 8 incluido. Si consideramos el conjunto A = {1,2,3} proporcionar las cotas superiores y el supremo.

Solución:

El conjunto que nos mencionan es el siguiente: C = {1,2,3,4,5,6,7,8}. El diagrama de Hasse será el siguiente:

[pic 23]

Problema 5:

1. ¿Cuántas cartas debes extraer de una baraja española de 40 cartas para asegurar que se extraen al menos dos cartas de distinto número?

1. ¿Cuántas cartas debes extraer de una baraja española de 40 cartas para asegurar que se extraen al menos dos cartas del mismo palo?

1. Si una cabeza humana tiene como máximo 500.000 cabellos, demostrar que en Madrid hay al menos dos personas no calvas que tiene el mismo número de pelos.

1. ¿Que aforo mínimo debe tener un cine para que estando completo haya al menos dos personas cuyo primer apellido empiece y termine por las mismas letras? (Considerar un abecedario de 27 letras).

Solución.

1. El peor caso posible sería que se sacaran las cuatro cartas de un número. En la siguiente extracción necesariamente tendría que ser distinto de ellos. Por consiguiente, por el principio del palomar, basta con sacar 5 cartas.

1. Por el mismo razonamiento que en el problema anterior, el peor caso se extraería una carta de cada palo hasta totalizar 4. La siguiente tendría que repetirse, así que por el principio del palomar, serán 5 cartas.

1. El peor caso posible será una persona con 1 pelo, otra con dos y así sucesivamente hasta

500.000. Como Madrid tiene millones de habitantes entonces hay al menos dos que tienen el mismo número de cabellos.

1. Se asume que los apellidos no tienen que ser realistas. Así por ejemplo Aiaurfhk sería un posible apellido. Naturalmente el número de letras de las que consta cada apellido no importa. La coincidencia entre letras iniciales y finales de los apellidos que se pone como condición es entre distintas personas. Es decir, el apellido de una persona no necesariamente empieza y termina por la misma letra. Así por ejemplo, los apellidos Abad, Abel y Abella se cuentan en este problema. Además los apellidos Alcaraz y Albornoz coincidirían, por ejemplo, según el criterio expuesto como coincidentes. Por tanto habrá 27·27 = 729 posibles pares de letras de comienzo y n. Por el principio del palomar bastaría que haya 730 asientos para que existen dos o más personas que cumplan la condición.

Problema 6:

El ejército del imperio galáctico comandado por Darth Vader ha conseguido doblegar a todos los planetas de la galaxia. Los rebeldes están arrinconados y entre sus filas hay traidores que colaboran con el enemigo. En un acto desesperado, un grupo de rebeldes eles se reúne en el planeta Hoth. Estos deciden enviar unos espías (entre los cuales se encuentran algunos de ellos como Yoda o Skywalker) a 10 de los planetas y lunas del conjunto total de mundos habitables de la galaxia. De este modo quieren recopilar información y buscar puntos débiles del enemigo en el imperio galáctico. De entre los posibles 11 miembros de  la resistencia capacitados para la labor de espía deciden eliminar por traidores a Nardor y Morgana en Tatooine, que se han pasado al lado oscuro de la fuerza. Nardor ha estado funcionado como doble agente en su puesto de gobernador de Tatooine y pasado información a Darth Vader. Morgana mató con sus propias manos el mes pasado a uno de los mejores miembros de la resistencia con la colaboración de Nardor. Yoda y Skywalker se prestan voluntarios para esta labor de eliminación y hacer de espías en Tatooine. A Jar Jar Been lo envían a Dagobah para librarse de él porque ya no lo aguantan más y en donde no puede meter la pata. Además, Han Solo se reserva para él mismo la misión a la luna boscosa de Endor. ¿De cuántas maneras podrán distribuirse los espías de la resistencia entre los objetivos? Distinguir el caso sin restricciones en el que un mundo puede recibir a más de un espía del caso más sensato en el que se tratan de repartirlos para cubrir el máximo número de mundos.

...