Ejercicios de Álgebra (Matemática Discreta) Propuestos durante el Curso 2011‐2012 …y casi todos resueltos
Profesor: José‐Miguel Pacheco Septiembre 2012
1
INDICE 02. Combinatoria, I 04. Combinatoria, II 06. Inducción 09. Recurrencia 13. Aritmética 17. Conjuntos, I 21. Conjuntos, II 24. Lógica, I 28. Lógica, II 29. Exámenes de 2011‐2012
2
EJERCICIOS DE COMBINATORIA, I 1. ¿Cuántas palabras de cinco letras pueden escribirse con las letras del alfabeto español? Solución: El alfabeto español consta de 26 letras. Una palabra es cualquier grupo de 5 letras, pudiendo repetirse, y además hay que tener en cuenta el orden (ojo: no es necesario que las palabras signifiquen nada). Por tanto, el número de palabras es el de VARIACIONES CON REPETICIÓN DE 26 ELEMENTOS, TOMADOS DE 5 EN 5, esto es:
.
2. Como en el ejercicio anterior, pero suponiendo que las palabras no pueden tener letras repetidas. Solución: Ahora el número de palabras será el de VARIACIONES ORDINARIAS DE 26 ELEMENTOS, TOMADOS DE 5 EN 5, esto es:
.
3. En cinco sillas en fila, ¿de cuántas maneras pueden sentarse dos personas? Solución: Aquí se trata de hacer grupos de dos posiciones, entre las cinco posibles. Teniendo en cuenta el orden, claro está ¿por qué?. El número de maneras es el de VARIACIONES ORDINARIAS DE 5 ELEMENTOS, TOMADOS DE 2 EN 2, esto es:
.
4. Un estudiante dispone de 5 libros de Álgebra, 4 de Cálculo y 5 de Matemática Discreta. Se acaba de comprar un estante y los piensa colocar en él. Se pregunta: de cuántas formas puede llevar a cabo su propósito? Solución: Este ejercicio admite varias interpretaciones, según lo que entendamos por “colocar”. La primera sería suponer que los libros se ponen revueltos unos con otros en el estante. En ese caso, como hay 12 libros en total, las posibilidades son las PERMUTACIONES DE 12 OBJETOS, . Podríamos pensar también (segunda) que los libros se mantienen esto es: agrupados por materias, sin más preocupación. Ahora se trataría sólo de permutaciones de . Todavía más, si el estudiante es tres objetos (los tres grupos de libros), esto es: cuidadoso (tercera), le gustaría colocarlos ordenadamente dentro de cada grupo. Entonces, los de Álgebra, dentro de su grupo, se pueden ordenar de 3! = 6 modos; los de Cálculo, en el suyo, de 4! = 24 formas; y los de Matemática discreta tienen 5! = 120 posibilidades. Aplicando ahora (por lo menos) dos veces el PRINCIPIO FUNDAMENTAL DE LA COMBINATORIA, tendríamos:
.
5. Se pregunta de cuántas formas distintas pueden sentarse 12 personas a intervalos regulares alrededor de una mesa redonda lo bastante grande como para acomodarlas a todas.
3
Solución: A primera vista diríamos que la solución es 12!, pues son ordenaciones (o permutaciones) de 12 elementos. Sin embargo, esta idea está equivocada: En realidad, una vez situada la primera persona, lo que determina la ordenación de todas ellas son las diversas formas de colocar a las 11 restantes en fila. Una vez ubicada la fila de personas en los 11 asientos vacantes, cosa que puede hacerse de 11! formas, queda resuelto el problema. NOTA: En clase vimos cómo se puede obtener la fórmula para hallar en general el número de las permutaciones circulares de n objetos, que es (n‐1)! 6. Dado el siguiente programa de ordenador, calcular el número de veces que ejecuta la instrucción WRITE: FOR I = 1 TO 10 DO FOR J = 16 DOWNTO 7 STEP 2 DO FOR K= 6 TO 15 DO WRITE ((I‐K)^J) Solución: La solución es, por el PRINCIPIO FUNDAMENTAL DE LA COMBINATORIA, 500 veces. En efecto: La I se puede elegir de 10 forrmas, pues varía entre 1 y 10; la J, de 5 formas, pues varía entre 7 y 16 (contando el 7) pero bajando de 16 hacia 7 saltando de 2 en 2; finalmente k puede elegirse de 10 maneras, entre 6 y 15 contando el 6. Por tanto las ternas (I, J, K) son 500, y como a cada terna le correspond llevar a cabo una instrucción WRITE, ésta se ejecuta 500 veces.
EJERCICIOS DE COMBINATORIA, II 7. En el juego del póquer cada jugador recibe cinco cartas de un total de 52 (4 palos de trece cartas cada uno). Supongamos que sólo hay un jugador. Se pregunta: a. ¿cuántas formas posibles existen de recibir cinco cartas? b. ¿cuántas formas posibles hay de obtener un full (es la abreviatura de full house, esto es, 3 cartas iguales y otras dos iguales pero diferentes a las anteriores, p. ej. 777QQ)? c. ¿de cuántas formas puede el jugador, si ya tiene un full, mejorar su juego a un póquer (cuatro cartas iguales, p. ej. 7777K ó QQQQ7)? 8. Consideremos el siguiente sumatorio: S =
8
∑
i , j , k =1
xi y j zk . Se pregunta:
a. ¿de cuántos sumandos se compone esta expresión? b. Si se supone que i ≠ j ≠ k , ¿cuántos sumandos quedan? c. ¿y si i ≤ j ≤ k ? d. ¿y si i < j < k ?
4
Solución: La cuestión a) es fácil: Hay tantos sumandos como variaciones con repetición de los 8 valores posibles de los subíndices, tomados de tres en tres, esto es: VR38 = 83 = 512. En la cuestión b) no permitimos que haya subíndices repetidos, luego son variaciones ordinarias de 8 elementos tomados de tres en tres, esto es: V38 =
8! 8! = = 336. (8 − 3)! 5!
Para la cuestión c) pensemos primero en un caso particular: elijamos p.ej. el subíndice i = 1. Para el segundo subíndice quedan 8 posibilidades: j ∈ {1, 2,3, 4,5, 6, 7,8} . Elijamos ahora un valor de este subíndice, p.ej, el 4. Ahora quedarán 5 posibilidades para el tercero:
k ∈ {4,5, 6, 7,8} . Por tanto habrá 5 ternas de subíndices asociadas a las elecciones 14, a saber: 144, 145, 146, 147 y 148. Pasemos ahora, usando la idea anterior, a efectuar el recuento (NOTA: Puede ayudar construir un diagrama “en árbol”). Elegir una i se puede hacer de 8 formas. Una vez seleccionada una, las posibilidades para j son 8‐(i‐1) = 9‐i, que van desde la i que hayamos tomado hasta 8. Para la k nos quedarán 8‐(j‐1) = 9‐j formas posibles, que van desde la j que sea hasta 8. Lo resumimos todo en una tabla y obtenemos que habrá 122 sumandos: Valor de i Posibles j Posibles k Total de ternas ijk 1
8
36
36
2
7
29
65
3
6
22
87
4
5
15
102
5
4
10
112
6
3
6
118
7
2
3
121
8
1
1
122
La cuestión d) es análoga a la c), pero con la precaución siguiente: Elegida una i, que no puede ser mayor que 6 ‐pues si no no habría ternas i
5
g. ¿cuántos de los números anteriores son impares? 10. En una excursión se reparten nueve turistas en tres vehículos A, B, C, de forma que en ninguno vayan menos de dos ni más de cuatro. Se desea saber: ¿de cuántas formas posibles pueden distribuirse? Solución: Éste es fácil. Con las condiciones del problema, sólo hay dos posibles distribuciones numéricas: La primera: 2 en un vehículo, 3 en otro y 4 en el último, la segunda: 3 en cada uno. Si no tenemos en cuenta qué personas concretas viajan en cada vehículo, la distribución 2+3+4 se puede dar de 6 = 3! maneras, luego en total hay 7 formas. Piensen en cómo sería el problema si se considera que los viajeros pueden querer elegir a sus compañeros de vehículo. 11. A una selección de personal se presentan ocho mujeres y seis hombres, pero sólo se puede contratar a cuatro y tres, respectivamente ¿Cuántas maneras hay de conseguirlo? 12. En el plano de coordenadas XY se consideran sólo los puntos con coordenadas enteras no negativas. Para ir de un punto a otro sólo se pueden dar pasos paralelos al eje X, hacia la derecha, que representaremos como 1’s, y al eje Y hacia arriba, que lo serán mediante 0’s ¿Cuántos caminos posibles hay entre el punto (2,2) y el (10,10), pasando siempre por el (6,6)? Solución: Para ir de (2,2) hacia (6,6) en las condiciones del ejercicio, hay que dar cuatro pasos hacia arriba y cuatro a la derecha, esto es, cada camino constará de cuatro ceros y cuatro unos. Así 8 pues, entre (2,2) y (6,6) hay un número de caminos igual a PR4,4 =
8! = 70. Para ir de (6,6) 4!4!
á (10,10) hay otros 70, luego APLICANDO EL PRINCIPIO FUNDAMENTAL DE LA COMBINATORIA, hay 70x70 = 4900 caminos posibles entre (2,2) y (10,10).
EJERCICIOS DE INDUCCIÓN 13. Demostrar por inducción sobre n las siguientes propiedades:
n 2 + n es siempre par i. n3 − 6n 2 + 14n es múltiplo de 3 j. Si a > 1 , entonces a n − 1 es divisible por a − 1 n(n + 1)(2n + 1) k. 12 + 22 + 32 + ... + n 2 = 6 1 − q n +1 l. 1 + q + q 2 + ... + q n = 1− q
h.
6
1 1 1 1 ⎞ ⎛ + + ... + n −1 = 2 ⎜1 − n ⎟ 2 4 2 ⎝ 2 ⎠ ⎛ 1⎞ ⎛ 1⎞ ⎛ 1⎞ 1 n. ⎜1 − ⎟ + ⎜ 1 − ⎟ + ... + ⎜ 1 − ⎟ = ⎝ 2⎠ ⎝ 3⎠ ⎝ n⎠ n
m. 1 +
2n > n3 si n ≥ 10 p. n ! > 2n si n ≥ 4
o.
q. Si a1 = 2 y an +1 = 2 −
1 n +1 , entonces an = an n
Si a1 = 2 y an +1 = 2 + an , entonces an ≤ 2
r.
s. La derivada n‐sima de x 2 e x es ( x 2 + 2nx + n(n − 1))e x Solución de algunos: c) Primer paso: Para n = 1 se tiene que a n − 1 = a − 1 es claramente divisible por a − 1 . Segundo paso (hipótesis de inducción): Supongamos que es cierto lo que se pide para k‐1. Tercer paso: Escribamos a k − 1 = a k − a k −1 + a k −1 − 1 , y agrupando términos, vemos que
a k − a k −1 + a k −1 − 1 = a k −1 (a − 1) + (a k −1 − 1) . El primer sumando del segundo miembro es claramente múltiplo de a − 1 , y el segundo también, por la hipótesis de inducción. Por tanto, a n − 1 es divisible por a − 1 para cualquier valor de n. e) Este puede demostrarse por inducción, y también sin ella. Hagámoslo primero sin inducción. Escribamos, para empezar, S n = 1 + q + q 2 + ... + q n . A continuación, multipliquemos por q esta expresión para obtener qS n = q + q 2 + ... + q n + q n +1 . Restando ambas expresiones y despejando la S n , tendremos S n =
1 − q n +1 . 1− q
Usemos ahora el método de inducción: Primer paso: Para n = 0 se tiene que S0 = 1 , y también que
1 − q 0+1 1 − q = = 1 . Luego el 1− q 1− q
resultado se comprueba para n=0. Segundo paso (hipótesis de inducción): Supongamos que es cierto lo que se pide para k‐1:
S k −1 = 1 + q + q 2 + ... + q k −1 =
1 − qk . 1− q
Tercer paso: Escribamos, S k = (1 + q + q 2 + ... + q k −1 ) + q k = S k −1 + q k y usando la hipótesis de inducción tendremos que:
1 − q k 1 − q k 1 − q k + q k − q k +1 1 − q k +1 . S k = S k −1 + q = + q = = 1− q 1− q 1− q 1− q k
7
h)
2n > n3 si n ≥ 10 . Primer paso: Para n = 10 (notemos que ahora el primer valor de n es 10, pues para valores menores puede no ser cierta la desigualdad) se tiene 210 = 1024 > 1000 = n3 . Segundo paso (hipótesis de inducción): Supongamos que es cierto lo que se pide para k‐1:
2k −1 > (k − 1)3 . Tercer paso: Escribamos 2k = 2 × 2k −1 = 2k −1 + 2k −1 , y usando dos veces la hipótesis de inducción tendremos que: 2k = 2k −1 + 2k −1 > (k − 1)3 + (k − 1)3 . Ahora nos queda hacer aparecer en el último miembro la tercera potencia de k [ésta es la parte más “imaginativa” del ejercicio]. Observemos que por ser k mayor o igual que 10, siempre es cierto que
(k − 1)3 > (k − 1) 2 y también que, por ejemplo, (k − 1)3 > 4(k − 1) 2 . Por tanto, podremos poner:
2k = 2k −1 + 2k −1 > (k − 1)3 + 4(k − 1) 2 = (k − 1)3 + 3(k − 1) 2 + (k − 1) 2 . Observamos ahora que los dos primeros sumandos del último miembro son los dos términos iniciales del desarrollo del binomio de ((k − 1) + 1)3 , así que completaremos ese desarrollo con los términos que hagan falta, restándolos después para que no cambie nada:
(k − 1)3 + 3(k − 1) 2 + 3(k − 1) + 1 + (k − 1) 2 − 3(k − 1) − 1 = ((k − 1) + 1)3 + (k − 1) 2 − 3(k − 1) − 1 = = k 3 + (k − 1) 2 − 3( k − 1) − 1 Po lo tanto, como k es mayor que 10, los términos que acompañan al cubo de k son una cantidad positiva, luego 2k = 2k −1 + 2k −1 > k 3 + (nº positivo) > k 3 . k) Si a1 = 2 y an +1 = 2 + an , entonces an ≤ 2 . Primer paso: Para n = 1 se tiene que a1 = 2 = 1, 414... < 2 . Antes de continuar escribamos algunos términos para hacernos una idea: a1 = 2, a2 = 2 + 2 , a3 = 2 + 2 + 2 ... Vemos claramente que el término n‐simo lleva n raíces. Segundo paso (hipótesis de inducción): Supongamos que es cierto lo que se pide para k‐1:
ak −1 = 2 + 2 + ... + 2 < 2 Tercer paso: Escribamos, ak = 2 + ak −1 y usando la hipótesis de inducción (y también el hecho de que la función “raíz cuadrada” es creciente) tendremos que:
ak = 2 + ak −1 < 2 + 2 = 4 = 2 . l) La derivada n‐sima de x 2 e x es ( x 2 + 2nx + n(n − 1))e x . Escribamos, como es costumbre, f ( x) = x 2 e x . Primer paso: Para n = 0 se tiene que la derivada 0‐ésima es la propia función: f (0) ( x) = x 2 e x , que satisface la fórmula dada; aún así, para asegurarnos más, calcularemos la primera
8
derivada,
f (1) ( x) = f '( x) = 2 xe x + x 2 e x = ( x 2 + 2 × 1× x + 1× (1 − 1))e x , que también la
satisface. Segundo paso (hipótesis de inducción): Supongamos que es cierto lo que se pide para k‐1:
f k −1 ( x) = ( x 2 + 2(k − 1) x + (k − 1)(k − 2))e x Tercer paso: Escribamos, f ( k ) ( x) = ( f ( k −1) ( x)) ' y usando la hipótesis de inducción tendremos :
( f k −1 ( x)) ' = [( x 2 + 2(k − 1) x + (k − 1)(k − 2))e x ]' = (derivando) = (2 x + 2(k − 1))e x + ( x 2 + 2(k − 1) x + (k − 1)(k − 2))e x = (reordenando) = ( x 2 + (2(k − 1) + 2) x + ( k − 1)(k − 2 + 2))e x = ( x 2 + 2kx + k ( k − 1))e x
EJERCICIOS DE RECURRENCIA 14. Resolver la recurrencia
Fn = 5 Fn −1 − 6 Fn − 2 F0 = 0, F1 = 1
y también ésta:
Fn = 2 Fn −1 − 2 Fn − 2 F0 = 1, F1 = 3
.
Solución: Resolvamos la primera. Notamos que es una recurrencia lineal, pues pasando todos los términos con alguna F al primer miembro nos queda una combinación lineal de los mismos:
Fn − 5 Fn −1 + 6 Fn − 2 = 0 . Ahora observamos también que el segundo miembro es 0, por lo que la recurrencia es homogénea. Por tanto, podemos resolverla suponiendo que las soluciones van a ser del tipo Fn = r n , donde r es un número todavía desconocido. Sustituyendo en la ecuación de la recurrencia obtenemos la “ecuación característica” r n − 5r n −1 + 6r n − 2 = 0 , que tras dividir por r n − 2 se reduce á r 2 − 5r + 6 = 0 . Resolviendo se obtiene que r puede valer 2 ó 3. Por tanto, hay dos soluciones posibles: Fn = 2n y Fn = 3n . Dada la linealidad de la recurrencia, la solución general es del tipo: Fn = a 2n + b3n , y determinaremos las constantes a y b usando las condiciones iniciales F0 = 0, F1 = 1 :
F0 = 0 = a 20 + b30 ⇒ a + b = 0 F1 = 1 = a 21 + b31 ⇒ 2a + 3b = 1
Luego a = −1, b = 1 . Por tanto, la solución general de la recurrencia es Fn = 3n − 2n . NOTA 1: También puede resolverse usando la función generatriz. NOTA 2: Comprobar numéricamente el resultado obtenido, construyendo algunos términos de la sucesión recurrente. Resolvamos la segunda. Todo es igual al caso anterior, hasta obtener la correspondiente ecuación característica r 2 − 2r + 2 = 0 . Las soluciones de esta ecuación son dos números complejos conjugados, 1 ± i . El hecho de que las soluciones sean complejas no plantea ninguna dificultad (además, conviene recordar que este tipo de soluciones siempre aparecen
9
en pares conjugados si los coeficientes de la ecuación son números reales). Para trabajar nos quedaremos sólo con una de ellas, p. ej. 1 + i , que nos provee la solución Fn = (1 + i ) n . NOTEMOS ahora que tanto la parte imaginaria de esta solución como la parte real son también soluciones de la recurrencia (esto puede demostrarse sin dificultad). Operemos ahora, escribiendo el complejo en forma trigonométrica:
π π ⎤ nπ nπ ⎡ + i sen ) . (1 + i ) = ⎢ 2(cos + i sen ) ⎥ = ( 2) n (cos 4 4 ⎦ 4 4 ⎣ nπ nπ Luego la solución general es de la forma Fn = a ( 2) n cos + b( 2) n sen , donde 4 4 determinaremos las constantes a y b usando las condiciones inicales F0 = 1, F1 = 3 : n
n
0π 0π + b( 2)0 sen ⇒ a =1 4 4 π π 1 1 F1 = 3 = a( 2) cos + b( 2) sen ⇒ a + b = 3 4 4 F0 = 1 = a( 2)0 cos
Luego a = 1, b = 2 . Por tanto, la solución general de la recurrencia es:
F1 = ( 2) n cos
nπ π + 2( 2) n sen . 4 4
NOTA: Comprobar numéricamente el resultado obtenido, construyendo algunos términos de la sucesión recurrente. 15. Consideramos los números de Fibonacci dados por la siguiente recurrencia:
Fn +1 = Fn + Fn −1 F1 = F2 = 1
Demostrar que 1 + F1 + F2 + ... + Fn = Fn + 2 y que F12 + F22 + ... + Fn2 = Fn Fn +1 . Solución de la primera: Es un caso claro de demostración por inducción, así que damos los pasos correspondientes: a) Comprobación para n = 1: 1 + F1 = 1 + 1 = 2 = F3 , pues por definición se tiene que
F3 = F1 + F2 = 1 + 1 = 2 . b) Hipótesis de inducción: Supongamos cierto el caso n=k‐1, esto es:
1 + F1 + F2 + ... + Fk −1 = Fk +1 . c) Conclusión. En efecto:
1 + F1 + F2 + ... + Fk = (1 + F1 + F2 + ... + Fk −1 ) + Fk = [usando la hipótesis de inducción] = Fk +1 + Fk = [por la definición de la recurrencia] = Fk + 2
10
NOTA: También puede demostrarse usando el “método de descenso”: Este procedimiento consiste en suponer cierto lo que se va a probar e ir rebajando el número de sumandos hasta llegar a una expresión de la que se sabe sin duda alguna que es cierta. En efecto:
1 + F1 + F2 + ... + Fn = Fn + 2 = [por la definición de la recurrencia] = = Fn +1 + Fn ⇒ 1 + F1 + F2 + ... + Fn −1 = Fn +1 [han desaparecido los Fn ]
Reiterando el proceso, lo cual sólo puede hacerse un número finito de veces, se llegará finalmente a la expresión, evidentemente cierta, 1+1 = 2.
16. Resolver la recurrencia
Fn = 4 Fn −1 + 2n F0 = 1
y también ésta:
Fn +1 − Fn = 2n + 3 F0 = 1
.
Solución: La primera. Nos encontramos ante una recurrencia lineal y no homogénea, debido a la presencia del término 2n. Por tanto, la solución general se compondrá de dos partes:
Fn = Fn( h ) + Fn( p ) , procedentes, respectivamente, de la recurrencia homogénea y de la parte no homogénea. Fn( p ) recibe el nombre de solución particular. a) Solución de la parte homogénea Fn = 4 Fn −1 . Usando la hipótesis Fn = r n se obtiene inmediatamente que Fn( h ) = 4n . b) Como 2n es un polinomio de primer grado en n, buscaremos una solución particular en forma de polinomio, también de primer grado: Fn( p ) = an + b . Sustituyendo esta forma en la ecuación original completa quedará: an + b = 4(a(n − 1) + b) + 2n o bien, pasándolo todo al primer miembro: n(−3a − 2) + (−3b + 4a) = 0 , lo cual nos da el siguiente sistema:
2 3 4a 8 −3b + 4a = 0 ⇒ b = =− 3 9 2 8 Luego la solución particular es: Fn( p ) = − n − , y la solución general será: 3 9 2 8 Fn = Fn( h ) + Fn( p ) = k 4n − n − 3 9 2 8 8 17 . Donde, usando la condición inicial F0 = 1 quedará F0 = 1 = k 40 − 0 − = k − ⇒ k = 3 9 9 9 17 n 2 8 4 − n − . Así pues, Fn = Fn( h ) + Fn( p ) = 9 3 9 −3a − 2 = 0 ⇒ a = −
11
La segunda. Nos encontramos también ante una recurrencia lineal y no homogénea, debido a la presencia del término 2n+3. Por tanto, la solución general se compondrá de dos partes:
Fn = Fn( h ) + Fn( p ) . Sin embargo, la ecuación característica resulta ser en este caso r = 1 , lo cual no nos permite utilizar el método del ejercicio anterior. PREGUNTA: ¿POR QUÉ? En lugar de ello, construyamos una tabla: n k 0 1 2 3 4 5 … …
Fn
1 4 9 16 25 36 …
Fn +1 − Fn 3 5 7 9
11 13 …
(k + 1) 2
…
2k + 3
…
En ella observamos inmediatamente que Fn = (n + 1) 2 , lo cual nos pide una demostración por inducción: a) Comprobación para n = 0: F0 = (0 + 1) 2 = 12 =1 . b) Hipótesis de inducción: Supongamos cierto el caso n=k, esto es: Fk = (k + 1) 2 . c) Conclusión: (k + 2) 2 = k 2 + 4k + 4 = (k 2 + 2k + 1) + (2k + 3) = Fk + (2k + 3) = Fk +1 NOTA: Observar que en la tabla de más arriba los elementos de la tercera fila son las diferencias de los que se hallan encima de ellos y forman una progresión aritmética de diferencia 2. Si repitiéramos el proceso de hallar las diferencias, tendríamos una cuarta fila toda de 2’s, y la quinta sería toda de 0’s. Por ello se dice a veces que la solución obtenida es una progresión aritmética de segundo grado. 17. Dado el alfabeto {a, b, c} , se define Fn como el número de ristras, listas o palabras de n
letras formadas con ese alfabeto que poseen exactamente dos letras b que, además, aparecen consecutivas. Hallar la relación de recurrencia correspondiente y resolverla. Solución: Construyamos una tabla para hacernos una idea del problema: n 0 1 2 3 4 5 … k
Fn 0 0 1 4 12 32 …
(k − 1) × 2k − 2
… …
Analicemos con algún detalle el caso k=5, por ejemplo. Una palabra de longitud 5 que satifsaga las condiciones del problema se compone de la pareja bb y de tres letra que pueden ser a ó c. El número de grupos formados con a’s y c’s es VR32 = 23 (= VRk2− 2 = 2k − 2 si k = 5) = 8 . Ahora bien, elegida una de la 8 variaciones, por ejemplo aca, el grupo bb puede ubicarse en cuatro
12
posiciones diferentes: *aca, a*ca, ac*a y aca*. Luego, por el Principio Fundamental de la Combinatoria: Nº de palabras de 5 letras que satisfacen las condiciones del ejercicio = (8 grupos de tres letras a, c) x (4 ubicaciones posibles) = 32. Por tanto, la tabla sugiere que Fk = (k − 1) × 2k − 2 . Para asegurarnos, es necesaria una demostración por inducción: ¡¡EJERCICIO!! Tal como está, tenemos ya la recurrencia resuelta. Podemos encontrar una fórmula recurrente simplemente restando dos términos consecutivos de la misma:
Fn − Fn −1 = (n − 1) × 2n − 2 − (n − 2) × 2n −3 = 2n −3 (2(n − 1) − (n − 2)) = n2n −3 Por tanto: Fn = Fn −1 + n 2n −3 . 18. En muchos procesos informáticos se utilizan algoritmos conocidos como “de divide y vencerás”.
El más simple de todos origina la recurrencia siguiente: Fn = 2 Fn / 2 + n, con F1 = 0. Resolverla. SUGERENCIA: Libro de Rosen, págs. 397 y siguientes. Solución: Tal como se advierte, la solución se puede leer en el texto de Rosen. Sin embargo, daremos una pista razonable: “divide y vencerás” quiere decir que para resolver un problema, se divide éste en varios subproblemas más sencillos y después se combinan las soluciones parciales obtenidas. El caso más simple corresponde a dividir el problema en dos (aunque puede hacerse en varios más, claro está), y después continuar dividiendo cada subproblema en otros dos, etc. etc. Por tanto, en este caso el índice n recorrerá las potencias de 2, esto es, 1, 2, 4, 8, 16…, así que podemos construir una tabla para hacernos una idea:
F1 = 0 F2 = 2 F1 + 2 = 2 × 0 + 2 = 2 F4 = 2 F2 + 4 = 2 × 2 + 4 = 8 F8 = 2 F4 + 8 = 2 × 8 + 8 = 24 F16 = 2 F8 + 16 = 2 × 24 + 16 = 64 … ¡¡Terminen el proceso!!
EJERCICIOS DE ARITMÉTICA 19. Dado un número cualquiera n ∈ que satisfaga n ≥ 2 , probar que en cualquier sucesión de n naturales consecutivos sólo hay uno que sea divisible por n.
13
Solución: Comenzamos haciendo tres observaciones: a) Se nos pide un resultado válido para TODOS los números naturales que sean mayores que 2. Por tanto, el MÉTODO DE INDUCCIÓN parece la forma más adecuada de proceder. b) Esta es inmediata, pero conviene señalarla: Los múltiplos de cualquier número natural n se hallan distribuidos a distancia n unos de otros en el conjunto de los naturales (p. ej. los de 2 (los pares), cada 2 números; los de 3, cada 3, etc. c) Notamos que lo que pide el ejercicio es demostrar que algo es único. Llevemos a cabo los tres pasos de la indución: 1) Comprobación para n =2: Según el ejemplo de la observación b), en cada pareja de números consecutivos hay sólo uno par. 2) Hipótesis de inducción: Supongamos cierto el caso n=k‐1, esto es, en cada sucesión de k‐1 números naturales consecutivos hay exactamente uno múltiplo de k‐1. Pasemos al caso siguiente: 3) Conclusión. Tomemos una sucesión de k naturales consecutivos, y dividámosla en dos partes: La primera la forman los primeros k‐1 números, la última, el k‐ésimo. Busquemos ahora en la sucesión un número que sea múltiplo de k. Si lo encontramos entre los k‐1 primeros, ya no hay más en la sucesión, pues el siguiente y el anterior están siempre fuera de ella, por la observación b). Si no está en la primera parte, ha de ser el que ocupa el lugar k‐ésimo, el cual también es único en la sucesión. 20. Dados tres números impares consecutivos cualesquiera y que sean ≥ 5 , probar que al menos uno de ellos es compuesto. Solución: Comenzamos haciendo algunas observaciones: a) Se nos pide un resultado válido para TODAS las ternas de números naturales impares consecutivos que sean ≥ 5 . Por tanto, el MÉTODO DE INDUCCIÓN parece la forma más adecuada de proceder. Sin embargo, no lo aplicaremos aquí. b) La condición ≥ 5 es necesaria porque hay dos ternas de números “pequeños” que son todos primos: (1,3,5) y (3,5,7). La siguiente, que es la primera de las admisibles, ya tiene uno compuesto: (5,7,9) c) Notamos que el ejercicio pide demostrar que al menos uno en cada terna es compuesto. Pero puede haber más: p. ej. en (301,303,305) son todos compuestos, pues 301=7x43, 303=3x101, y 305=5x61. La demostración se basa en la observación b) del ejercicio anterior. En efecto: Los números impares están a distancia 2 entre sí, y los múltiplos de 3, a distancia 3. En algún momento coinciden ambas sucesiones; en las condiciones del ejercicio, por primera vez es en el número 9, y después, cada seis números: 15, 21, 27, 35,… Pero en cada seis
14
números consecutivos hay tres impares, luego siempre uno de ellos es múltiplo de 3, por lo cual es compuesto. Ilustración: 6 enteros consecutivos, en negrita los impares y subrayados los múltiplos de 3: …‐20‐21‐22‐23‐24‐25‐…
⎛ p⎞ ⎝ j⎠
21. Si p es un número primo y j ∈ {1, 2,..., p − 1} , entonces p divide á ⎜ ⎟ . Solución: Comenzamos a trabajar formalmente: Por la definición de los números combinatorios tendremos:
⎛ p⎞ p! p × ( p − 1)! ( p − 1)! = =p ⎜ ⎟= j !( p − j )! ⎝ j ⎠ j !( p − j )! j !( p − j )! En principio parece haberse terminado ya, pero no es cierto: ¡Aún no hemos utilizado la condición de que p sea primo! La demostración finaliza –ahora casi sí‐ observando que el denominador de la fracción es un producto de números que son todos menores que p. Como éste es primo, ninguno de ellos lo divide. Por tanto,
⎛ p⎞ ( p − 1)! = p × (un número natural) , esto es, un múltiplo de p. ⎜ ⎟= p j !( p − j )! ⎝ j⎠ ( p − 1)! es ciertamente un NOTA 1. Para ser estrictos, también deberíamos probar que j !( p − j )! número natural. Quede como ejercicio complementario, inspirándose en la NOTA 2. NOTA 2. Presentamos un par de ilustraciones:
⎛11⎞ 11! 10 × 9 × 8 × 7 = 11× = 11× (5 × 3 × 4 × 7) ⎟= 4 × 3× 2 ⎝ 4 ⎠ 4!7!
1ª) Ejempo afirmativo, pues 11 es primo: ⎜
2ª) Ejemplo negativo, pues 8 no es primo:
⎛8⎞ 8! 8 × 7 × 6 × 5 8 6 = = × × 7 × 5 = 2 × 1× 35 = 70 que NO es múltiplo de 8. ⎜ ⎟= 4 × 3× 2 4 3× 2 ⎝ 4 ⎠ 4!4! 22. Demostrar que para cualquier n ∈ , si p es primo, se tiene que p divide á n p − n. Evidentemente, se trata de una demostración por inducción. Solución: 1) Comprobación para n =1: 1p − 1 = 1 − 1 = 0 = p × 0 es múltiplo de p. 2) Hipótesis de inducción: Supongamos cierto el caso n=k‐1, esto es , que (k − 1) p − (k − 1) es divisible por p.
15
3) Conclusión. Escribamos k p − k utilizando la igualdad k = k − 1 + 1 = (k − 1) + 1 . Nos quedará
k p − k = [ (k − 1) + 1] − [ (k − 1) + 1] p
Donde vemos que el primer término del segundo miembro es la potencia p‐ésima de un binomio. Por tanto, sustituimos su desarrollo:
⎛ p⎞ k − k = [ (k − 1) + 1] − [ (k − 1) + 1] = ∑ ⎜ ⎟(k − 1) j 1p − j − [ (k − 1) + 1] j =0 ⎝ j ⎠ p
p
p
Recordemos ahora que los términos primero y último del sumatorio son respectivamente:
⎛ p⎞ ⎛ p⎞ 0 p p 0 p ⎜ ⎟ (k − 1) 1 = 1 y ⎜ ⎟ (k − 1) 1 = (k − 1) p 0 ⎝ ⎠ ⎝ ⎠ Usando esto reordenemos los términos de la expresión para k p − k : p −1 ⎛ p⎞ k p − k = 1 + (k − 1) p + ∑ ⎜ ⎟(k − 1) j 1p − j − (k − 1) − 1 j =1 ⎝ j ⎠ p −1 ⎛ p⎞ p j p− j = ⎡⎣(k − 1) − (k − 1) ⎤⎦ + ∑ ⎜ ⎟(k − 1) 1 j =1 ⎝ j ⎠
El término entre corchetes es múltiplo de p por la hipótesis de inducción, y el sumatorio
⎛ p⎞ ⎝ j⎠
también lo es, pues es una suma de términos del tipo ⎜ ⎟ × número , pero el número combinatorio es divisible por p (por ser éste primo: ver ejercicio anterior). Luego k p − k es divisible por p. Fin de la demostración. 23. Probar que si p es primo, entonces el resto de dividir (a + b) p entre p es el mismo que deja la división de a p + b p entre p. Solución: Éste es fácil. Antes de continuar, hagamos la siguiente OBSERVACIÓN: Si m deja un resto r al dividir por p, y n un resto s, entonces m+n deja el resto r+s. En efecto: Usando el algoritmo de la división tendremos m=pxq+r y también n=pxQ+s. Sumando ambas igualdades y reordenando tendremos: (m+n)=px(q+Q)+(r+s) (PIENSEN UN MOMENTO qué pasaría si r+s>p) p −1 ⎛ p ⎞ j p− j ⎛ p⎞ p p = a + b + ∑ ⎜ ⎟a j b p − j , pero Para la demostración, escribamos (a + b) = ∑ ⎜ ⎟a b j =0 ⎝ j ⎠ j =1 ⎝ j ⎠ p
p
el último sumatorio es múltiplo de p, según el ejercicio anterior, y daría resto 0. Por tanto: Resto de dividir (a + b) p entre p = Resto de dividir a p + b p entre p.
16
24. Sean tres números a, m, n ∈
. Probar que si (a m − 1) es divisor de (a n − 1) , entonces m
es divisor de n. Solución: Éste también es fácil. Vamos a efectuar la división de (a n − 1) por (a m − 1) :
an −1 = a n − m + a n − 2 m + a n −3m + ... am −1 Esta expresión termina sólo si n es múltiplo de n, pues si n=km para algún natural k, tendremos:
a n − m + a n − 2 m + a n −3m + ... + a n − km = a n − m + a n − 2 m + a n −3m + ... + a 0 = a n − m + a n − 2 m + a n −3m + ... + 1 y la división ya no puede proseguir. NOTA: Si n no fuese múltiplo de m, acabarían apareciendo términos con exponentes negativos. 25. Si n ∈
, se llama n‐simo número de Mersenne a M n = 2n − 1 .
a) Probar que si un número de Mersenne divide a otro, el exponente del primero divide al del segundo. b) Probar también que si un número de Mersenne es primo, su exponente también lo es ¿y al revés? Solución: La primera cuestión es el ejercicio anterior cuando a = 2. La segunda se deja como ejercicio para pensar en casa. La contestación a la pregunta es NO. El número M 67 = 267 − 1 no es primo. La demostración de que no lo es se debió a E. Lucas (1876), y la obtención de una factorización fue conseguida por F. N. Cole en 1903.
EJERCICIOS DE CONJUNTOS, I 26. En el conjunto de los números naturales, excluido el 0, investigar si la relación binaria
es una relación de equivalencia, de orden parcial, de orden total… Representar lo que se diga con diagramas adecuados.
Solución:
17
Es una relación de orden parcial. En efecto: •
Se tiene que para cualquier número entero n, se cumple que nRn (propiedad reflexiva). NOTA: esta propiedad no es esencial en las relaciones de orden.
•
Además, si nRm y mRn , ello quiere decir que n divide á a m y m divide á n, lo cual sólo se cumple si ambos números son iguales (propiedad antisimétrica, esta propiedad tampoco es esencial para las relaciones de orden).
•
Si nRm y mRp , ello equivale a decir que existen dos números r y s tales que m=nr y p=ms, de donde p=ms=(nr)s=n(rs), esto es nRp , lo que equivale a decir que n es divisor de p.(propiedad transitiva).
Que la relación es de orden parcial lo ilustran ejemplos como éste: 2R12 y 2R18 , pero no es psosible decidir si 12 antecede á 18 ó viceversa. Véase la figura siguiente:
27. Se llama “diagrama de Venn” a la representación gráfica de conjuntos mediante curvas cerradas en el plano tales que entre ellas siempre hay un número finito o nulo de puntos de intersección. Construir diagramas de Venn generales (esto es, donde todas las curvas corten a todas) para n = 1, 2, 3, 4, 5. Observar que cada vez son más difíciles de dibujar. Por tanto, pensar algún procedimiento sistemático para la construcción de tales diagramas. Probar además que el número de regiones en que un diagrama de Venn para n conjuntos divide al plano es . PISTA: Usar el método de inducción. Solución: Observar las sigientes figuras:
18
Figura A Si intentamos dibujar con el mismo método el caso de 4 conjuntos, veremos que la situación puede resultar “bastante confusa” (hacerlo). Por tanto, es mejor seguir una pauta como la que se muestra en la fig.B. La demostración por inducción se deja como ejercicio:
Figura B 28.
El
producto
cartesiano
de
dos
conjuntos
A
y
B
se
denota
por
. Para tres conjuntos hay varias posibilidades: ¿Son todas iguales? ¿por qué? Solución: Se trata de tres conjuntos diferentes, lo cual prueba que el producto cartesiano de conjuntos no es asociativo. En efecto, el primero de ellos está formado por ternas (a,b,c); el segundo,
19
por pares ((a,b),c), donde el primer elemento es a su vez un par; el tercero, por pares (a,(b,c)), donde el segundo elemento es a su vez un par. 29. En el conjunto
de todos los números racionales positivos se considera la familia de
conjuntos . Se construye el nuevo conjunto Estudiar el tipo de orden de A: ¿es total? ¿es bueno? ¿por qué?
.
Solución: Consideremos la siguiente figura, donde vemos que los elementos del conjunto se hallan ordenados, de acuerdo con la forma habitual en los números reales, linealmente sobre la semirrecta real positiva: Por tanto el orden es total.
Sin embargo, este orden no es bueno, pues por ejemplo el subconjunto de A formado por todos los números que pertenecen a él y son estrictamente mayores que 2 no tiene primer elemento: Siempre hay puntos del conjunto arbitrariamente próximos á 2. NOTA: En Análisis se dice que los números 0, 1, 2, 3, 4,… son puntos de acumulación de A. 30. Establecer todas las posibles funciones inyectivas entre y . ¿Existen funciones epiyectivas (o sobreyectivas, o exhaustivas) entre esos dos conjuntos? ¿Por qué? Solución: Los conjuntos en cuestión son: Z 3 = {0,1,2} y Z 5 = {0,1,2,3,4} . Si una función f : Z3 → Z 5 es inyectiva, entonces todos los elementos f (0), f (1) y f (2) son diferentes en Z 5 . Por tanto hay tantas funciones inyectivas como subconjuntos de tres elementos distintos haya en Z 5 , teniendo
V35 =
además en cuenta
el orden en que se
eligen, o sea, hay
5! 120 = = 60 funciones inyectivas. (5 − 3)! 2
No hay funciones epiyectivas f : Z3 → Z 5 , pues si g fuese una de ellas, una vez agotados los valores g(0), g(1) y g(2) en Z 5 , habría aún dos elementos de este conjunto que deberían proceder, mediante g, de 0, 1, ó 2 en Z 3 . Pero en ese caso g NO sería una función. NOTA 1. Podríamos preguntarnos cuántas funciones (inyectivas o no) f : Z 3 → Z 5 existen en total. La solución es fácil: Como hemos visto antes, cualquier función viene determinada por tres elementos f (0), f (1) y f (2) de Z 5 . Si la función es inyectiva, son distintos entre sí, y si no lo son, seguiremos teniendo una función, aunque no inyectiva. Por tanto hay tantas funciones inyectivas como subconjuntos de tres elementos, distintos o no, haya en Z 5 , teniendo
20
además en cuenta el orden en que se eligen, o sea, hay VR35 = 53 = 125 funciones, entre las cuales sólo 60 son inyectivas. NOTA 2. En Teoría de Conjuntos es costumbre escribir el conjunto de todas las funciones de un conjunto A en otro B en la forma B A (exponenciación de conjuntos). Si los conjuntos son finitos, es válida la regla entre números cardinales B A = B un caso particular, poniendo B A = Z Z5 3 = Z 5
Z3
A
, de la cual la NOTA 1 presenta
= 53 = 125 .
EJERCICIOS DE CONJUNTOS, II 31. Encontrar, usando la Teoría de Conjuntos, el error en el siguiente razonamiento, donde supuestamente se prueba que −32 = 32 :
−32 = (−2)5 = (−2)10 /2 = ((−2)10 )1/2 = 10241 /2 = 32 Solución: El error está en que elevar a ½, esto es, extraer la raíz cuadrada, NO ES UNA FUNCIÓN. Por tanto, en 10241/2 = ±32 se ha elegido un signo (para transformar la raíz cuadrada en función) que es el equivocado. 32. Sea x ∈Z , distinto de 0. Hay varias funciones enteras asociadas a los enteros. Dibujar sus gráficas en el intervalo [‐5,5]: • • • • • •
Solución: Véase la figura siguiente (sólo para valores entre ‐2 y 2).
21
33. Sean A y B dos conjuntos cualesquiera, vacíos o no. Demostrar que se cumple y encontrar un contraejemplo en el que la inclusión sea estricta (esto es, no se cumpla la igualdad). Solución: Hay varias formas de probar esta inclusión. Elijamos una fácil, distribuida en varios casos: •
Si A ∩ B = ∅ , entonces es cierta la igualdad, pues al construir la unión P(A) ∪ P(B) , es imposible que haya subconjuntos que lo sean a la vez de A yde B, exceptuando el vacío, que sólo contaremos una vez.
•
Si A ⊆ B (o al revés), entonces todos los subconjuntos de A lo son de B (o al revés), luego se tiene la inclusión P(A) ∪ P(B) ⊆ P(A ∪ B) = P(B) (ó P(A) , claro está).
•
Si A ∩ B ≠ ∅ , es fácil ver que P(A) ∪ P(B) ⊆ P( A ∪ B) , pues en el último conjunto encontraremos todos los subconjuntos de A y los de B, además de aquellos que poseen elementos comunes con A, con B y con A ∩ B , si los hubiera.
Para ver un ejemplo de inclusión estricta, consideremos A = {1,2,3,4,5} , B = {4,5,6,7} . En este caso, A ∩ B = {4,5} ≠ ∅ . El subconjunto C = {3,4,7} ⊂ A ∪ B no es subconjunto ni de A, ni de B, ni de su intersección, pero sí de su unión (corresponde al punto tercero recién visto). 34. A veces se escribe el conjunto de todas las funciones de un conjunto A en otro B en la forma B A ⊂ P(A × B) . Por ejemplo,
es el conjunto de todas las funciones reales de una
× el de las funciones reales de dos variables reales (algunos subconjuntos variable real, y de éstos son los que se usan en el curso de análisis). Sea ahora A un conjunto cualquiera, y
B = {0,1} . Calcular para este caso el conjunto B A = {0,1} . ¿Qué se puede decir de él en A
relación al conjunto de las partes de A? Solución:
22
Sea
C ⊆ A un subconjunto cualquiera de A. Definiremos una función χC : A → {0,1} ,
asociada a él, de la forma siguiente:
⎧1 si x ∈ C ⎩0 si x ∉ C
χ C ( x) = ⎨
En otras palabras, esta función, a la que llamaremos “función característica de C”, nos informa de si un determinado elemento x pertenece (valor 1) o no (valor 0) al subconjunto C. La letra griega χ se lee “ji” (en inglés se escribe “chi” y se pronuncia “kái”). Por tanto, dar un subconjunto equivale a dar su función característica. Luego {0,1} = P(A) , A
que es costumbre escribir simplemente como 2A . NOTA: Si A es finito, recuperamos la fórmula P( A) = 2 > A . Si no lo es, la expresión 2A A
provee un conjunto cuyo cardinal infinito “es mayor” que el de A. Por ejemplo, si A = tendremos que P( ) = 2
ℵ0
ℵ0
= 2 > ℵ0 . Nadie ha conseguido probar que 2 =
,
, ni
tampoco lo contrario. La última igualdad es una forma de la “Hipótesis del Continuo”. Por tanto, existen Matemáticas en las que se acepta esta hipótesis, y otras donde no. 35. Sea A = [ x ] el conjunto de todos los polinomios en una variable x con coeficientes reales. Consideremos ahora el polinomio x 2 + 1 y definamos una relación de equivalencia en A de la siguiente forma: p(x)ℜq(x) si los restos de dividir esos polinomios entre x 2 + 1 tienen el mismo grado. Construir el conjunto cociente [ x ]/ ℜ . Fijándose bien, se darán cuenta de que
[ x ]/ ℜ es “casualmente” el conjunto
de los
números complejos. Solución: Al dividir un polinomio cualquiera de [ x ] por x 2 + 1 el resto sólo puede ser una constante (el cero es una de ellas, por supuesto) o un polinomio de grado 1, a + bx . Luego en [ x ]/ ℜ sólo hay dos clases de equivalencia:
⎧[1] = {polinomios que dan resto constante} [ x ]/ ℜ = ⎨ x x polinomios no nulos múltiplos de = [ ] { } ⎩ Por tanto, y en analogía con el caso de la Aritmética Modular, la clase de un polinomio cualquiera de primer grado será: [a + bx ] = a [1] + b [ x ] . Si usamos la notación [1] = 1, [ x ] = i ,
tendremos que [a + bx ] = a [1] + b [ x ] = a + bi .
23
EJERCICIOS DE LÓGICA, I 36. Entre el cálculo proposicional y la teoría de conjuntos existe una analogía representada en la siguiente tabla:
Cálculo de proposiciones
Álgebra de conjuntos
Proposiciones: p, q
Conjuntos: A, B
p ∨ q , disyunción
A ∪ B , unión
p ∧ q , conjunción
A ∩ B , intersección
¬p , negación
A , complementario
Contradicción
∅ , conjunto vacío
Tautología
Conjunto universal
p ⇒ q , implicación
A ⊆ B , subconjunto
Establecer cuál es el análogo de la “doble implicación” p ⇔ q , usando tablas de verdad (y sin ellas). Solución: Lo resolvemos primero sin tablas: Si p ⇒ q se corresponde con A ⊆ B , entonces p ⇐ q se corresponderá con A ⊇ B . Por tanto, la doble implicación p ⇔ q , definida como
(p ⇒ q) ∧ (p ⇐ q) y también llamada equivalencia, se corresponde con A = B , la igualdad de conjuntos. Usemos ahora una tabla de verdad: p q p ⇒ q p ⇐ q
[ (p ⇒ q) ∧ (p ⇐ q) ]=[ p ⇔ q ]
1 1
1
1
1
1 0
0
1
0
0 1
1
0
0
0 0
1
1
1
La tabla nos dice que las proposiciones p y q son equivalentes cuando tienen el mismo valor de verdad. Esta analogía se extiende también al “Álgebra de Boole”. Estudiarlo en algún texto, p. ej., el Rosen.
24
37. Usando tablas de verdad (y sin ellas), hallar los valores de verdad de p ∨ (¬q ∧ r ) y de
¬p ∨ (q ⇐ r ) . Solución: Resolvámoslo directamente y comencemos con la segunda expresión. Se trata de una conjunción, luego para que su valor de verdad sea 1 han de serlo los de ambas partes de ella. Por tanto, en el primer término será ¬p = 1 , o bien p = 0 . El segundo término es una implicación, que es cierta siempre, excepto si el antecedente es verdadero, r = 1 , y el consecuente falso, q = 0 . Podemos resumirlo en una mini‐tabla: p q r Expresión 2ª 0 1 1
1
0 1 0
1
0 0 1
0
0 0 0
1
Para la primera expresión, notamos que es preisamente la negación de la segunda, por aplicación de las Leyes de De Morgan, con lo cual acaba el ejercicio.
38. Si la expresión p(x) se transforma en una proposición al darle algún valor concreto a la variable x, entonces se dice que p(x) es un predicado. El conjunto de valores de la variable para los que la proposición correspondiente es verdadera es la extensión de predicado. Hallar la extensión de los siguientes predicados: p(x)= “el número x es primo y múltiplo de 3” q(x)= “el entero x es múltiplo de 7 y divisor de 730” r(x)=”el par x=(a,b) es solución de la ecuación diofántica 3a+2b=7” s(x)=”el ciudadano x vota al partido XYZ en las elecciones generales y al ABC en las locales” t(x)=”el número complejo x tiene módulo 1” Solución: La extensión del primer caso se reduce al conjunto {3}, pues no existen números que sean primos y múltiplos de 3 salvo él mismo. En el segundo caso, la extensión es el conjunto vacío, pues la descomposición de 730 es 2x5x73, luego no hay múltiplos de 7 entre sus divisores. Para el caso tercero, basta con resolver la ecuación diofántica propuesta (ésta sí tiene soluciones: calcularlas). En el cuarto caso, la extensión es el conjunto de aquellos ciudadanos que cambian su voto XYZ en las generales por el ABC en las locales. Finalmente, el caso quinto tiene como
{
extensión x + iy ∈
}
x 2 + y 2 = 1 .
25
39. Para los predicados valen las reglas de negación obtenidas generalizando las leyes de De Morgan para proposiciones. Obtener las negaciones de los siguientes predicados cuantificados: p(z)=”todos los zurdos escriben con la mano izquierda”
{
q(n)= “todos los conjuntos An = n +
1 n∈ ,m ∈ m
}
− {0} son no vacíos”
r(d)= “algunos daneses son rubios” s(e)= “ningún español es descendiente de esquimales” t(p)= “Nadie es perfecto” (esta es la última frase de la película de Billy Wilder Con faldas y a lo loco) Solución: Notemos, para el caso primero, que estamos ante una expresión del tipo ∀z z(i) [aquí z(i) quiere decir que el zurdo z escribe con la izquierda]. Para negar expresiones cuantificadas, se cambia el cuantificador por su negación y el predicado por la suya:
¬[∀z z(i)] = ( ¬∀z ) (¬z(i)) = ∃z ¬z(i) , que se lee: “Hay algunos zurdos que no escriben con
la izquierda”. El caso segundo consiste en negar la expresión ∀n An ≠ ∅ . El resultado sería: “Hay algunos conjuntos de esa familia que son vacíos”. En el tercer caso hemos de negar una expresión del tipo ∃d d (r ) , cuyo resultado será
¬[ ∃d d (r )] = ( ¬∃d )( ¬d (r )) = ∀d ¬d (r ) = ¡acabarlo! Para el caso cuarto, se trata de negar ∀e ¬e(esquimal) … ¡terminarlo! Caso quinto. Tras ver la película y disfrutar con ella, nótese que se puede escribir la frase en la forma “todas las personas son imperfectas”, esto es, ∀p p(i) . Su negación es “hay alguien que no es imperfecto”. 40. Demostrar el siguiente teorema por diversos métodos (directo, inducción, contrarrecíproco, contradicción…): TEOREMA: “Todo número entero no nulo que sea múltiplo de 4 es par” Solución: Método directo: Si n es múltiplo de 4, es de la forma 4xk para algún entero k. Pero 4 se descompone en la forma 2x2, luego n= 4xk =(2x2)xk = [usando la propiedad asociativa del producto de enteros] = 2x(2xk) = un número par. Demostración por el contrarrecíproco (se probará que si n no es par, no puede ser múltiplo de 4): Sea n un número no par. Ello quiere decir que no hay ningún 2 en su decomposición en primos. Por tanto, n tampoco puede ser múltiplo de 4, pues en tal caso tendría al menos dos doses en su descomposición en factores primos. Inducción: Escribamos p(k) = 4xk para k entero positivo no nulo. Los pasos del método de inducción son ahora:
26
•
Comprobación inicial: Para k=1 es evidente que p(1) = 4x1 = 2x2 es par.
•
Hipótesis de inducción: Supongamos que p(k‐1) = 4x(k‐1) es par.
•
Conclusión: Veamos que p(k) = 4xk es par. En efecto: p(k) = 4xk = 4x(k‐1+1) = 4x(k‐1) + 4 = p(k‐1)+4 = una suma de números pares, luego es también par.
Busquen otros métodos de demostración…
EJERCICIOS DE LÓGICA, II 41. Demostrando Teoremas. Por regla general, en Matemáticas y en otras Ciencias semejantes, los Teoremas son expresiones lógicas de la forma A ⇒ B , y en atención al contenido o significado de lo que se esté tratando, entenderemos que si A es verdadero, también lo será B. Cuando tal cosa ocurre, estamos ante un razonamiento válido. Los razonamientos no válidos se llaman “falacias”. Habitualmente, la expresión A es una conjunción de hipótesis o condiciones, esto es, A = A1 ∧ A2 ∧ ... ∧ An , y B es más a menudo una sola proposición, aunque no es necesario que lo sea. Por ejemplo, en Análisis Matemático tomemos el siguiente Teorema: “Si {an n ∈
} es una
sucesión acotada y monótona, entonces es convergente”. En este caso A = A1 ∧ A2 , donde
A1 es la proposición “ {an n ∈
“ {an n ∈
} es acotada”,
A2 es “ {an n ∈
} es monótona”, y B es
} es convergente”.
Existen algunas reglas de manejo de expresiones que conviene conocer. Se pide demostrar las siguientes, donde p, q y r son proposiciones. 1.
p ⇒ p ∨ q (regla de adición)
2.
p ∧ q ⇒ p (regla de sustracción)
3.
p ∧ (p ⇒ q) ⇒ q (regla conocida como modus ponendo)
4. (p ⇒ q) ∧ ¬q ⇒ ¬p (regla conocida como modus tollendo) 5.
[(p ⇒ q) ∧ (q ⇒ r )] ⇒ (p ⇒ r ) (regla conocida como silogismo hipotético)
42. Consideremos estos dos ejemplos de razonamiento para decidir si son válidos o falacias, razonando la decisión tomada: 1. “Si Pepito estudiase Informática, entonces sería simpático. Pepito no estudia Informática, luego no es simpático”.
27
2. “Si hace sol, Maruchi irá a la playa. Si va a la playa, tomará un helado (de fresa, claro está). Hoy Maruchi no ha tomado helado (de ninguna clase). Por tanto Maruchi no ha ido a la playa”.
43. Un rompecabezas lógico. Manolito es invitado a una reunión en la cual toman parte Maruchi, Pepito y Susanita. Según entra, Maruchi le dice: “nosotros tres somos unos mentirosos”; Pepito, muy ofendido, responde que “no, la única mentirosa es Maruchi”, y para rematarlo del todo, Susanita exclama: “estos dos son aquí los únicos mentirosos”. Manolito, en plena desesperación, se va de la reunión e intenta determinar si alguno de los otros tres le ha dicho la verdad ¡¡ayúdenlo!!
44. Tómese la tabla de verdad correspondiente a las operaciones que se pueden llevar a cabo con dos proposiciones p y q (la que tiene 16 columnas sin contar las dos primeras, reservadas a los valores de p y q). Comprobar los siguientes hechos: 1. Toda la tabla puede construirse usando solamente los símbolos ∨ , ¬ . 2. Toda la tabla puede construirse usando solamente los símbolos ∧ , ¬ . 3. Intenten establecer si será cierto lo mismo para un número arbitrario de proposiciones. NOTA: Las familias de símbolos lógicos
{∨ , ¬} y {∧ , ¬}
se denominan “conjuntos
funcionalmente completos de operadores (=símbolos) lógicos”. Existen también conjuntos funcionalmente completos con sólo un símbolo (véase cualquier texto). 45. Escribir tablas de verdad para las siguientes combinaciones de proposiciones y símbolos, señalando si algunas son tautologías o contradicciones: 1.
¬q ⇒ q
2.
p ∨ (q ⇒ p)
3.
p ⇒ (q ⇒ r )
4. (p ⇒ q) ⇒ (q ⇒ p) 5. ((p ⇒ q) ⇒ p) ⇒ ¬q
28
UN PAR DE EXÁMENES Instrucciones generales para los exámenes. 1. En todos los ejercicios ha de EXPLICARSE CON DETALLE el proceso seguido. Se calificará con 0 (cero) 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.
EXAMEN DE 30.01.2012 (Máximo: 18 puntos) Ejercicio Primero (Combinatoria y Recurrencia, 3+3 puntos). • •
Definir “variaciones (con y sin repetición) de n elementos tomados de k en k”. En cierto país se matriculan los automóviles con placas del tipo “2 letras +3 números +2 letras” ¿cuántos vehículos pueden numerarse? (usar alfabeto latino de 26 letras). Definir “relación de recurrencia”. Definir “relación lineal de recurrencia”. ¿Es lineal la recurrencia an +3 = 3an + 2 + an +1 − 3an ? Resolverla con las condiciones iniciales a1 = 1 ,
a2 = 1 , a3 = 1 . (Pista: una raíz de la ecuación característica es 1) Ejercicio Segundo (Aritmética Entera y Modular) (3+3 puntos). •
•
El millonario Dolarín acaba de fallecer sin que se sepa muy bien quiénes son sus herederos. En principio aparecen 7 y el notario ve que repartiendo a partes iguales los millones, sin fraccionarlos, sobrarían 4 para una ONG, pero más adelante (antes de repartir nada) se hallan a otros cuatro herederos, con lo que ONG se llevaría 6. Mientras tanto se encuentran dos herederos más, y la ONG se queda con 5 millones ¿A cuánto asciende, como mínimo, la herencia? Definir la “función de Euler ϕ (m) , siendo m ∈ ”. Escribir el enunciado del
“Teorema de Euler”. Utilizar tal teorema para calcular el resto de dividir 21992 entre 17. Comentar. Ejercicio Tercero (Conjuntos y Lógica) (3+3 puntos) •
•
Definir “relación sobre un conjunto” y “relación transitiva”. Sobre el conjunto Z × Z se define una relación: (a, b) R (c, d ) cuando ad = bc . ¿Es reflexiva y simétrica? ¿y transitiva? Elija uno de estos dos: o Traducir a lenguaje lógico el siguiente razonamiento: “A veces ocurre que el juez J no envía a los ladrones a la cárcel. El acusado A no va a la cárcel, luego es un ladrón” ¿se trata de un razonamiento válido? Explicar.
29
o
Escribir en lenguaje lógico la expresión “En el país Z nadie recicla las basuras y todo el mundo circula en automóvil privado” Construir su negación y escribirla en lenguaje ordinario.
EXAMEN DE 06.07.2012 (Máximo: 18 puntos)
Ejercicio Primero (Combinatoria y Recurrencia, 3+3 puntos). •
Establecer razonadamente que “el número de permutaciones con repetición, Pnn1 ,n2 ,..., n k , de n elementos distribuidos en k grupos tales que n = n1 + n2 + ... + nk ”, es
•
n! . Aplicación: En el desarrollo del trinomio (3a + 2b − c)6 , hallar el n1 !n2 !...nk !
coeficiente del término donde aparece a 2b 2 c 2 . ¿Qué se entiende por solución de una relación de recurrencia? ¿Qué se entiende por resolver la recurrencia? Para trabajar: {0,1,5,14,30,55,...} es solución de la recurrrencia lineal no homogénea
an +1 = an + n 2 . Comprobarlo aplicando el método explicado en clase para tales casos (solución general más solución particular, etc…) Ejercicio Segundo (Aritmética Entera y Modular) (3+3 puntos). • •
¿Qué es y para qué sirve el Algoritmo de Euclides de la Aritmética Entera? ¿Por qué dicho algoritmo termina siempre? ¿Qué son los “divisores de 0” en Aritmética Modular? 1. Hallar los divisores de 0 en Z12 2. Resolver en Z 5 la ecuación de segundo grado x 2 + x + 4 = 0 . ¿Por qué no
puede resolverse, en principio, en Z12 ? Ejercicio Tercero (Conjuntos y Lógica) (3+3 puntos) •
•
Definir “relación de orden total sobre un conjunto”. Sobre el conjunto N × N se da esta relación: (a, b) ≺ (c, d ) cuando a < c , pero si a = c , entonces (a, b) ≺ (a, d ) cuando b < d . Probar que es de orden total. Elija uno de estos dos: o Traducir a lenguaje lógico: “A quien la policía de tráfico encuentra conduciendo sin seguro, se le quitan dos puntos del permiso de conducir. El conductor C ha perdido dos, luego conducía sin seguro”. Este razonamiento no es válido: Explicar por qué (no vale contestar algo así como “no, porque los perdió por no llevar el cinturón puesto…”). o Escribir en lenguaje lógico la expresión “En el país E todos son aficionados al fútbol y nadie tiene doce teléfonos móviles”. Construir su negación y escribirla en lenguaje ordinario.
30
