Introduccion a la Matematica Discreta.Grado en Ingenierıa Informatica. Informatica de Computadores.

22 de Diciembre de 2014. Grupo 3.

Nombre:

Ejercicio 1 (1.5 puntos)

a) Hallar una formula explıcita para el termino general de la siguiente sucesion

u0 = 1, u1 = 4, u2 = 0un = 3un−2 + 2un−3, ∀n ≥ 3.

b) Demostrar por induccion completa que un = −2n(−1)n + 2n es solucion de la recurrencia linealhomogenea anterior.

Ejercicio 2 (1 punto)

Probar:

a) Si n ≥ 1 es impar, entonces 7n + 1 es divisible por 8.

b) Si n ≥ 1, 233n+2 − 7n + 4 no puede se multiplo de 7.

Ejercicio 3 (2 puntos) Resolver la siguiente ecuacion diofantica:

10676x + 195465y = 320123

Comprobar si tiene soluciones positivas.

Ejercicio 4 (2.5 puntos)

Dado el siguiente sistema de congruencias:

3x ≡ 1 (mod 19)2x ≡ 6 (mod 10)

Se pide:

a) Usando el teorema chino de los restos, encontrar todas las soluciones.

b) Encuentra todas las soluciones positivas. ¿Cual es la solucion positiva mas pequena?

Para codificar un mensaje se utiliza el sistema RSA con r = 2 y una clave publica (n, e).Sabiendo que n = 2729, que 2729 es primo y que la clave privada es (n, d) con d la menorsolucion positiva del sistema de congruencias anterior:

a) Averigua la clave publica

b) Descifra el siguiente mensaje: 432

Nota:

En caso de necesitar calcular el maximo comun divisor y/o la identidad de Bezout habra que hacerlo mediante el

Algoritmo Extendido de Euclides. En el ejercicio 4, usar el alfabeto {t = 00, A = 01, B = 02, C = 03, . . . , Z = 27}.

Introduccion a la Matematica Discreta.Grado en Ingenierıa Informatica. Informatica de Computadores.

3 de Febrero de 2015. Grupo 3.

Nombre:

Ejercicio 1 (2 puntos)

a) Hallar una formula explıcita para el termino general de la siguiente sucesion

u0 = 1, u1 = 1, u2 = 9un = 3un−1 − 4un−3, ∀n ≥ 3.

b) Demostrar por induccion que

2 · 2! + 3 · 3! + · · ·+ n · n! = (n + 1)!− 2, n ≥ 2

Ejercicio 2 (2 puntos) Una agencia de viajes esta organizando dos viajes, uno a Lisboa y otro a Nueva

York. El coste total (por persona) del viaje a Lisboa es de 106 euros con 76 centimos y del viaje a NuevaYork es de 1954 euros con 65 centimos tambien por persona. La agencia pretende recaudar un total de 15795euros con 77 centimos.

a) Plantea una ecuacion diofantica que resuelva el sistema.

b) Resuelvela.

c) Demuestra que la agencia se ha equivocado en los calculos.

Ejercicio 3 (2 puntos) Sean xyz = z + y · 10 + x · 102 un numero entero de tres cifras. Demostrar, usandocongruencias y la expresion decimal del numero, que:

a) El numero de seis cifras xyzxyz es divisible por 7.

b) El numero de seis cifras xyzxyz es divisible por 11.

c) El numero de seis cifras xyzxyz es divisible por 13.

d) Deducir de lo anterior que xyzxyz = 1001 · xyz.

Ejercicio 4 (2 puntos) Para codificar un mensaje se utiliza el sistema RSA con r = 2 y una clave publica

(n, e). Sabiendo que n = 2729, que 2729 es primo y que la clave privada es (n, d) con d = 17:

a) Averigua la clave publica

b) Descifra el siguiente mensaje: 689

Ejercicio 5 (2 puntos)

a) Cinco personas suben a un microbus de siete plazas, excluida la del conductor ¿de cuantas formas sepueden sentar?

b) ¿Cuantas sucesiones binarias de ceros y unos y de longitud diez contienen exactamente tres ceros?

Nota:

En caso de necesitar calcular el maximo comun divisor y/o la identidad de Bezout habra que hacerlo mediante el Algoritmo

Extendido de Euclides. En el ejercicio 4, usar el alfabeto {t = 00, A = 01, B = 02, C = 03, . . . , Z = 27}.

Introduccion a la Matematica Discreta. Grado en Ingenierıa Informatica. TecnologıasInformaticas.

12 de Septiembre de 2016. Grupos 1 y 2

Nombre: Grupo:

Ejercicio 1 (1.25 puntos)Hallar una formula explıcita para el termino general de la siguiente sucesion:

u0 = 4, u1 = 5un = un−2 + 4n, ∀n ≥ 2.

Ejercicio 2 (2.5 puntos)

Sean x, y, z numeros enteros tales que x2 + y2 = z2.

a) (0.5 puntos) Probar que cualquier entero x no divisible por 3 verifica que x2 ≡ 1 (mod 3).

b) (0.5 puntos) Usando el metodo de reduccion al absurdo y el apartado anterior, probar que al menos uno delos valores x, y o z es divisible por 3.

c) (0.5 puntos) Probar que los enteros x, y y z o son pares o hay dos impares y uno par.

d) (0.5 puntos) Probar que cualquier entero x no divisible por 5 verifica que x2 ≡ ±1 (mod 5).

e) (0.5 puntos) Usando el metodo de reduccion al absurdo y el apartado anterior, probar que al menos uno delos valores x, y o z es divisible por 5.

Ejercicio 3 (1.25 puntos)Usando el metodo de induccion, demostrar que para todo numero natural n se verifica que:

1

1 · 3+

1

3 · 5+ · · ·+ 1

(2n− 1)(2n + 1)=

n

(2n + 1)

Ejercicio 4 (2 puntos)Una empresa vende motocicletas y bicicletas electronicas. El beneficio obtenido en la venta de cada motocicleta

es de 2029 euros con 35 centimos y de cada bicicleta es de 110 euros con 84 centimos. ¿Es posible vender unacantidad de motocicletas y de bicicletas para que el beneficio obtenido sea de 3323 euros con 57 centimos? Razonala respuesta.

Ejercicio 5 (2 puntos)

Para codificar un mensaje se utiliza el sistema RSA con r = 2 y la clave publica (n, e) donde n = 20413 =137× 149 y e = 13.

a) (0.5 puntos) Probar que la clave usada es correcta.

b) (0.5 puntos) Averigua la clave privada.

c) (1 punto) Cifra el siguiente mensaje: SOLUtiliza el siguiente alfabeto:

{t = 0, E = 1, L = 2, O = 3, S = 4, T = 5, U = 6, V = 7, W = 8, X = 9}

Ejercicio 6 (1 punto)

Usando el Teorema de Fermat, encontrar un numero entero 0 ≤ a < 73 tal que a ≡ 9794 (mod 73).

Nota:

En caso de necesitar calcular el maximo comun divisor y/o la identidad de Bezout habra que hacerlo mediante el Algoritmo Extendido

de Euclides.