COLECCIÓN DE EJERCICIOS DE MATEMÁTICA DISCRETA Profesor: José M. Pacheco Castelao
Aplicación: Un heptadecágono regular
ESCUELA DE INGENIERÍA INFORMÁTICA DE LA ULPGC Curso 2011-2012
1
Índice Parte 1: Ejercicios de Combinatoria…3 Algunos ejemplos más prácticos…6 Más ejercicios de Combinatoria, Inducción, etc….7 Aún más ejercicios…8 Y todavía algunos ejemplos más…9 Parte 2: Ejercicios de Aritmática…10 He aquí otros ejercicios más…12 Otros ejercicios de Aritmética…12 Parte 3: Ejercicios de Conjuntos y Lógica…14 Otro par de ejercicios…15 Más ejercicios de Conjuntos…16 Algunos ejercicios de Lógica…17 Un modelo, resuelto, de preparación del examen final…18 Más ejercicios pre-examen, I…21 Más ejercicios pre-examen, II…22
2
Parte 1: EJERCICIOS DE COMBINATORIA Lean y estudien el siguiente ejercicio de examen (Septiembre de 2008) Habitualmente las caras de los dados de juego están numeradas de 1 á 6, de manera que la suma de los números que se hallan en caras opuestas es 7. Sin embargo, en este ejercicio las preguntas se refieren a dados que no cumplen esa condición Se pregunta, cuántos dados pueden existir de modo que: a) (2 puntos) Sólo un par de caras opuestas sume 7. b) (1 punto) Con sólo dos pares de caras que sumen 7. c) (1 punto) Sin ningún par de caras opuestas que sumen 7. Solución Este ejercicio admite varias interpretaciones. Sin embargo, en todas ellas la cuestión b) tiene siempre contestación negativa: Si se han fijado dos pares de caras opuestas con suma 7, el par restante también sumará 7. Queda, por tanto, contestar a las cuestiones a) y c). a) Supongamos que hemos fijado un par de caras (arriba y abajo) cuyos números sumen 7, lo cual podemos hacer de tres maneras: (1,6), (2,5) y (3,4). No habrá más pares de caras que sumen 7 si en las caras laterales del dado aparecen contiguos dos números que sumen 7. Por ejemplo, si elegimos el par (1,6) para empezar, bastará con saber que 3 y 4 no se hallan enfrentados en los laterales del dado. Esto puede ocurrir de cuatro maneras diferentes: Si la tabla siguiente representa las caras laterales: 3425 seleccionemos las dos primeras posiciones para el 3 y el 4 (hay dos formas: 3-4 y 4-3), así que quedan las otras dos para el 5 y el 2 (en las versiones 2-5 y 5-2). Por tanto, hay cuatro formas de tener un dado con sólo un par de caras (1,6) que suman 7. Como podemos cambiar (1,6) por (2,5) y (3,4), aplicando la regla fundamental de la Combinatoria, hasta ahora habrá en total 12 tipos de dados con sólo un par de caras opuestas que sumen 7. Además, dado que el par (1,6) puede aparecer como 1-6 y 6-1, tendremos en total 24 tipos de dados con sólo un par de caras opuestas que sumen 7. c) Usemos el mismo argumento que en el caso a). Elijamos una cara, p. ej. la 1, y hagamos que su opuesta no sea su complementaria a 7 (en el ejemplo, que no sea 6). Eso puede hacerse de 4 maneras diferentes. Para las cuatro caras laterales queda una pareja que suma 7 y otra que no (en el ejemplo, si tomamos (1,2) para empezar, son (3,4) y (5,6) respectivamente). Pero ya sabemos que hay cuatro modos de conseguir que la pareja que suma 7 no se halle enfrentada. Por tanto, según el principio fundamental de la combinatoria habrá 32 tipos de dados en los que no hay pares de caras opuestas que sumen 7. NOTA 1: Si consideramos que (3,4) es lo mismo que (4,3), etc., el ejercicio se reducirá a estudiar un dado coloreado con tres colores, correspondientes a los pares (1,6), (2,5) y (3,4) y estudiar la distribución cromática. Por supuesto, es más fácil y salen números diferentes. NOTA 2: Aún hay más interpretaciones válidas para el ejercicio…
3
Otro ejercicio de examen (Enero de 2008) Un sudoku de 16 cuadros es un esquema como el siguiente, donde en cada columna, fila y cuadrado aparece una y sólo una vez cada una de las cifras 1, 2, 3, 4:
Calcule razonadamente el número total de sudokus posibles de 16 cuadros. Solución. a) Comenzamos eligiendo la primera fila, que es una permutación de los cuatro elementos {1, 2,3, 4} . Por tanto, hay 4!=24 posibilidades para la primera fila. b) Para la segunda fila: Los dos primeros puestos han de ser ocupados por los dos números que no se hallan en las dos primeras casillas de la primera fila. Esto puede hacerse de 2 maneras diferentes. Lo mismo puede decirse de las posiciones tercera y cuarta de la segunda fila en el cuadrado superior derecho. Por tanto hay 4 posibilidades de elección para la segunda fila. c) Observamos ahora que la tercera fila queda totalmente determinada por las dos primeras casillas (y también el resto del sudoku). Pero hay 4 formas diferentes de rellenar esas dos casillas. Por ejemplo, para la elección de las dos primeras filas dada por la figura de debajo, las posibilidades de rellenar las dos primeras casillas de la tercera fila sin violar las reglas del sudoku son estas cuatro: (2-1), (4-3), (4-1) y (2-3).
Usando ahora el principio básico de la Combinatoria, el número posible de sudokus de 16 cuadrados es 24× 4 ×4 = 384. Propuesta de ejercicios del libro de Rosen: 1. Lean (e intenten) los del Capítulo 4, páginas 287-290 2. Ídem id, páginas 301-303. NOTA IMPORTANTE: En el libro de Rosen se llama r-permutaciones a lo que en clase hemos denominado variaciones de n elementos tomados de r en r. Lecturas del libro de Rosen: Lean el apartado 4.4 (páginas 303-308), para plantear posibles cuestiones en clase.
4
Un ejercicio suplementario para pensar un poco. Habitualmente usamos el sistema decimal para representar números grandes. Con este método, p. ej. el número 314 es una expresión abreviada de la suma siguiente:
3 ×100 + 1× 10 + 4 ×10 = 3 × 102 + 1× 101 + 4 × 100 , de manera que utilizamos las potencias sucesivas de 10 para escribir números cada vez mayores. Pero también podríamos emplear, en lugar de la sucesión creciente de potencias de 10, otra también creciente, por ejemplo la sucesión de las factoriales de los números naturales: {0!, 1!, 2!, 3!, 4!, 5!,...} = {1, 1, 2, 6, 24, 120,...} De este modo, por ejemplo el número 49 quedaría representado como: 49 = 2 × 24 + 1 = 2 × 4!+ 0 × 3!+ 0 × 2!+ 1× 1!+ 0 × 0! = 20010
Según esto, cualquier número entero n se puede escribir así: n=
k = Nk
∑ a k !, con a k =0
k
≤ k.
k
Cuestiones: 1. Mostrar que en este sistema todos los nombres de los números acaban en 0. 2. Comprobar que n! se escribe como un 1 seguido de n ceros. 3. Construir los pasos iniciales de una tabla representativa.
… y para pensar aún un poco más: Intente comprobar que los números entre 0 y 1 se pueden escribir también con este sistema, esto es: Si 0 < x < 1, entonces x =
k = Nk
∑a k =0
5
k
1 , con ak ≤ k . k!
ALGUNOS EJEMPLOS MÁS PRÁCTICOS Ejemplo 1. ¿Cuántas ristras de 6 bits hay que comiencen con 1 y acaben con 00? Solución: Este ejercicio trata claramente de Variaciones con Repetición. Las ristras buscadas son del tipo 1-XXX-00, donde X puede ser 0 ó 1. Además hay que tener en cuenta el orden en que aparecen los dígitos binarios, p. ej. la ristra 1-001-00 se considera diferente de la 1-010-00. Por tanto, el número de ristras es el de posibles grupos XXX, esto es, V32 = 23 = 8. Si los escribimos, tendremos: 1-000-00, 1-001-00, 1-010-00, 1-100-00, 1-111-00, 1-011-00, 1-101-00 y 1-110-00. Notemos que, como 3 > 2, obligatoriamente habrá un bit con nombre repetido en la sucesión XXX. Esta observación se llama a veces “principio del palomar”, “del casillero”, o “principio de Dirichlet”. Notamos también que el total de ristras de 6 bits es V62 = 26 = 64. Ejemplo 2. A un partido de fútbol asisten 6543 espectadores (de pago). Demostrar que hay por lo menos 17 que cumplen años el mismo día del año. Solución: Este ejercicio es una “aplicación del principio del palomar”. Como el año tiene 365 días (si no es bisiesto, claro), hay que distribuir a los 6543 espectadores en 365 casillas. Como 6543 > 365, en alguna casilla habrá más de uno (he aquí el famoso principio en acción). Dado que 6543:365 = 17,92…, encontraremos al menos un día en el que cumplen años más de 17 espectadores. Nota importante: El ejercicio asegura que existe algún día en el que hay más de 17 cumpleañeros simultáneos entre los espectadores: Perfectamente, podrían todos cumplir años el mismo día, y lo pedido seguiría siendo cierto. Ejemplo 3.
Consideremos el conjunto de 3 elementos
{a, b, c} .
Sabemos que existen 3! = 6
permutaciones en él. Entre ellas hay algunas que forman grupos de permutaciones circulares. Por ejemplo, (abc), (bca) y (cab) forman uno de esos grupos. Se llaman circulares porque las letras siempre conservan sus posiciones relativas:
... → a → b → c → a → b → c → ... ¿Cuántos grupos hay de permutaciones circulares de 3 elementos? ¿Y de n objetos?
6
Solución: En este ejercicio, para la primera pregunta, fijemos un elemento, p. ej. el a. A partir de él colocamos b y c en cualquiera de las dos formas posibles: bc ó cb y así obtendremos las siguientes pautas: ... → a → b → c → a → b → c → ... ... → a → c → b → a → c → b → ...
Luego hay sólo dos posibles grupos de permutaciones circulares con tres objetos. Notamos ahora que 2 = 2!, y pasamos al caso de n objetos. Comencemos fijando el primero, a1 , y pongamos a continuación de él una permutación cualquiera de los n − 1 restantes. Como de éstas hay (n − 1)! , éste es número posible de grupos de permutaciones circulares. En fórmulas: PCn = (n − 1)! = Pn −1.
MÁS EJERCICIOS DE COMBINATORIA, INDUCCIÓN, ETC. Ejercicio 1.
x n +1 − 1 . Nótese que x es un número x −1 k =0 cualquiera, fijo, positivo y distinto de 1 (para no molestar ¿por qué?), y que la inducción hay que hacerla sobre la variable n.
Demostrar por inducción la siguiente fórmula:
n
∑ xk =
Ejercicio 2.
Calcular el valor de la fórmula
n
⎛n⎞
∑ ⎜ k ⎟ 2 . NOTA: Usar el desarrollo del binomio (1 + 2) k =0
k
⎝ ⎠
n
.
Solución: n ⎛n⎞ Recuerde, según la NOTA, el desarrollo del binomio: (1 + x) n = ∑ ⎜ ⎟ x k . Elija un valor k =0 ⎝ k ⎠ adecuado para x, y ya está.
Ejercicio 3. Calcule el coeficiente de x 2 yz en el desarrollo del trinomio ( x + 2 y + 3 z ) 4 .
Solución: Recuerde, para calcular, que el desarrollo de (a + b + c) n es
∑
k1 + k2 + k3 = n
Pk1k2 k3 a k1 b k2 c k3 .
Ejercicio 4. Los teléfonos fijos españoles poseen una numeración con las siguientes características: • Tienen 9 cifras.
7
• •
La primera puede ser 9 u 8. La segunda y tercera representan números entre 11 y 63 (esto no es exactamente así, pero para el ejercicio lo consideraremos cierto) ¿Cuántos números posibles hay para teléfonos fijos?
NOTA: Use el principio fundamental de la Combinatoria.
AÚN MÁS JERCICIOS DE COMBINATORIA Ejercicio 1. ¿Cuántas “palabras” de longitud k se pueden construir con n letras? a) Si cada letra puede aparecer sólo una vez. b) Si hay una letra repetida, sólo puede aparecer dos veces en la palabra. Calcularlo en particular para n = 7, k = 4. Ejercicio 2. Demostrar, usando el llamado principio del palomar, que dados n números (n ≥ 2) enteros, entre ellos hay por lo menos 2 cuya diferencia es múltiplo de n − 1 ¿Y si hablamos de la suma en lugar de la diferencia? Ejercicio 3. Considere la regla de recurreencia an = 3an −1 − 2an − 2 junto con las condiciones iniciales a1 = 3, a2 = 5 . Calcule los seis primeros términos de la familia de números an e intente hallar una fórmula sencilla y cerrada equivalente a la recurrencia. Ejercicio 4. En el Análisis Matemático se usa con frecuencia la llamada “desigualdad de Bernouilli”: (1 + x ) n ≥ 1 + nx , válida para cualesquiera n ∈ y x > 0. a) ¿De dónde sale esta fórmula? b) Demostrarla. n2 − n 2 n c) Probar que puede mejorarse en la forma (1 + x) ≥ 1 + nx + x ¿Qué se quiere 2 decir aquí con mejorar? Ejercicio 5. Considérese la siguiente permutación de 9 elementos:
⎛a b c d e f g h ⎜ ⎝f g h d i e c b a) Escribirla como producto de ciclos. b) Representarla como producto de transposiciones.
8
i⎞ ⎟ a⎠
Y TODAVÍA ALGUNOS EJERCICIOS MÁS DE COMBINATORIA Ejercicio 1. ¿Cuántos ceros hay al final del número 999!? ¿y del 1000!? Ejercicio 2. Demostrar que los números de Stirling de segunda clase satisfacen las siguientes relaciones:
⎛ n + 1⎞ n S n +1,n = ⎜ ⎟ y S n +1,2 + 1 = 2 . ⎝ 2 ⎠ PISTA: ESTUDIAR EL TRIÁNGULO DE LOS NÚMEROS DE STIRLING. Ejercicio 3. La figura siguiente muestra el alfabeto irlandés conocido como ogham o alfabeto uncial, que sólo tiene 18 letras:
En las largas tardes de invierno, en el célebre pub An bheoir1 se ha planteado un juego que consiste en ordenar lexicográficamente (como en los diccionarios normales) todas las permutaciones de las 18 letras y escribirlas en servilletas. No importa que se mezclen mayúsculas y minúsculas. El ganador de cada ronda recibirá como premio el peso del gato del propietario del pub en cerveza, aunque se le recomienda compartirla con el resto de la clientela, pues el animal es más bien rollizo… En la primera ronda del juego, ganará quien escriba correctamente y en su orden las cuatro palabras centrales de la lista ¿Cuáles son?
1
Significa “La cerveza”.
9
Parte 2: EJERCICIOS DE ARITMÉTICA Primer ejercicio. Calcular las descomposiciones en producto de números primos de a = 185; b = 950; c = 1000; d = 1155. A partir de ellas, hallar también: MCD(a, b); MCM (c, d ); MCD(a, b, c); MCM (b, c, d ). Segundo ejercicio (CON SOLUCIÓN). Si n es un número entero positivo, representaremos por d (n) el número total de sus divisores. Por ejemplo, d (6) = 4 porque los divisores de 6 son {1, 2,3,6} . a) Mostrar que si p es primo, entonces d ( p) = 2. Claramente es así porque los números primos sólo pueden tener dos divisores: El 1 y el propio número. b) Si p es primo, entonces d ( p k ) = k + 1 para cualquier natural k. Es fácil, porque todos los posibles divisores de p k son de la forma p j , con j = 0,1,..., k − 1, k . Por tanto hay k + 1 divisores. c) ¿Cuánto valdrá d ( p k q r ) ? Haciendo una tabla se ve de inmediato que d ( p k q r ) = (k + 1)(r + 1) . d) Generalizar c). Dado un número entero positivo no nulo n, descompuesto en factores primos, n = p a1 p a2 ... p ak , aplicando repetidas veces el resultado anterior se obtiene que d (n) = d ( p a1 ... p ak ) = (a1 + 1)(a2 + 1)...(ak + 1) . e) Hallar el número total de divisores de 14850. Puesto que 14850 = 2 × 33 × 52 ×11 , se tiene: d (14850) = 2 × 4 × 3 × 2 = 48.
Tercer ejercicio (CON SOLUCIÓN). La notación a b significa que “a divide á b”. Probar las siguientes implicaciones: a) De a (b + c) y a b se deduce que a c . Para verlo, recordemos que a (b + c) quiere decir que existe un cierto número entero q1 tal que a × q1 = b + c . De igual manera, habrá otro entero q2 tal que a × q2 = b. Así pues, tendremos que: a × q1 = b + c = a × q2 + c, de donde c = a × (q1 − q2 ) = a × q3 , o bien a c . b) De a bc se deduce que a b ó a c. Este no necesita casi escribir fórmulas. Si a bc , descompongamos a y bc en factores primos. En la descomposición de a
habrá sólo factores de los que aparecen en la descomposición del producto, y con exponentes como mucho iguales a los del producto. Si sólo hubiera factores de los de b, a dividiría a b (lo mismo para c). Si hubiese de los dos, entonces a divide a ambos, b y c.
10
Cuarto ejercicio (CON SOLUCIÓN). Probar que, cualquiera que sea el número natural n ≥ 1 , la expresión 11n +1 + 122 n −1 representa un número divisible por 133. Se trata de un ejercicio claro de inducción. El primer paso es fácil: n = 1 ⇒ 112 + 121 = 121 + 12 = 133 = 133 × 1 n = 2 ⇒ 113 + 123 = 1331 + 1728 = 3059 = 133 × 23
Segundo paso: Supongamos ahora que al poner n − 1 en lugar de n el número obtenido es múltiplo de 133, esto es, 133 divide á 11n + 122( n −1) −1 = 11n + 122 n −3 . Tercer paso: Obtengamos que la propiedad dicha es válida también para n, basándonos en la validez del segundo paso. En efecto: 11n +1 + 122 n −1 = 11× 11n + 122 × 122 n −3 = 11× 11n + 144 × 122 n −3 =
= 11×11n + (144 − 11 + 11) × 122 n −3 = 11× 11n + 11× 122 n −3 + (144 − 11) × 122 n −3 = = 11× (11n + 122 n −3 ) + 133 × 122 n −3 = = 11× (un múltiplo de 133) + otro múltiplo de 133. Quinto ejercicio. Aplicar el algoritmo de Euclides para determinar los MCD de todas las parejas de números del ejercicio primero. Sexto ejercicio (CON SOLUCIÓN). Calcular los coeficientes necesarios para escribir el número 50 como combinación lineal de 25 y 35. ¿Es posible hacer lo mismo con los números 35 y 28? ¿por qué? Se trata de ver si es posible encontrar dos números enteros R y S (positivos o negativos) tales que 25 × R + 35 × S = 50. Notemos, para empezar, que cualquier combinación lineal 25 × p + 35 × q con coeficientes enteros es múltiplo del MCD de 25 y 35. Este resulta ser 5, que sí es divisor de 50. Por tanto, el problema tiene solución. Dividamos ahora 25 × R + 35 × S = 50 entre 5 para obtener 5 × R + 7 × S = 10. Observamos que 5 y 7 son primos entre sí, luego por el Teorema de Bézout existen dos números r y s tales que 5 × r + 7 × s = 1. Directamente, o mediante el algoritmo de Euclides vemos que r = 3 y s = −2 , esto es 5 × 3 + 7 × (−2) = 1. Multipliquemos ahora esta ecuación sucesivamente por 5 y por 10, y tendremos: [5 × 3 + 7 × (−2) = 1] × 5 ⇒ 25 × (3) + 35 × (−2) = 5
[25 × (3) + 35 × (−2) = 5] × 10 ⇒ 25 × (30) + 7 × (−20) = 50 Por tanto, se obtiene que R = 30 y S = −20.
11
La contestación a la segunda pregunta es negativa, pues el MCD de 35 y 28 es 7, que NO ES DIVISOR de 50. HE AQUÍ OTROS EJERCICIOS MÁS: Primer ejercicio. Calcular las descomposiciones en producto de números primos de a = 185; b = 950; c = 1000; d = 1155. A partir de ellas, hallar también: MCD(a, b); MCM (c, d ); MCD(a, b, c); MCM (b, c, d ). Segundo ejercicio. Si n es un número entero positivo, representaremos por d (n) el número total de sus divisores. Por ejemplo, d (6) = 4 porque los divisores de 6 son {1, 2,3,6} .
f) Mostrar que si p es primo, entonces d ( p) = 2. g) h) i) j)
Si p es primo, entonces d ( p k ) = k + 1 para cualquier natural k. ¿Cuánto valdrá d ( p k q r ) ? Generalizar c). Hallar el número total de divisores de 14850.
Tercer ejercicio. La notación a b significa que “a divide á b”. Probar las siguientes implicaciones: c) De a (b + c) y a b se deduce que a c .
d) De a bc se deduce que a b ó a c. Cuarto ejercicio. Probar que, cualquiera que sea el número natural n, la expresión 11n +1 + 122 n −1 representa un número divisible por 133. Quinto ejercicio. Aplicar el algoritmo de Euclides para determinar los MCD de todas las parejas de números del ejercicio primero. Sexto ejercicio. Calcular los coeficientes necesarios para escribir el número 50 como combinación lineal de 25 y 35. ¿Es posible hacer lo mismo con los números 35 y 28? ¿por qué? OTROS EJERCICIOS DE ARITMÉTICA… Primer ejercicio.
Establecer la validez de la llamada “prueba de los nueves”, usada en las escuelas elementales para comprobar si una operación aritmética está bien realizada. Segundo ejercicio.
Hasta el año 2005 los libros se codificaban de acuerdo con el International Standard Book Number de 10 cifras (ISBN-10). Este código es de 9 cifras, que identifican el país, la
12
editorial y el título, más un último dígito de control que se obtiene de la siguiente forma: Dadas las 9 cifras a1a2 a3a4 a5a6 a7 a8 a9 , se calcula el dígito de control a10 mediante la 9
congruencia siguiente: a10 ≡ ∑ iai (11) . i =1
• •
Hallar el dígito de control del ISBN-10 del libro en cuyo código las nueve primeras cifras son 844814073 (Solución: mirar el Rosen). También se encuentran libros cuyo ISBN-10 tiene por dígito de control una X ¿Por qué?
Tercer ejercicio. Establecer razonadamente el criterio por el cual se puede saber si un número entero dado es divisible por 11 (sin hacer la división, claro está). ¿Es 15752 divisible por 11?
Cuarto ejercicio. Al construir un sistema de transmisión de datos se intenta agrupar un cierto número de cables en unos conductos. Al agruparlos de 13 en 13 se observa que hay que añadir un conducto extra para tres cables, si se colocan de 7 en 7 resulta que una de las vías queda sólo con 5 cables, mientras que en grupos de 5 cables queda uno con 4. Se pide calcular el número de cables, atendiendo a los siguientes puntos: •¿Tiene solución el problema planteado? Justificar razonadamente por qué. •¿Cuál es el número mínimo de cables que se están utilizando?
Quinto ejercicio. Escribir en código la frase “El libro de Rosen es bastante grueso” utilizando la clave 234, esto es, dividiendo tal frase en grupos de tres letras y aplicando a la primera letra un código César-2, a la segunda uno César-3 y a la tercera uno César-3, y así sucesivamente. Efectuarlo de dos formas: • Contando sólo las letras (alfabeto español de 26). • Contando también los espacios como si fueran letras.
13
Parte 3: EJERCICIOS DE CONJUNTOS Y LÓGICA Primer ejercicio. En este ejercicio, si A es un conjunto, la notación A se lee “el cardinal de A” y se suele interpretar, para conjuntos no infinitos, como “el número de elementos que posee el conjunto A”. La regla fundamental para el cálculo con cardinales es la siguiente: A∪ B = A + B − A∩ B • •
Demostrar dicha regla. Resolver el siguiente enigma: En la macrofiesta del día de Santa Bibiana (2 de Diciembre), patrona del pueblo ABC, celebrada en la discoteca XYZ, se dejó entrar a 1000 personas. Para animar la fiesta se repartieron al principio, de forma gratuita, 600 refrescos de cola, 450 de zumo de maracuyá con arándanos silvestres y 450 cervezas de una marca nueva que estaba en promoción. No se llevó mucho control, así que poco después se observó gente que se había apropiado de más de una botella o lata. Un recuento de urgencia llevado a cabo por el equipo de relaciones públicas del local mostró que el 20% llevaban cerveza y cola, que el 25% habían conseguido zumo y cola, y que otro 15% estaba provisto de cerveza y cola. Incluso cincuenta avispados se llevaron de las tres cosas. Se pregunta: o ¿Se quedó alguien sin bebida gratuita? En caso afirmativo ¿cuántos? o Bastantes pudieron conseguir sólo una de las tres ¿Cuántos se quedaron sólo con una, según las diferentes clases? o ¿Qué porcentaje del total tuvo acceso exactamente a dos tipos de bebida?
Segundo ejercicio. Se llama orden lexicográfico al orden el cual aparecen las palabras en los diccionarios. Para establecer este orden es necesario disponer de un alfabeto previamente bien ordenado para el conjunto de letras individuales, como puede ser el {a < b < c < d ...} , y con ayuda
de él se ordenan todas las palabras: En primer lugar van las que comienzan por a. Dentro de éstas, se mira la segunda letra, y se coloca primero el que tenga la letra más próxima a la a. Por ejemplo, amapola < anguila, si las segundas letras son iguales, se comparan las terceras, p.ej. abertura < abierto < abrir, etc. Al acabar con la a, se sigue con la b, etc. etc. Se pide: • ¿Es total el orden lexicográfico? ¿Qué ventaja práctica tiene el que lo sea, en caso afirmativo? • Si se inventa una nueva palabra, p.ej. “libroderrosen” ¿Cuál es el algoritmo para ubicarla en un diccionario) • A veces se usa el “orden lexicográfico inverso” ¿en qué puede consistir tal cosa? • Ordenar lexicográficamente todas las ristras de 12 bits usando como alfabeto auxiliar el {0 < 1} .
14
OTRO PAR DE EJERCICIOS Primer ejercicio (usar libros). En este ejercicio, sean A = Z y B = Z − {0} . Construimos el producto cartesiano de ambos,
Z × ⎡⎣Z − {0}⎤⎦ , y en él establecemos la relación: [ (a, b) R (c, d ) ] ⇔ [ ad = bc ] .
(
)
El conjunto cociente Z × ⎡⎣Z − {0}⎤⎦ / R se denomina “conjunto de los números racionales” y se denota con la letra (la inicial de “quotient” o “cociente”). • Comprobar que R es una relación de equivalencia. • ¿Cuál es la clase de equivalencia del par (4,1) ? ¿Y del (3, 0) y del (1,3) , respectivamente? • Establecer las reglas aritméticas para números racionales. Segundo ejercicio.
En este ejercicio, sean A = Z y B = . Construimos el producto cartesiano de ambos, A× B = Z × N . • Representar gráficamente este conjunto. • Representar en el dibujo anterior la relación R = {a −4 ≤ a ≤ 4} × {b b ≤ 5} . o ¿Se trata de una función? o ¿Tal vez una relación de equivalencia?
Sea ahora la relación R* = {a −4 ≤ a ≤ 4} × {2} ⊆ R . Demostrar que es una función, y además inyectiva, entre un cierto subconjunto de Z y otro de N ¿cuáles? Tercer ejercicio (usar libros, otra vez).
En el conjunto Z existe la relación de orden “natural” siguiente: {... < −3 < −2 < −1 < 0 < 1 < 2 < 3...} . Se puede definir una relación de orden sobre de la manera siguiente: [ (a, b) < (c, d ) ] ⇔ [ ad < bc ] . • •
Probar que la relación establecida sobre los números racionales es de orden, y además es total. Se puede identificar el conjunto Z con un subconjunto de mediante el isomorfismo por el que n ∈ Z se corresponde con [ (n,1) ] ∈ . Demostrar que con
•
esta identificación se puede extender el orden de los enteros a los arcionales y que entre cada dos enteros hay infinitos racionales. A pesar de lo anterior, el cardinal de los racionales no es mayor que el de los racionales, esto es: Z = . Buscar una demostración de este hecho aparentemente contradictorio.
15
MÁS EJERCICIOS DE TEORÍA DE CONJUNTOS Primer ejercicio (Rosen, p. 101 y sigs). Ej. 30: “Sean f ( x) = ax + b y g ( x) = cx + d dos funciones reales de variable real, donde a, b, c y d son constantes. Hallar los valores de dichas constantes para que se cumpla que f g = g f ”. definida por f ( x) = ax + b , siendo a y b Ej. 31: “Demostrar que la función f : → constantes, es inversible excepto si a es nula. Hallar la función inversa”. Ej. 64: “Sean A y B dos conjuntos finitos con el mismo cardinal. Demostrar que toda función inyectiva entre A y B es epiyectiva, y recíprocamente”. Segundo ejercicio (Rosen, p. 107) Ejercicios 39 a 44, ambos inclusive. Tercer ejercicio. Sean A y B dos conjuntos finitos tales que A = n > 0 y B = m > 0 . Sea además una
función f : A → B . Se pide: • Considerando f como una relación (subconjunto del producto cartesiano A × B ) ¿Cuál es el mayor cardinal posible que puede tener f ? • Establecer las relaciones que ligan m y n en los casos en que f sea inyectiva, epiyectiva y biyectiva, respectivamente. Cuarto ejercicio. Se considera el conjunto A = {a, b, c, d } . El símbolo A A representa el conjunto de todas las
funciones f : A → A , y el símbolo f 2 ( x) significa f ( f ( x)) . Se pide: •
Hallar A A y escribir todas las posibles funciones que constituyen A A .
• • •
¿Cuántas funciones hay en A A que satisfagan f 2 ( x) = f ( x) ? ¿Y f 2 ( x) = x ? ¿Y f 2 ( x) = f 3 ( x) ?
Quinto ejercicio. La función característica de un conjunto A se define como χ A : A → {0,1} , que actúa de la
⎧ 1, si x ∈ A siguiente forma: χ A ( x) = ⎨ ⎩0, si x ∉ A Se pide: • Probar que χ A∪ B = χ A + χ B − χ A × χ B . • Ídem íd. χ A∩ B = χ A × χ B • Redacte brevemente qué relación observa entre las fórmulas anteriores y las empleadas para el cálculo del cardinal de la unión de dos conjuntos.
16
ALGUNOS EJERCICIOS DE LÓGICA Primer ejercicio. • Se considera la fórmula lógica ( p ⊕ q) → ( p ∧ ¬q ) . Decidir, mediante una tabla de verdad, si se trata de una contingencia, una tautología o una contradicción. • Ídem íd. (¬p ↔ ¬q) ↔ ( p ↔ q ) . Segundo ejercicio. Considérense tres proposiciones p, q, r. Si se construye una tabla de verdad con todas las posibles “combinaciones” de ellas mediante los conectivos lógicos, ¿Cuántas columnas tendrá la tabla? Tercer ejercicio (la demostración “por el contrarrecíproco”) Muchos teoremas matemáticos, expresiones del tipo p → q , se demuestran tratando de probar ¬q → ¬p en lugar de atacar directamente la forma original p → q . Para ver que esta técnica de demostración es correcta, hay que establecer la equivalencia lógica entre las expresiones p → q y ¬q → ¬p : • Hacerlo. • Aplicarlo al caso en que p → q es: “Si la última cifra de un número entero positivo es 0 ó 5, entonces ese entero es múltiplo de 5” Cuarto ejercicio. Se considera la siguiente función proposicional: p( x) = ⎡⎣ x 2 + 1 ≤ 0 ⎤⎦ ¿Para qué valores
reales de la variable x se convierte en una proposición verdadera? ¿Y para valores complejos? Quinto ejercicio. Libro de Rosen, p. 37. Ejercicios 22 y 23. Sexto ejercicio. Libro de Rosen, p. 50. Ejercicios 27 y 28.
17
Un Modelo de Preparación para el Examen de Matemática Discreta (Para este ejemplo concreto, el máximo posible es de 18 puntos)
NOTAS MUY IMPORTANTES CON RELACIÓN AL EXAMEN 1. En todos los ejercicios ha de EXPLICARSE CON DETALLE el proceso seguido. Se calificará con 0 (cero) puntos cualquier ejercicio que carezca de explicaciones, aunque el resultado final sea el correcto. 2. NO SE PUEDEN DEJAR EJERCICIOS EN BLANCO. Dejar uno o más de ellos implica automáticamente NO APROBAR el examen, con nota total 0 (cero). 3. Para SUPERAR el examen, una vez satisfechas las condiciones 1 y 2 anteriores, será necesario obtener COMO MÍNIMO 9 (nueve) puntos, y en CADA EJERCICIO AL MENOS 1 punto. 4. Tiempo estimado: HORA Y MEDIA. Ejercicio Primero (Combinatoria y recurrencia) (3+3 puntos). • ¿Cuál es la diferencia entre Variaciones y Combinaciones de n elementos tomados de k en k? De las cantidades V68 y C79 , ¿cuál es mayor? La diferencia está en que al calcular Variaciones se tiene en cuenta el orden en que se eligen los k elementos, pero no al calcular Combinaciones. Sabemos que Vkn = n × (n − 1) × ... × (n − k + 1) siendo en este caso n = 8, k = 6 . Por tanto
V68 = 8 × 7 × 6 × 5 × 4 × 3 = 20160, pues n − k + 1 = 8 − 6 + 1 = 3 . Calculando por otro lado las ⎛9⎞ 9! combinaciones, se tiene C79 = ⎜ ⎟ = = 36 , luego V68 > C79 . 7 7!2! ⎝ ⎠ • Se da la relación de recurrencia an = 3an −1 + 54 an − 2 , con las condiciones iniciales a0 = 1 , a1 = 2 . Resolverla, razonando el proceso. Como la recurrencia dada es lineal, supondremos que las soluciones son del tipo an = r n , donde r es una cantidad que se determinará. Dado que la recurrencia es de segundo orden, habrá dos valores para r, r1 y r2 , y la solución de la recurrencia se escribirá en la forma
α r1n + β r2n , donde las constantes α y β se determinan utilizando las condiciones iniciales (libro de Rosen, hacia la página 372) De an = 3an −1 + 54 an − 2 obtenemos r n = 3r n −1 + 54 r n − 2 , o bien r 2 = 3r + 54 . Resolviendo esta 5 1 ecuación de segundo grado hallamos r1 = y r2 = . Luego las soluciones son del tipo 2 2 n n ⎛5⎞ ⎛1⎞ an = α ⎜ ⎟ + β ⎜ ⎟ . Para calcular las constantes resolveremos un sistema utilizando los ⎝2⎠ ⎝2⎠ valores de las condiciones iniciales:
18
0 ⎧ ⎛ 5 ⎞0 ⎛1⎞ + α β ⎪ ⎜ ⎟ ⎜ ⎟ = a0 ⎪ ⎝2⎠ ⎝2⎠ ⎨ 1 1 ⎛1⎞ ⎪ ⎛5⎞ ⎪ α ⎜⎝ 2 ⎟⎠ + β ⎜⎝ 2 ⎟⎠ = a1 ⎩ ⎧ α + β =1 ⎪ o bien ⎨ 5 1 ⎪⎩ 2 α + 2 β = 2 n
n
3⎛5⎞ 1⎛1⎞ 3 1 El resultado obtenido es: α = y β = . Luego an = ⎜ ⎟ + ⎜ ⎟ . 4⎝2⎠ 4⎝2⎠ 4 4
Ejercicio Segundo (Aritmética Entera y Modular) (3+3 puntos). • Resolver razonadamente la ecuación diofántica 6 x + 3 y = 54 , escribiendo la totalidad de las soluciones. Veamos en primer lugar si tiene solución o no. El MCD de 6 y 3 es 3, que es divisor del término independiente, pues 54 = 3 × 18 . Esto es, existen soluciones de esta ecuación diofántica. Para hallarlas: 1. Dividimos toda la ecuación por el MCD, quedará 2 x + y = 18 . 2. Resolvemos 2 x + y = 1 mediante el Teorema de Bézout, obteniendo 2 ×1+1× (−1) = 1. 3. Multipliquemos la última expresión por 3 y 18, y reordenemos los términos: [2 ×1+1× (−1) = 1] × 3 ×18 ⇒ 6 ×18 + 3 × (−18) = 54 . Luego ya tenemos UNA solución: ( x = 18, y = −18) . 4. Para hallar TODAS las soluciones, observemos que el MCD 3 es primo y sólo posee los divisores 1 y 3. El conjunto de las soluciones viene expresado ⎧ 3 6 ⎫ por ⎨ x = 18 + × k , y = −18 − × k ⎬ . Se puede construir una tabla g g ⎩ ⎭ g∈{1,3}, k∈ para mostrar algunas de las soluciones. • Calcular el resto de la división de 201034171 entre 2011 , explicando en qué teoremas o resultados se basa la resolución efectuada. En primer lugar, observemos que 2010 < 2011 y que 2011 es primo (para ver esto último hay que probar con los posibles divisores primos menores que 2011 = 44,84... , esto es, hasta el 43). El problema es, por tanto, una aplicación del Teorema “pequeño” de Fermat: “Si p es primo y a < p, entonces a p −1 ≡ 1 ( p) ”. Aquí el p es el 2011. Dividiendo 34171 entre 2010 (que es ahora el p − 1 ) se tiene: 34171 = 2010 × 17 + 1 , luego 201034171 = 20102010×17 +1 = (20102010 )17 × 2010 . Pero 20102010 ≡ 1(2011) de acuerdo con el Teorema de Fermat, luego el resto pedido es precisamente 2010.
Ejercicio Tercero (Conjuntos y Lógica) (3+3 puntos)
19
•
Se considera la siguiente relación entre conjuntos: ARB quiere decir A ⊂ B (inclusión estricta, esto es, no se permite que A = B ). Demostrar que es una relación irreflexiva, antisimétrica y transitiva. Desde luego es irreflexiva: Si fuera cierto que A ⊂ A , existiría algún elemento x ∈ A que también satisfaría x ∉ A , lo cual es una contradicción. Que es antisimétrica también es cierto: De A ⊂ B y B ⊂ A se deduce, por la definición de igualdad de conjuntos, que A = B . Para ver que es transitiva, consideremos un elemento arbitrario x ∈ A . Por ser A ⊂ B , se tiene que x ∈ B . Además, por ser B ⊂ C , también es x ∈ C . Como x es arbitrario, todos los elementos de A lo son de C, luego la relación es transitiva. • ¿Para qué valores de verdad de las proposiciones p, q, r resulta cierta la proposición compuesta ( p → q ) ∧ ¬r ? Resolverlo SIN construir tablas de verdad, razonando el proceso seguido. Notemos que la expresión ( p → q ) ∧ ¬r es una conjunción. Para que su valor de verdad sea 1 es necesario que ambos componentes sean verdaderos. Por tanto ¬r ha de valer 1, esto es, r tiene valor de verdad 0. La otra mitad de la conjunción, p → q , es verdad siempre, excepto si p es 1 y q es 0. Luego las posibles combinaciones de valores de verdad de ( p, q, r ) que hacen verdadera la
proposición compuesta son: {(1,1, 0), (0,1, 0), (0, 0, 0)} .
20
MÁS EJERCICIOS PRE-EXAMEN, I Número 1. Consideremos el conjunto
= {0,1, 2,3,...} . Definimos una función
F: × → de la siguiente forma: F ⎡⎣( m, n ) ⎤⎦ = m + {(a, b) a + b < m + n} . Se piden dos cosas:
Escribir F ⎡⎣( m, n ) ⎤⎦ directamente como función sólo de m y n. • Probar que esta función muestra que × es numerable. Pista: Hacer una representación gráfica de los primeros elementos de •
×
.
Número 2. Hallar una fórmula cerrada para la recurrencia siguiente: F0 = 1, F1 = 2, Fn = 4 Fn −1 − Fn − 2
Número 3. (Fácil) Escribir el MCD(98182,14028) en la forma 98182a + 14028b . Número 4. Consideremos la aritmética Z 6783 . • ¿Tienen inverso multiplicativo todos los elementos? ¿Por qué? • En caso de respuesta negativa a la pregunta anterior, calcular cuántos elementos tienen inverso multiplicativo. Número 5. En la pastelería Manolo venden sólo 4 clases de pasteles. Compramos 20. ¿Cuántas posibilidades de compra existen? Número 6. Investigar (sin escribir todo el conjunto, claro está) si en el conjunto A = {30 ,31 ,32 ,...,3100 } existen dos números cuya diferencia es múltiplo de 100. Número 7. ¿Es cierto que [( ¬p ∧ q ) → ( p ∨ ¬q )] ↔ [q → (¬q ∧ p)] ?
21
MÁS EJERCICIOS PRE-EXAMEN, II Ejercicio Primero (Combinatoria) (4 puntos). a) ¿Qué significa la expresión “partición de un número entero positivo en sumandos”? b) ¿Qué “números” se usan para contar la cantidad de particiones de un entero? ¿Siguen alguna regla para su formación? Razone su respuesta. c) Obtenga todas las particiones del número 10 en cuatro sumandos. Ejercicio Segundo (Recurrencia) (3 puntos). Llamemos Rn al número de ristras formadas por n dígitos binarios en las que no aparecen
nunca tres ceros consecutivos. Halle una regla de recurrencia para Rn . Pista: Construya una tabla para los primeros valores de n. Ejercicio Tercero (Aritmética Modular, etc) (4 puntos) ¿Cuál es la congruencia de Euler? Indique brevemente de dónde procede y en qué se basa su demostración (no es necesario dar la demostración completa) Utilice dicha congruencia para hallar el resto de dividir 1001529 entre 2010. Ejercicio Cuarto (Funciones) (3 puntos). Sean A = Z4 , B = Z9 . ¿Cuántas funciones inyectivas existen del tipo sobreyectivas? Conteste a las mismas preguntas para el caso
A→B?
¿Cuántas hay
B → A.
Ejercicio Quinto (Lógica) (3 puntos). Explique qué es una “demostración por el contrarrecíproco”. Justifique en qué principio lógico se basa la validez de esta clase de demostraciones. Ponga un ejemplo fácil.
22
