Todos!!!!!exmatdis

EXÁMENES RESUELTOS MATEMÁTICA DISCRETA

INFORMÁTICA SISTEMAS Y GESTIÓN DELEGACIÓN DE ALUMNOS CENTRO ASOCIADO DE BALEARES

EXÁMENES MATEMÁTICA DISCRETA

Asignatura: MATEMATICA DISCRETA Fecha: Junio 1994 - 1ª Semana Tipo examen: General PROBLEMA 1 Sean a1 = 1, a2 = 3, an = an-1 + an-2 para todo n ≥ 3. Demuéstrese que an < (7/4) para todo n que pertenece a N. n

PROBLEMA 2 Se distribuyen 37 bolas idénticas en 6 cajas de forma que cada caja tenga al menos una bola. a) ¿De cuántas formas puede realizarse esta distribución? b) Probar que al menos una caja tiene 7 bolas.

PROBLEMA 3 En el digrafo siguiente:

v1

v5

v3

v4

v2

¿Existe algún camino entre v5 y v2? Respóndase primero usando matrices de adyacencia y después sin hacer uso de tales matrices.

1

Asignatura: MATEMATICA DISCRETA Fecha: Junio 1994 - 2ª Semana Tipo examen: General PROBLEMA 1 Pruébese que para cualquier número entero n el número:

1 2 2 n ( n − 1) 12 es también un número entero.

PROBLEMA 2 En cada uno de los siguientes apartados, estúdiese cuantas permutaciones del conjunto de las letras a, c, d, e satisfacen la condición enunciada: a) La letra b está en segunda posición. b) La letra a está en primera posición y la d en la cuarta. c) La letra a está en la primera posición o la d en la cuarta. d) La letra a no está en la primera posición ni la d en la cuarta.

PROBLEMA 3 ¿El grafo de la siguiente figura es plano? Explíquese por qué.

1

b,

Asignatura: MATEMATICA DISCRETA Fecha: Septiembre 1994 Tipo examen: General PROBLEMA 1 Demuéstrese que un entero escrito en base 7 es par si y sólo si la suma de sus cifras es par.

PROBLEMA 2 Encuéntrese una fórmula para la función g(n) definida del modo siguiente: i) g(1) = 1 ii) g(n) = g(n - 1) + 2n - 1 para n > 1

PROBLEMA 3 Estudiar si son isomorfos los siguientes grafos:

b

y

d

x z

t

a

c

(Obsérvese que el cruce de las aristas bc con ad no es un vértice).

1

Asignatura: MATEMATICA DISCRETA Fecha: Septiembre 1994 - Reserva Tipo examen: General PROBLEMA 1 Resolver la ecuación diofántica:

2x + 6y + 10z = 14 (Indicación: pasar el término en z al segundo miembro).

PROBLEMA 2 ¿De cuántas formas pueden colocarse cinco mujeres y cinco hombres alrededor de una mesa circular si se quiere que no haya dos personas del mismo sexo contiguas?

PROBLEMA 3 Estúdiese si el siguiente grafo es plano:

1

Asignatura: MATEMATICA DISCRETA Fecha: Junio 1995 - 1ª Semana Tipo examen: B 1.- Cuántos números de cinco cifras se pueden escribir con cuatro doses y cuatro cincos: a) 30 b) 50 c) 36

2.- Sean a y b números naturales con an | bn , entonces: n

a) b | a b) a | b siempre c) a | b dependiendo de los valores de n

3.- Dado el grafo de la figura:

a) Es hamiltoniano b) Es euleriano c) Es bipartito

4.- Cuál es el tamaño mínimo de una población para que exista al menos un día al año (de 365 días) donde coincidan la fecha del aniversario de nacimiento de al menos nueve personas: a) 2921 b) 2633 c) 3025

5.- Sea n el número cuyas cifras de izquierda a derecha son un "1", dos "2", tres "3", …, nueve "9". ¿Cuál es el múltiplo de 11 más próximo a n = 122333…999999999?: a) n + 6 b) el propio n c) n + 3

6.- Sea G un grafo conexo cuyos vértices son {v1, v2, v3, v4, v5}, la sucesión (v1, v2, v3, v5, v1) es: a) Un camino euleriano b) Un ciclo hamiltoniano c) Ninguno de los anteriores

1

7.- Un estudiante compra un total de 5 libros de dos series distintas A y B pagando un total de 5700 ptas. sabiendo que el precio de cada libro de la serie A es 900 ptas. más que el precio de cada libro de la otra, ¿cuál de la siguientes cantidades pagó por todos los libros de la serie A?: a) 4500 ptas. b) 3800 ptas. c) 4200 ptas.

8.- Una solución de la relación recurrente: h(n) = -3h(n - 1) - 2h(n - 2) con h(1) = 1, h(2) = 1 es: n

n

a) 3 - 2 - 4(n - 1) n n b) -3(-1) + (-2) n n c) -2(-1) + (-3)

9.- Sea M un mapa cuyas regiones se pueden colorear con sólo dos colores: a) El pseudomultigrafo dual es bipartito b) Todas las caras son polígonos con un número par de lados. c) No existen tales mapas.

10.- ¿Cuál es el coeficiente de x6 en el producto (1 - x + x3) (3 + 2x)6 : a) 5256 b) 3808 c) 5253

2

Asignatura: MATEMATICA DISCRETA Fecha: Junio 1995 - 2ª Semana Tipo examen: D 1.- La matriz de adyacencia del grafo G es: ⎡1 ⎢1 ⎢ ⎢1 ⎢ ⎣0

1 1 0⎤ 1 0 1⎥ ⎥ 0 1 1⎥ ⎥ 1 1 1⎦

entonces: a) G es un pseudografo b) G es un grafo completo c) G no es conexo

2.- Sea A la matriz de adyacencia de un multigrafo G con vértices {v1, …, vn} y sea a23 = 3 una de las entradas de A. Entonces: a) Existe un camino con tres vértices entre v2 y v3 b) Hay tres aristas con extremos los vértices v2 y v3 c) Hay tres vértices adyacentes con v2 y v3

3.- Una organización estudiantil tiene que elegir un delegado y un subdelegado. Hay 7 candidatos, ¿cuántas combinaciones se pueden hacer con los candidatos para realizar la selección?: a) 21 b) 49 c) 42

4.- Sea G un grafo con 7 vértices y C = (v1, v3, v2, v4, v5, v7, v6, v1) un camino en G: a) C es un camino euleriano b) C es un ciclo hamiltoniano c) C no está bien definido

5.- Una solución de la relación recurrente: g(n) = 6g(n - 1) - 11g(n - 2) + 6g(n - 3) con g(1) = 1, g(2) = 6 y g(3) = 20 es: n-1

n-1

a) -2 + 2 · 3 + 2 n n b) -1 + 2 · 3 + 2 n n-1 c) 4 + 3 + 3 · 2

6.- Un grupo de tres chicos y dos chicas son colocados al azar en una mesa circular. Si a es el número de colocaciones diferentes en las que se sientan dos chicas juntas y b es el número de colocaciones diferentes en las que no se sientan dos chicas juntas (dos colocaciones serán iguales si una puede ser obtenida de la otra mediante una rotación apropiada), entonces: a) a = 12 y b = 12 b) a = 14 y b = 12 c) a = 15 y b = 10

1

7.- La solución general del sistema de congruencias: x + 3y ≡ 0 mod (11) 3x + 2y ≡ 1 mod (11) es: a) x = 5 + 11k, y = 3 + 11k' b) x = 2 + 11k, y = 3 + 11k' c) x = 2 + 11k, y = 5 + 11k'

8.- ¿Cuál es el número de colocaciones diferentes de 7 libros en una estantería de modo que tres libros determinados estén siempre separados entre sí?: a) 1520 b) 1634 c) 1440

9.- Dados los números escritos en base 5: 433 y 424 su suma (en base 5) es: a) 1122 b) 1012 c) 1412

10.- Los números de la forma 2k + 1 con k natural múltiplo de 3 son: a) Siempre primos b) Siempre compuestos c) Son primos o compuestos dependiendo de k

2

Asignatura: MATEMATICA DISCRETA Fecha: Septiembre - 1995 Tipo examen: A 1.- Dado el digrafo etiquetado: x 1

2 1

1

3

1 7

2

2

2 y

¿Cuál es la distancia entre x e y? a) ∞ b) 5 c) 12

2.- Cuál es el número de soluciones enteras no negativas de la ecuación: x1 + x2 + x3 + x4 + x5 = 30 a) 60211 b) 46376 c) 48520

3.- Un número entero escrito en base 7 es par si y sólo si: a) La suma de sus cifras es par b) La suma de sus cifras es múltiplo de 4 c) La suma de sus cifras es múltiplo de 3

4.- En una carrera de maratón intervienen 4 españoles, 4 italianos, 4 ingleses y 4 franceses. Supuesto que terminan la carrera todos los corredores, cúantos podios distintos pueden darse al acabar la carrera en los cuales no hay españoles: a) 1348 b) 1320 c) 1570

5.- Dadas las matrices de adyacencia A, B y C de tres grafos: ⎡0 ⎢1 A= ⎢ ⎢0 ⎢ ⎣0

1 0 1 1

0 1 0 1

0⎤ 1⎥ ⎥ 1⎥ ⎥ 0⎦

⎡0 ⎢1 B=⎢ ⎢1 ⎢ ⎣1

1 0 0 0

1 0 0 1

1⎤ 0⎥ ⎥ 1⎥ ⎥ 0⎦

⎡0 ⎢1 C=⎢ ⎢1 ⎢ ⎣1

a) A y B son isomorfos b) A y C son isomorfos c) B y C son isomorfos

1

1 0 1 1

1 1 0 1

1⎤ 1⎥ ⎥ 1⎥ ⎥ 0⎦

6.- ¿Cuántas permutaciones del conjunto de números 1, 2, 3, 4, 5 y 6 satisfacen la condición: el 1 está en primera posición y el 4 en la tercera?: a) 23 b) 24 c) 26

7.- ¿Cuál de los siguientes grafos no se puede dibujar sin levantar el lápiz del papel y sin dibujar dos veces la misma arista?: a)

b)

c)

8.- Supongamos que hemos comprobado que 7307 no es divisible por ningún número primo p, con p ≤ q. ¿Cuál es el mínimo valor de q para el que podemos asegurar que 7307 es primo?: a) q = 47 b) q = 3659 c) q = 83

9.- Utilizando las propiedades de los números combinatorios se pueden establecer que una de las siguientes igualdades es cierta. ¿Cuál es?: ⎛ n⎞ ⎝ k⎠

2

⎛ n⎞ ⎝ k⎠

2

⎛ n − 1⎞ ⎟ con 0 ≤ k < n ⎝ k ⎠

a) n( n − k ) ⎜ ⎟ = n ⎜

⎛ n − 1⎞ ⎟ con 0 ≤ k < n ⎝ k ⎠

b) n( n − 1) ⎜ ⎟ = n ⎜

c)

⎛ n − 1⎞ ⎛ n⎞ n⎜ ⎟ = n 2 ⎜ ⎟ con 0 ≤ k < n ⎝ k ⎠ ⎝ k⎠

10.- Si m ≡ n mod ( r ) y m ≡ n mod ( s ) entonces: a) b) c)

m2 ≡ n2 mod ( r ) m ≡ n mod ( r · s ) m ≡ n mod ( r + s )

2

Asignatura: MATEMATICA DISCRETA Fecha: Junio 1996 - 1ª Semana Tipo examen: C 1.- Con las cifras 0, 1, …, 8 se forman números de cinco cifras. ¿Cuántos números diferentes pueden formarse sin repetir cifras?: a) 15120 b) 13144 c) 12882

2.- Sea G un grafo y M un mapa con #R regiones que representa a G. Supongamos que el grado de todos los vértices de G es 4 y que G tiene 14 aristas. ¿Cuál de las siguientes afirmaciones es cierta?: a) #R = 9 b) #R = 12 c) #R = 10

3.- ¿Cuántas sucesiones de n dígitos se pueden formar con los elementos del conjunto {0, 1, 2}, que posean al menos un "0", un "1" y un "2"?: n

a) 3 n n b) 3 - 3 · 2 + 3 n n c) 3 - 2 + 1

4.- Sea el mapa M de la figura:

a) M se puede colorear con tres colores diferentes b) M necesita más de tres colores para ser coloreado c) Son necesarios más de cuatro colores para colorear M

5.- Si para todo primo p ≤ 4√n se tiene que p no es divisor de n entonces: a) n es primo o producto de dos o cuatro primos b) n es primo o producto de dos o tres primos c) n es siempre primo

6.- Sea E un alfabeto con 5 vocales y 21 consonantes. ¿Cuántas palabras de 5 letras pueden formarse con las letras de E, tales que la primera y la última letras sean vocales distintas y las otras tres sean consonantes distintas?:

26! 3!• 2! 5 21 b) 2 · 3 c) V(5, 2) · V(21, 3) a)

1

7.- Sea un número primo siguientes: a) b) c)

m > 3. Entonces m siempre se puede escribir de una de las tres formas

6n + 1, 6n + 3 ó 6n + 5 6n + 1, 6n + 2 ó 6n + 3 6n + 1, 6n + 4 ó 6n + 5

8.- ¿Cuál es el número de divisores de 600 (incluyendo el 1 y el 600)?: a) b) c)

6 30 24

9.- El resto de la división de 11434292 por 5 es: a) b) c)

1 2 3

10.- Los dos grafos de la figura:

a) Son isomorfos pues tienen el mismo número de vértices y de aristas b) Son isomorfos porque se puede establecer un isomorfismo entre ellos c) No son isomorfos pues en uno hay dos vértices de grado 2 y en el otro hay tres vértices de grado 2 Solución: 1 A. 2 A. 3 . 4 B. 5 . 6 C. 7

. 8 C. 9 A. 10 C.

2

Asignatura: MATEMATICA DISCRETA Fecha: Junio 1996 - 2ª Semana Tipo examen: D 1.- Los grafos de la figura, ¿son isomorfos?:

a) No, porque uno es plano y el otro no b) Sí, pues existe un isomorfismo entre ellos c) Sí, porque tienen el mismo número de vértices y aristas

2.- ¿Cuál es el coeficiente de x12x3x43x5 en el desarrollo de (x1 + x2 + x3 + x4 + x5)7 ?: a) 420 b) 7! c) C(7, 2) · C(7, 3)

3.- ¿Cuántas soluciones en números naturales tiene la ecuación x2 - y2 = 460?: a) Una única solución b) Exactamente dos soluciones c) Más de dos soluciones

4.- El resto de la división de 13 + 23 + 33 + … + 8003 por 8 es: a) 1 b) 0 c) 3

5.- Para ir de la ciudad A a la ciudad D hay que pasar por las ciudades B y C a través de las carreteras que se indican en la figura: A

D B

C

El número de posibles recorridos distintos es: a) 10 b) C(10, 2) · C(10, 5) · C(10, 3) c) 30

6.- La suma de los cuadrados de dos enteros impares: a) Puede ser impar b) Es el cuadrado de un número c) No puede ser el cuadrado de un número

1

7.- Dado el grafo G con matriz de adyacencia: ⎡0 ⎢1 ⎢ ⎢1 ⎢ ⎢0 ⎢⎣1

1 1 0 1⎤ 0 1 0 0⎥ ⎥ 1 0 1 1⎥ ⎥ 0 1 0 1⎥ 0 1 1 0⎥⎦

a) G tiene un camino euleriano b) G no es conexo c) G tiene un vértice de grado 5

8.- En el grafo de la figura sea L( vi ) la longitud del camino más corto entre los vértices u y vi : u

6

v4 2

3

1

2

1

1

2

1 v3

v1 1

v2 3

Entonces: a) L(v4) = 6 y L(v2) = 2 b) L(v3) = 4 y L(v4) = 6 c) L(v3) = 3 y L(v4) = 5

9.- El sistema de ecuaciones:

2x + 5y ≡ 3 mod (9) 5x + 6y ≡ 2 mod (9)

tiene las siguientes soluciones mod (9): a) 1 b) 2 c) 3

10.- La solución de la ecuación recurrente:

un+2 - 5un+1 + 6un = 0 (n ≥ 0) con las condiciones iniciales u0 = 0, u1 = 1, es: 3

2

a) n - n n n b) 3 - 2 n+1 c) (-1) ·n

2

Asignatura: MATEMATICA DISCRETA Fecha: Septiembre 1996 Tipo examen: F 1.- ¿Cuántas permutaciones del conjunto de números {1, 2, 3, 4, 6, 9} satisfacen la condición de que en la primera posición y en la última haya un múltiplo de 3: a) 360 b) 24 c) 144

2.- Dado un grafo con matriz de adyacencia: ⎡0 ⎢1 ⎢ ⎢0 ⎢ ⎢1 ⎢⎣1

1 0 1 0 0

0 1 0 1 1

1 0 1 0 1

1⎤ 0⎥ ⎥ 1⎥ ⎥ 1⎥ 0⎥⎦

a) El grafo es euleriano b) El grafo es conexo c) Es un multigrafo

3.- Mediante el algoritmo de Euclides dígase cuál es el m.c.d. de los números 15141 y 5439: a) 147 b) 21 c) Ninguno de ellos

4.- Un estudiante ha estudiado 120 horas a lo largo de 14 días (se supone que cada día lo ha hecho un número entero de horas). Entonces hubo necesariamente un par de días consecutivos en los que estudió al menos un total de horas de: a) 19 b) 18 c) 20

5.- Sea Kn el grafo completo con n vértices, n par, n ≥ 3, entonces: a) Kn es hamiltoniano b) Kn es euleriano c) Kn es bipartito

6.- Sólo una de las siguientes afirmaciones es falsa: ab

a

(b-1)a

(b-2)a

a) Siempre se verifica que: 2 - 1 = (2 - 1) · (2 +2 + … + 1) n b) Si n es un número natural, 4 - 1 es siempre compuesto, n > 1 1/3 c) Sea p el más pequeño factor primo de n, donde n es compuesto. Entonces si p > n , n / p es compuesto

1

7.- Con los dígitos 1, 2, …, 5 se forman números de tres cifras. ¿Cuántos números diferentes pueden formarse, sin repetir cifras, que sean múltiplos de 3?: a) 60 b) 24 c) 20

8.- Sea M la matriz de adyacencia de un grafo con P > 1 vértices. Sea C = MP + MP-1 + … + M: a) Si C ≠ 0 entonces el grafo es conexo b) Si la entrada (i, j) de C es igual a 1 entonces existe una arista entre los vértices i y j en el grafo c) Si el grafo es conexo entonces todas las entradas de C son no nulas

9.- En una cafetería hay 4 tipos de bocadillos para comer. ¿De cuántas maneras distintas se pueden elegir 6 bocadillos de entre los 4 tipos?: a) 81 b) 87 c) 84

10.- Sea pn el n-ésimo primo, y sea: Pn = (p1 · p2 · … · pn) + 1 entonces: a) Ningún entero de la forma Pn es un cuadrado b) Todo entero de la forma Pn es un cuadrado c) Existen enteros de la forma Pn que son cuadrados y otros que no lo son

2

Asignatura: MATEMATICA DISCRETA Fecha: Junio 1997 - 1ª Semana Tipo examen: B 1.- ¿Cuál es el número de veces que se debe levantar el lápiz para dibujar la figura siguiente sin repetir ninguna arista?:

a) Ninguna. b) Una vez. c) Dos veces.

2.- Se tienen cadenas formadas por dos letras seguidas de cuatro dígitos y otras tres letras más. No están permitidas las repeticiones de letras y dígitos dentro de cada grupo, pero el último grupo de tres letras puede contener una o dos de las utilizadas al principio de la cadena. ¿Cuántas cadenas distintas se pueden formar si el número de letras disponibles es de 26?: a) 560 000 000 b) 720 100 029 c) 51 105 600 000

3.- El número de pares ordenados de enteros (x, y) tales que x2 + y2 ≤ 5 es: a) 23 b) 36 c) 21

4.- Una de las siguientes afirmaciones no es correcta: a) La suma de los cuadrados de dos enteros impares no puede ser un cuadrado. b) La suma de los cuadrados de dos enteros impares no puede ser múltiplo de 4. c) La suma de los cuadrados de dos enteros impares es múltiplo de 4.

⎧2 x + 3 y ≡ 3 mod( 8) Las soluciones enteras son de la forma x = x0 + 8k , y = ⎩ x + 4 y ≡ 7 mod( 8) y0 + 8k’ para cualquier par de enteros k y k’. Entonces:

5.- Dado el sistema: ⎨

a) 0 ≤ y0 ≤ 6 b) 0 ≤ y0 ≤ 4 c) 0 ≤ y0 ≤ 7

0 ≤ x0 ≤ 3 0 ≤ x0 ≤ 5 0 ≤ x0 ≤ 4

6.- ¿Cuántas soluciones en números enteros positivos tiene la ecuación x2 - y2 = 452?: a) Una solución. b) Dos soluciones. c) Tres soluciones. 1

7.- Sea el grafo de la figura: ⎡0 ⎢1 ⎢ ⎢0 ⎢ ⎢1 ⎢0 ⎢ ⎢1 ⎢0 ⎢ ⎢⎣1

1 0 1 0 1 0 1 0

0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0

0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0

1⎤ 0⎥ ⎥ 1⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥⎦

0 1 0 1 0 1 0 1

a) Es plano. b) No es plano. c) No es bipartito.

8.- Sea x el número tal que 59x748 es divisible por 123. Entonces: a) 0 ≤ x ≤ 3 b) 4 ≤ x ≤ 6 c) 7 ≤ x ≤ 9

a

9

b

18

28 6

s

14

10

15

9.- Dado el grafo etiquetado:

t 36

c

7

d

Se aplica el algoritmo de Dijkstra partiendo del vértice s. Se designa por δ(s,w) la distancia entre s y cualquier otro vértice w. ¿Cuál de los siguientes resultados es cierto? a) δ(s,a) = 18 δ(s,b) = 27 δ(s,c) = 15 δ(s,d) = 22 δ(s,t) = 55 b) δ(s,a) = 18 δ(s,b) = 27 δ(s,c) = 15 δ(s,d) = 22 δ(s,t) = 57 c) δ(s,a) = 18 δ(s,b) = 29 δ(s,c) = 15 δ(s,d) = 22 δ(s,t) = 57

10.- El coeficiente numérico de y6 en la expansión de (2x + y2)9 es: a) 7315 b) 3765 c) 5376

2

Asignatura: MATEMATICA DISCRETA Fecha: Septiembre 1997 Tipo examen: F 1.- Dado el producto 165432078 · 1009612 = 167022211_33736 sin efectuar la multiplicación: a) La cifra que falta es 1 b) Como el primer factor es múltiplo de 3 y el segundo no, la cifra que falta es 7 c) Como el producto ha de ser múltiplo de 8, la cifra que falta es 4

2.- ¿Cuál de las siguientes afirmaciones sobre los grafos de la figura es cierta?: A

B

C

a) B y C tienen un camino euleriano b) A es euleriano c) A tiene un camino euleriano y B un circuito euleriano

3.- ¿Cuál es la solución general del siguiente sistema de congruencias?:

3x + 4y ≡ 2 (mód 13) 2x + 6y ≡ 1 (mód 13)

a) x = 11 + 13t y = 8 + 13t' b) x = 1 + 13t y = 3 + 13t' c) x = 6 + 13t y = 9 + 13t'

4.- Un deportista ha entrenado 42 horas a lo largo de 8 días consecutivos (se supone que cada día lo ha hecho un número entero de horas). Entonces hubo necesariamente un par de días consecutivos en los que entrenó al menos un total de horas de: a) 13 b) 12 c) 11

5.- ¿Cuál es el número de colocaciones diferentes de 8 libros en una estantería de modo que 4 libros determinados estén siempre separados entre sí?: a) 2880 b) 3040 c) 3268

1

6.- Dadas las matrices de adyacencia de los grafos A, B y C: ⎡0 ⎢1 ⎢ ⎢1 ⎢ ⎣1

1 1 1⎤ 0 0 0⎥ ⎥ 0 0 1⎥ ⎥ 0 1 0⎦

⎡0 ⎢1 ⎢ ⎢1 ⎢ ⎣1

1 1 1⎤ 0 1 1⎥ ⎥ 1 0 0⎥ ⎥ 1 0 0⎦

⎡0 ⎢1 ⎢ ⎢0 ⎢ ⎣1

1 0 1⎤ 0 0 1⎥ ⎥ 0 0 1⎥ ⎥ 1 1 0⎦

a) A y B son isomorfos b) A y C son isomorfos c) B y C son isomorfos

7.- ¿Cuántas soluciones enteras no negativas tiene la ecuación x1 + x2 + x3 + x4 = 25?: a) 2024 b) 3276 c) 12650

8.-

Sea n el número 988777666655555444444333333322222222111111111. ¿Cuál de los siguientes números es múltiplo de 11?: a) n b) n - 2 c) n + 6

9.- Sea K6 el grafo completo con 6 vértices, entonces: a) Es bipartito, ya que, tiene un número par de vértices b) Es hamiltoniano c) Es euleriano

10.- Dados los números de la forma n = 2k - 1, entonces: a) n es primo si y sólo si k es primo b) si k es compuesto entonces n puede ser primo o compuesto c) si k es compuesto entonces n es necesariamente compuesto

2

02'(/2 '( (;$0(1

6HDHOJUDIRFRPSOHWR.U U! 6XPDWUL]GHDG\DFHQFLDHV D DLL  DLM L GLVWLQWRGHM  E DLL DLM L GLVWLQWRGHM  F DLL DLM L GLVWLQWRGHM 

6HDQXQQ~PHURQDWXUDOQ{PRG HQWRQFHVQHVHOFXDGUDGRGHXQQ~PHURQDWXUDO D 3DUDWRGRQLPSDU E 1XQFDFXDOTXLHUDTXHVHDQ F 6yORVLQHVLPSDUQRSULPR

¢'HFXiQWDVIRUPDVVHSXHGHQGLVSRQHUHQXQDILODODVOHWUDVDEFG[[[[[GHPRGRTXH QLQJ~QSDUGHC[ TXHGHQMXQWDV D  E  F " 6HDHOJUDIRGHODILJXUD

D (OJUDIRHVHXOHULDQR E (OJUDIRHVUHJXODU F (OJUDIRHVKDPLOWRQLDQR

6HDQXQQ~PHURQDWXUDOQ!&RQVLGHUHPRVODVXPDGHORVGRVQ~PHURVFRPELQDWRULRV &Q &Q HQWRQFHVHVWDVXPDHVHOFXDGUDGRGHXQQ~PHURQDWXUDO D &XDOTXLHUDTXHVHDQ E 6yORVLQHVSDU F &XDQGRQVHDXQFXDGUDGR ¢&XiQWDVVROXFLRQHVHQQ~PHURVHQWHURVSRVLWLYRVWLHQHODHFXDFLyQ[ \ " D 1LQJXQD E 8QD F 'RV" ¢&XiQWDVSHUPXWDFLRQHVGHORVQ~PHURVGHMDQILMRVWUHVQ~PHURV D  E  F " (OUHVWRGHODGLYLVLyQGH SRUHV D  E  F 

(QHOPDSDGHODILJXUDODVUHJLRQHVVHGHVLJQDQSRU5L 

 F HOJUDGRGHODUHJLyQ5 HV D  E  F 

 E

 D

(OFRHILFLHQWHQXPpULFRGH\ HQODH[SDQVLyQGH[\  HV D  E  F 

 F

 D

 F

 F

 D

 E

 E

02'(/2'((;$0(1 &RQVLGHUHPRVHOJUDIR*GHODILJXUD

D (OJUDIRQRHVSODQRSRUTXHGRVDULVWDVVHFRUWDQ E (OJUDIRQRHVSODQRSRUTXH WRGRYpUWLFHHVGHJUDGR F (OJUDIRHVSODQR

(OUHVWRGHODGLYLVLyQGH SRUHV D  E  F 

6HDQQ\NQ~PHURVQDWXUDOHVSRVLWLYRVFRQQ NHQWRQFHVQ N  D (VXQQ~PHURIUDFFLRQDULRFXDOTXLHUDTXHVHDN E (VXQQ~PHURHQWHURSDUDWRGRN F (VXQQ~PHURHQWHURVyORFXDQGRNHVXQQ~PHURSULPR 6HDHOJUDIRFRPSOHWR.U U! (QWRQFHV.U HVELSDUWLWR D 1RFXDOTXLHUDTXHVHDU E 6tSDUDWRGRYDORUGHU F 6yORVLUHVSDU /DVROXFLyQJHQHUDOGHOVLVWHPDGHFRQJUXHQFLDV [\{ PRG  [\{ PRG  HV D [ N\ N  E [ N\ N  F [ N\ N 

/DVROXFLyQGHODUHODFLyQGHUHFXUUHQFLDIQ  IQ VLQ!\I  HV D  Q  E  Q Q  F  Q 

¢'HFXiQWDVPDQHUDVVHSXHGHIRUPDUXQHTXLSRGHEDORQFHVWRGHMXJDGRUHVVLHQODSODQWLOOD KD\MXJDGRUHV1RVHWLHQHHQFXDQWDHOSXHVWRGHFDGDMXJDGRU D   E &  F  8QDGHODVVLJXLHQWHVDILUPDFLRQHVQRHVFRUUHFWD D /DVXPDGHORVFXDGUDGRVGHGRVHQWHURVLPSDUHVQRSXHGHVHUXQFXDGUDGR E /DVXPDGHORVFXDGUDGRVGHGRVHQWHURVLPSDUHVQRSXHGHVHUP~OWLSORGH F /DVXPDGHORVFXDGUDGRVGHGRVHQWHURVLPSDUHVHVP~OWLSORGH

¢&XiOGHHVWDVDILUPDFLRQHVHVIDOVD D 7RGRJUDIRWLHQHXQQ~PHURLPSDUGHYpUWLFHVGHJUDGRSDU E 7RGRJUDIRWLHQHXQQ~PHURSDURFHURGHYpUWLFHVGHJUDGRLPSDU F /DVXPDGHORVJUDGRVGHORVYpUWLFHVGHXQJUDIRHVSDU" (OUHVWRGHODGLYLVLyQGHSRUHV D  E  F  BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB 6ROXFLRQHV

 F

 E

 E

 D

 E

 F

 E

 F

 D

 F

02'(/2'((;$0(1 /DPDWUL]GHDG\DFHQFLDGHOJUDIR*HV

 D *HVXQSVHXGRJUDIR E *HVXQJUDIRFRPSOHWR F *QRHVFRQH[R

8QHVWXGLDQWHFRPSUDXQWRWDOGHOLEURVGHGRVVHULHVGLVWLQWDV$\%SDJDQGRXQWRWDOGH SWDVVDELHQGRTXHHOSUHFLRGHFDGDOLEURGHODVHULH$HVSWDVPiVTXHHOSUHFLRGHFDGDOLEUR GHODRWUD¢&XDOGHODVVLJXLHQWHVFDQWLGDGHVSDJySRUWRGRVORVOLEURVGHODVHULH$" D SWDV E SWDV F SWDV 8QDRUJDQL]DFLyQHVWXGLDQWLOWLHQHTXHHOHJLUXQGHOHJDGR\XQVXEGHOHJDGR+D\ FDQGLGDWRV¢&XiQWDVHOHFFLRQHVGLVWLQWDVVHSXHGHQKDFHU" D  E  F  /RVGRVJUDIRVGHODILJXUD

D 6RQLVRPRUIRVSXHVWLHQHQHOPLVPRQ~PHURGHYpUWLFHV\GHDULVWDV E 6RQLVRPRUIRVSRUTXHVHSXHGHHVWDEOHFHUXQLVRPRUILVPRHQWUHHOORV F 1RVRQLVRPRUIRVSXHVHQXQRKD\GRVYpUWLFHVGHJUDGR\HQHORWURKD\ WUHVYpUWLFHVGHJUDGR

8QHVWXGLDQWHKDHVWXGLDGRKRUDVDORODUJRGHGtDVVHVXSRQHTXHFDGDGtDORKDKHFKR XQQ~PHURHQWHURGHKRUDV (QWRQFHVKXERQHFHVDULDPHQWHXQSDUGHGtDVFRQVHFXWLYRVHQORVTXH HVWXGLyDO PHQRV D KRUDV E KRUDV F KRUDV 6HDSQ HOQpVLPRSULPR\VHD3Q S S SQ  D 1LQJ~QHQWHURGHODIRUPD3Q HVXQFXDGUDGR E 7RGRHQWHURGHODIRUPD3Q HVXQFXDGUDGR F ([LVWHQHQWHURVGHODIRUPD3Q TXHVRQFXDGUDGRV\RWURVTXHQRORVRQ 6HD.Q HOJUDIRFRPSOHWRFRQQ!YpUWLFHVQSDU D (VHXOHULDQR E (VELSDUWLWR F (VKDPLOWRQLDQR

¢&XiOHVHOQ~PHURGHFRORFDFLRQHVGLIHUHQWHVGHOLEURVHQXQDHVWDQWHUtDGHPRGRTXHWUHV OLEURVGHWHUPLQDGRVHVWpQVLHPSUHVHSDUDGRVHQWUHVt D  E  F  'DGRVORVQ~PHURVHVFULWRVHQEDVH\VXVXPDHQEDVH HV D  E  F  /RVQ~PHURVGHODIRUPDN FRQN!QDWXUDO P~OWLSORGHVRQ D 6LHPSUHSULPRV E 6LHPSUHFRPSXHVWRV F 6RQSULPRVRFRPSXHVWRVGHSHQGLHQGRGHN 6ROXFLRQHV

 D

 D

 E

 F

 E

 D

 F

 F

 D

 E

02'(/2'((;$0(1

'DGRHOVLVWHPDGHFRQJUXHQFLDV [{ PRG [\{ PRG ODVROXFLyQJHQHUDOHV D [ W\ V E [ W\ V F [ W\ V 6HDHOPDSDGHODILJXUD

7HQLHQGRWDPELpQHQFXHQWDODUHJLyQH[WHULRUSDUDFRORUHDUHOPDSDVHQHFHVLWDQ D 'RVFRORUHVE 7UHVFRORUHVF &XDWURFRORUHV 6HDS!XQQ~PHURSULPR(QWRQFHVS HVGHODIRUPDNS D &XDQGRSHVGHODIRUPDP E &XDQGRSHVGHODIRUPDP F 6LHPSUH ¢&XiOHVHOQ~PHURGHVROXFLRQHVHQWHUDVQRQHJDWLYDVGHODHFXDFLyQ [ [ [ [  D E F 

6HD*XQJUDIR\0XQPDSDFRQUUHJLRQHVTXHUHSUHVHQWDD*6LHOJUDGRGHWRGRVORVYpUWLFHV HV\*WLHQHDULVWDVHQWRQFHVUHV D E F 

¢&XiQWDVVXFHVLRQHVFRQQ HOHPHQWRVVHSXHGHQIRUPDUFRQORVVtPERORVGHOFRQMXQWR^DEF` TXHSRVHDQDOPHQRVXQDCD DOPHQRVXQDCE \DOPHQRVXQDCF \WDOHVTXHWRGDVODVCD VHDQ FRQWLJXDV\ORPLVPRODVCE \ODVCF  D Q Q  E Q  Q F Q Q 6HDQHOQ~PHURFX\DVFLIUDVGHL]TXLHUGDDGHUHFKDVRQQXHYHC RFKRC VLHWHC VHLVC  FLQFRC FXDWURC WUHVC GRVC \XQC (VGHFLUHOQ~PHURWLHQHFLIUDV\DFDEDHQ  ¢&XiOHVHOP~OWLSORGHPiVSUy[LPRDQ D (OSURSLRQE QF Q

6HD*HOJUDIRIRUPDGRSRUORVYpUWLFHV\DULVWDVGHXQWHWUDHGUR7PiVHOFHQWURGH7\ODVDULVWDV TXHXQHQGLFKRFHQWURFRQORVYpUWLFHVGH7(QWRQFHV D *HVELSDUWLWR E *HVHXOHULDQR F *QRHVKDPLOWRQLDQR (OUHVWRGHODGLYLVLyQGH SRUHV D E F 

¢&XiQWRVQ~PHURVGLVWLQWRVGHVHLVFLIUDVVHSXHGHQIRUPDUFRQFXDWURC \FXDWURC  D E F   F

 E

 F

 D

 E

 F

 E

 E

 D

 D

6ROXFLRQHV

EXAMEN septiembre 2000 1. La solución de la relación de recurrencia: f(n) = 2.f(n - 1) +1, si n > 1 y f(1) = 1, es: a) 3 n - 2, b) 2 n+2 - (n - 2), c) 2 n - 1. 2. Sea G un grafo y M un mapa con r regiones que representa a G. Supongamos que el grado de todos los vértices de G es 4 y que G tiene 14 aristas. ¿Cuál de las siguientes afirmaciones es cierta? a) r = 12. b) r = 10. c) r = 9. 3. Sea n un número natural n = 3 mod (7), entonces n es el cuadrado de un número natural: a) Para todo n impar. b) Nunca, cualquiera que sea n. c) Sólo si n es impar no primo. 4. ¿Cuántas permutaciones de los números 1, 2, ..., 5, dejan fijos dos o más números: a) 31, b) 56, c) 89? 5. El resto de la división de 13 + 23 + 33 + ... +8003 por 8 es: a) 1. b) 0. c) 3. 6. Un estudiante compra un total de 6 libros de dos series distintas A y B pagando un total de 21600 ptas. Sabiendo que el precio de cada libro de la serie A es 300 ptas. más que el precio de cada libro de la otra. ¿Cuál de las siguientes cantidades pagó por todos los libros de la serie A? a) 15500 ptas. b) 14800 ptas. c) 12400 ptas. 7. Sea G un grafo con n vértices y sea S la suma de los grados de los vértices de G. Entonces: a) S es par. b) S es impar. c) La paridad de S depende de n. 8. Sea G el grafo formado por los vértices y aristas de un cubo C más el centro de C y las aristas que unen dicho centro con los vértices de C. Entonces: a) G es euleriano. b) G es bipartito. c) G no es hamiltoniano. 9. Sea el siguiente número escrito en base 20: 43 ... 14 ... 43 (catorce "43") entonces: a) es divisible por 3 o por 7 pero no por ambos. b) es divisible por 3 y por 7. c) no es divisible ni por 3 ni por 7. 10. Sea Zn el conjunto de los restos módulo n. ¿Cuántas aplicaciones inyectivas distintas hay entre Z3 y Z8 ? a) 38 . b) 336. c) 24. Soluciones:

1

2

3

4

5

6

7

8

9

10

c

c

b

a

b

b

a

a

a

b

Solución: Es fácil contarlos. Aunque también se puede hacer por combinatoria.

MATEMÁTICA DISCRETA Junio 2.001 – 1ª semana

5. Un grafo completo puede tener

EXAMEN TIPO A 1. Los números de la forma 1 + 3 + 5+ ...+ (2n – 1) con n > 1 y natural, son a) siempre primos b) siempre compuestos,(ésta) c) primos o compuestos dependiendo de n. Solución: Solamente hay 1+3+5+7+...+(2n-1)=n2

que

ver

que

a) Es bipartito; plano.(ésta)

1 0 1 1

1 1 0 0

0⎤ 1⎥⎥ 0⎥ ⎥ 0⎦

b) No es conexo,

a) 60; b) 80 (ésta) , c) 125.

c)

Es

Solución: Si se dibuja el grafo se ve claramente que es conexo y que contiene un ciclo de grado tres por lo que no puede ser no conexo ni bipartito. Además se ve claramente que es plano. 3. El resto de la división de 77156 por 169 es a) 1(ésta) ; b) 77 , c) 168. Solución: Aplicando el Teorema de Euler (pag. 102) para el resto de 77156 por 169. Como Φ(169)=169-13=156 (número de enteros positivos que son menores o iguales que 169 y son primos con m). Según el teorema de Euler 77156 =1mod(169) por lo que el resto es 1. 4. ¿Cuántos números del conjunto { 1, 2, ..., 10000} tienen la propiedad de que la suma de sus dígitos es seis y la cifra correspondiente a las unidades es “1”? a) 166 ;

b) 83 , c) 21.(ésta)

Solución: Como debe de cumplir que Σgr(vi)=2#E para Kn será n(n-1)=2#E, o sea, n(n-1)/2= #E (nº de aristas). Probando con enteros se ve que el único de los tres que lo cumple es para n=8 que salen 28 aristas ya que para n=9 salen 36 aristas y se pasa. Por lo tanto la solución es a) 28 aristas. 6.- ¿Cuántas banderas distintas formadas por tres bandas horizontales pueden realizarse con cinco colores, si dos bandas contiguas han de ser de diferente color?

2. Sea el grafo con matriz de adyacencia ⎡0 ⎢1 ⎢ ⎢1 ⎢ ⎣0

a) 28 aristas (ésta); b) 30 aristas, c) 32 aristas.

Solución: Hagamos banderas sin que se repitan colores, esto es, Variaciones de 5 colores tomados de tres en tres, V(5, 3)= 60. Como no pueden haber dos colores iguales contiguos, fijamos dos colores en las franjas exteriores. Para cada color tendremos otros cuatro posibles colores para terminar la bandera. Repitiendo esto para los 5 colores tenemos que hay 5*4 = 20 banderas con dos colores iguales en las franjas exteriores. Esto es, la solución será 60+20= 80. También se podría haber hecho viendo que 125 = VR(5, 3) , o sea, que 125 son todas las posibles variaciones de banderas con repetición, observando que el número de banderas tiene que ser mayor que 60 y menor que 125, solo quedaba el 80. 7. El número escrito en base 15: 9 ...21 ... 9, es decir, las veintiuna cifras iguales a 9, es múltiplo de a) 7(ésta); b) 2; c) 5. Solución: Aplicando los criterios de divisibilidad, como el número es n=9.1520+9.1519+...+9.15+9. Será divisible entre k si Σi=0i=209.ri=0mod(k) donde ri son los restos de 15t entre k para 0 ≤ t ≤ 20. Para k=7 todos los restos son 1, o sea, 15t=1mod(7), para k=2 también es 1, o sea, 15t=1mod(2) y para k=5 es 150=1mod(5) y los

demos son 15t=0mod(5). Por lo tanto para que el número n sea divisible por 7 tendrá que ser Σ9.1=9*21=0mod(7), para que sea por 2 tendrá que ser Σ9.1=9*21=0mod(2) y para que sea por 5 será Σ9.r=9=0mod(5). El último no lo es por lo que no es divisible por 5. Vamos a estudiar los otros dos. Está claro que 9*21 tampoco es divisible entre dos mientras que 9*21 si que lo es. Por lo tanto la respuesta correcta es la a) 7. 8. Sea A un conjunto de cuatro elementos. Consideremos un grafo G cuyos vértices son los subconjuntos de A con dos elementos. Dos vértices están unidos por una arista si su intersección (como subconjuntos de A) es no vacía. Entonces G es a) Completo; Bipartito.

b)

Euleriano(ésta);

c)

Solución: Haciendo los subconjuntos (que salen 6 subconjuntos de dos elementos) y viendo las aristas quedaría una cosa así, siendo A={a,b,c,d}:

{a,b}

{b,c}

{a,c}

{b,d}

lo que la suma de sus cifras también, o sea: 5+X+6+7+3+2+Y+1=24+X+Y=0mod(3), o lo que es lo mismo, por ser 24 múltiplo de 3, será X+Y=0mod(3). De la otra condición sabemos que XY=0mod(7), o lo que es lo mismo 3X+Y=0mod(7), con lo que hay que resolver el sistema por congruencias: X+Y=0mod(3) 3 X+Y=0mod(7) Si Y=7 quedaría X=2mod(3) y 3x=0mod(7) y como X={0,1,2,3,4,5,6,7,8,9} por ser un número de una cifra , probando se llega a que no hay solución. Si Y=1 quedan, X=2mod(3) y 3X=6mod(7) y probando se llega a que X=2 e Y=1. Para Y=4 quedaría X=2mod(3) y 3x=3mod(7) que tampoco tiene solución. Por lo tanto la solución es la b) 1. 10. En cada cara de un cubo se trazan las diagonales. Consideremos el mapa sobre el cubo formado por las 24 regiones triangulares que aparecen. Para colorearlo son necesarios y suficientes:

{a,d}

a) Dos colores; b) Tres colores; c) Cuatro colores

{c,d}

Solución: Harán falta dos colores ya que quedaría algo así, pero no me hagáis mucho caso ya que tengo una duda, ¿se considera la región exterior?, en ese caso harían falta tres colores.

Entonces se ve que no es bipartito porque contiene un ciclo de longitud tres, por ejemplo el que va de: [{a,b},{a,c},{a,d},{a,b}] . No es completo porque de los vértices no salen aristas a todos los demás vértices., no tienen grado 5. Si acaso sería regular 4. Es Euleriano ya que contiene un camino Euleriano, por ejemplo, el borde del rectángula, el camino: [{a,b},{a,c},{a,d},{b,c},{b,d},{c.d},{a,b}]

1

2 2

1 2

1 2

2

1

1 2

9. Sea el número 5X6732Y1 del cual sabemos que es múltiplo de 33. Además el número XY formado por las cifras X e Y es múltiplo de 7. Entonces la cifra Y es a) 7; b) 1(ésta); c) 4. Solución: Como 33=3.11, para que el número sea divisible por 33 tendrá que ser divisible por 3 por

1

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Junio 2001 - Matemática Discreta 1ª semana – Modelo A Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta Primera Semana (Junio 2001) - MODELO A Ejercicio 1 Los números 1, 3, 5, ... (2n-1) son los n primeros números impares que forman una progresión aritmética de primer término 1 y de diferencia 2. La suma es: (a + a ) [1 + (2n − 1)]·n = 2n ·n = n2 y por tanto la solución es la b) Siempre Sn = 1 n ·n = 2 2 2

Sol: b)

compuestos.

Ejercicio 2 ⎡0 ⎢1 Si dibujamos el Grafo G de matriz A = ⎢ ⎢1 ⎢ ⎣0

1 1 0⎤ 0 1 1 ⎥⎥ 1 0 0⎥ ⎥ 1 0 0⎦

1

2

3

4

Se ve claramente que no es bipartito (contiene un ciclo de longitud 3), que si es conexo y

Sol: c)

que es plano. La solución es la c) Es plano

Ejercicio 3

( )

Como 169 no es primo: 169 = 132 , Φ (169) = Φ 132 = 132 − 13 = 169 − 13 = 156 , el Pequeño Teorema de Fermat dice: 77Φ (169) ≡ 1 mod (169) . En este caso 77156 ≡ 1 mod (169) Luego la solución es a) 1

Sol: a)

Ejercicio 4 Como acaban en 1, solo hay que buscar las tres primeras cifras que sumen cinco; estarían los que tiene cifras repetidas: (5,0,0), (3,1,1), (2,2,1), y los que no las tienen repetidas (4,1,0), (3,2,0); a 3! los tres primeros habría que permutarlos entre sí, P32 = = 3 , y los dos segundos también, 2! 2 P3 = 3! = 6 . En definitiva: 3 · P3 + 2 · P3 = 3 · 3 + 2 · 6 = 9 + 12 = 21 . Solucion c) 21

Sol: c) Ejercicio 5 El número de aristas de un grafo completo con n vértices K n , es Combinaciones de los n ⎛n⎞ n! n(n − 1) n(n − 1) . Si igualamos = a las posibles vértices tomados de dos en dos: ⎜ ⎟ = 2 2 ⎝ 2 ⎠ 2!(n − 2)! soluciones y pasamos el 2 multiplicando al segundo miembro, quedaría n(n − 1) = 56 , o bien n(n − 1) = 60 , o n(n − 1) = 64 . Se pueden resolver las tres ecuaciones de 2º grado, pero es más fácil ________________________________________________________________________________ Junio 2001 - Matemática Discreta 1ª semana – Modelo A Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora pensar que n(n-1) es el producto de dos números consecutivos y la única solución es 8 por 7 = 56.

Sol: a)

La solución es a) 28 aristas, y el grafo sería K8

Ejercicio 6

Habrá banderas tricolores: V5,3 = 60 , y banderas bicolores (uno en el centro y las dos franjas

de los extremos del mismo color, p.e. la bandera de España), V5,2 = 20 . En total 80 banderas. La

Sol: b)

solución es la b) 80

Ejercicio 7 Para establecer criterios de divisibilidad en base 15 hay que hacer las potencias de 15. 150 = 1 ; 151 = 15 , ... y la siguiente tabla: mód (2)

mód (5)

mód (7)

15 0 = 1 ≡

1

1

1

15 1 = 15 ≡

1

0

1

∀n 15 n ≡

1

0

1

El criterio de divisibilidad entre 5 sería que acabe en 0 o en 5, y como el número acaba en 9, no es múltiplo de 5. Los criterios de divisibilidad entre 2 (y entre 7) son que la suma de las cifras sea múltiplo de dos (o de siete) En este caso, como el número tiene 21 cifras todas nueve, la suma de las cifras será 21 por 9, que son 189, múltiplo de siete, pero no de dos. La solución es a) 7.

Sol: a) Ejercicio 8

Si A = {a, b, c, d } , los vértices corresponderían a los subconjuntos:

{a, b} , {a, c} , {a, d } , {b, c} , {b, d } , {c, d } .

Cada uno estaría conectado con todos los demás menos con él mismo (ya que es un grafo, no un pseudografo), y con su complementario sobre A. Por ejemplo, el vértice {b, d } no estaría conectado con el {a, c} . Por tanto, como hay seis vértices, cada uno está conectado con otros cuatro y el grado de cada vértice es cuatro. Todos son de grado par y el grafo será Euleriano. La solución es b) Euleriano.

Sol: a)

Ejercicio 9 Al ser 5X6732Y1 múltiplo de 33, lo ha de ser a la vez de 3 y de 11 Por ser múltiplo de tres, la suma de las cifras 5+X+6+7+3+2+Y+1 = 24 + X + Y = múltiplo •

de 3 ⇒ X + Y = 3 . Como ha de ser múltiplo de 11, la suma de las cifras que ocupan lugar par

________________________________________________________________________________ Junio 2001 - Matemática Discreta 1ª semana – Modelo A Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora Y+3++6+5 = 14+Y, menos las que ocupan lugar impar 1+2+7+X = 10+X, (14+Y) – (10+X) = 4+Y•

•

X = múltiplo de 11 ⇒ Y – X = 11− 4 . Al ser XY múltiplo de 7 ⇒ 3X + Y = 7 . Esto es: •

a) X + Y = 3 •

b) Y – X + 4 = 11 •

c) 3X + Y = 7 •

Si Y = 7, para que sea múltiplo de 3 X+Y, tendríamos XY: 27, 57, que no son 7 •

Si Y = 1, para que sea múltiplo de 3 X+Y, tendríamos XY: 21, 51, 81; 21 es 7 , pero no se cumple b) •

•

Si Y = 4, para que sea múltiplo de 3 X+Y, tendríamos: 24, 54, 84; 84 es 3 , 7 , y, además, •

4 – 8 + 4 = 0, 11 . La solución es c) 4 .

Sol: c)

Ejercicio 10 Si hacemos el desarrollo del cubo se ve enseguida que el número de colores que se necesitan es dos:

La solución es a) Dos colores

Sol: a)

Zamora, 25 de Mayo de 2.003

________________________________________________________________________________ Junio 2001 - Matemática Discreta 1ª semana – Modelo A Miguel Sobrino Morchón -4-

MATEMÁTICA DISCRETA (2001 2ª SEMANA) 1.- Sea un conjunto C con n elementos. Se sabe que C tiene 435 subconjuntos distintos de dos elementos. Entonces n es: a) 87 b) 30 c) 15 2.- El número de soluciones distintas de la ecuación 12x = 20 MÓD(21) a) una b) tres c) no tiene soluciones

a) b) c)

3.- La matriz de adyacencia de un grafo G es: no es euleriano no es plano es bipartito

01111 10111 11011 11101 11110

4.- Sea S un conjunto formado por 100 números naturales distintos. Entonces en S hay al menos K elementos que proporcionan el mismo resto al dividirlo por 21, donde K es: a) 5 b) 6 c) 10 5.- Sea G el grafo completo con r vértices. Entonces: a) G es hamiltoniano para todo r b) G es hamiltoniano solamente para r par c) G es bipartito para todo r>4 6.- El resto de la división del número m=16!.15! por 17 es: a) 1 b) 16 c) 0 7.- ¿Cuántas soluciones en números enteros tiene la ecuación x + y + z = 17 con las condiciones x>3, y>4, z>5. a) 21 b) 171 c) 17^3 8.- Sea G un grafo 3-regular con v vértices. Entonces: a) v es par b) v es impar c) la paridad de v depende del número de arista G 9.- Con las cifras {1, 2 ... 2n + 1} donde 1 < n < 4 ¿Cuántos números distintos de cinco cifras se pueden formar, de modo que la tercera y la cuarta cifra sean distintos entre sí y la primera sea par? a) 16n^5 + 24n^4 + 12n^3 + 2n b) 32n^5 + 64n^4 + 48n^3 + 16n^2 + 2n c) 2n + 5 5 10.- Sea n un número natural no divisible por 2 ni por 5. Entonces: a) n^2 – 1 es multiplo de 10 b) n^2 + 1 es multiplo de 10 c) La cifra correspondiente a las unidades del número n^2 es “1” o “9”

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Matemática Discreta 1ª semana – Modelo A Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta Primera Semana (27 de mayo de 2002) MODELO A Ejercicio 1

Si se empieza a construir una tabla de doble entrada con los elementos de A* ={1, 2,..,15} y empezamos a multiplicar y quedarnos con el resto al dividir entre 16, se encuentra pronto que 3*9=27 ≡ 11 mód (16), luego 11 no es primo, y se excluyen las opciones a) Los únicos primos en A* son 11 y 13, y la opción c) Un elemento es primo en A* si y sólo si es primo en general. Por tanto, la solución es b) no existen primos en A*.

Ejercicio 2 Un meridiano es un círculo máximo en una esfera que pasa por dos puntos diametralmente opuestos, que son los polos. Si hay 5 meridianos, de cada polo salen 10 aristas, luego los dos vértices correspondientes a los polos tienen grado par. El ecuador corta perpendicularmente al eje polar y a los meridianos, determinando 10 vértices de grado cuatro, por tanto todos de grado par. El grafo es euleriano. Sin embargo no es bipartito ya que si el polo norte lo pintamos blanco, todos los vértices del ecuador serían negros y habría vértices consecutivos del mismo color. La solución es la a) Euleriano y no bipartito.

Ejercicio 3 Designamos con D al movimiento del rey hacia la derecha, y A al movimiento del rey hacia arriba. Para ir desde la esquina inferior izquierda del tablero hasta la esquina superior derecha hay que hacer 14 movimientos, lo que supone construir una serie de 7 letras D y 7 letras A; esto es, 14! 14! 14 permutaciones de 14 donde se repiten 7 y 7: P7,7 , y la solución es la c) = 7!⋅ 7! 7!⋅ 7!

Ejercicio 4 Este problema es equivalente a buscar el menor número que dividido entre 3 de resto 2, al dividirlo entre 7 de resto 6, y al dividirlo entre p de resto 3. Si dividimos 188 entre 3, da resto 2 (188 = 62*3 + 2); al dividirlo entre 7, da resto 6 (188 = 26*7 + 6). Pero al dividirlo entre 37, o entre 5, que son las alternativas que ofrece el ejercicio, da resto 3 en ambos casos (188 = 37*5 + 3). Ahora bien, por el Corolario 1-5.21, el sistema de congruencias tiene una única solución en cada conjunto completo de residuos módulo 3*7*p; en el caso de p = 5, 3*7*p = 3*7*5=105, y 188 ≡ 83 mód (105), y 188 no sería el mínimo. Por tanto, la solución es la a) p = 37.

Ejercicio 5 El mapa se puede colorear con tres colores. Si se empieza por el centro: color 1 para el octógono interior; color 2 para las esquinas de la estrella que se puede construir sobre los lados del octógono; otra vez el color 1 para los cuadriláteros que tienen un vértice opuesto al del octógono pequeño. Los pentágonos han de colorearse con dos colores: uno puede ser el color 2, pero el otro no puede ser el 1, hay que añadir un color 3. Finalmente, para el exterior, se puede utilizar el color 1 (es más fácil hacerlo con rotuladores de colores, y sobre el dibujo del grafo) La solución es la b) 3 ________________________________________________________________________________ Matemática Discreta 1ª semana – Modelo A Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora Ejercicio 6 La diferencia de dos números es múltiplo de 17 si dan el mismo resto al dividirlos entre 17. Como los números son distintos, en el caso más desfavorable, habría 17 que darían restos 0, 1, 2, 3, ....., 15 y 16. El siguiente, el 18º ha de repetir resto. La solución es b) 18

Ejercicio 7 Como la M y la E han de ir juntas, es como si fueran una sola letra, y habría 9 letras de las que son iguales dos A, dos I y dos T. 9! 9 = ; este número hay que multiplicarlo por 2! (permutaciones ME y EM) Serían: p2,2,2 2!2!2! 9! 9 ⋅ 8 ⋅ 7! Por tanto queda: 2! = = 18 ⋅ 7! , y la solución es la c) 18 ⋅ 7! 2!2!2! 4

Ejercicio 8

Como 59 es primo que no divide a 3, 358 ≡ 1 mód (59). (Pequeño Teorema de Fermat) Por otro lado 192853 = 3325*58 +3 y 3192853 = 358*3325*33 ≡ 33 = 27. La solución es b) 27

Ejercicio 9 ⎛0 1 1 0 1⎞ ⎜ ⎟ ⎜1 0 1 0 0⎟ La matriz es: ⎜ 1 1 0 1 1 ⎟ . Si sumamos las filas salen los grados de los vértices , que ⎜ ⎟ ⎜0 0 1 0 1⎟ ⎜1 0 1 1 0⎟ ⎝ ⎠ son: 3, 2, 4, 2, 3. Hay dos vértices de grado impar. La solución es a) G tiene un camino euleriano.

Ejercicio 10

110 = 1 ≡ 1 mód (10) ; 111 = 11 ≡ 1 mód (10) ; 112 = 121 ≡ 1 mód (10) esto es: 11n ≡ 1 mód (10) para todo n. Por tanto el criterio de divisibilidad por 1º en base 11 es b) La suma de sus cifras es un múltiplo de 10. Zamora, 27 de Mayo de 2.002

________________________________________________________________________________ Matemática Discreta 1ª semana – Modelo A Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Matemática Discreta 2ª semana – Modelo B Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta Segunda Semana (10 de junio de 2002) MODELO B Ejercicio 1 Se puede hacer de dos formas: pasando los números a base 10, sumarlos y después pasarlos a base 6. 5121 = 5·63 + 1·62 + 2·6 + 1 = 5·216 + 1·36 + 2·6 + 1 = 1080 + 36 + 12 + 1 = 1129 555 = 5·62 + 5·6 + 5 = 5·36 + 5·6 + 5 = 180 + 30 + 5 = 215 Si sumamos: 1129 + 215 = 1344, y pasando a base 6 queda 10120 El otro procedimiento sería sumar en base 5: si empezamos por las unidades: 5+1 = 10, queda un 0 en las unidades y llevamos 1; 1+2+5 = 12, queda un 2 en las decenas y llevamos 1, 1+5+1 = 11, queda un 1 en las centenas y llevamos 1, 1+5 = 10, luego el número es: 10120. La solución es b) 10120

Ejercicio 2 Con solo la primera letra, hay 7 posibilidades. Luego estaría la primera letra y un símbolo, que puede ser uno de los caracteres (7 letras y 3 dígitos). esto es 10, luego sería 7·10 Después, la primera letra y dos símbolos VR(10,2) = 102. En total, 7·102 . Seguiría la primera letra y tres símbolos VR(10,3) = 103. Esto es 7·103. Y así, hasta una letra y seis símbolos: 7.106 Si sumamos todos, quedaría 7777777, y a este número le restaríamos las 32 palabras clave. Luego la solución es 7777777 – 32 = 7777745. La solución es la b) 7777745

Ejercicio 3

Si ponemos un ejemplo sencillo: x ≡ 2 mód (3) ; x ≡ 4 mód (5) ; x ≡ 6 mód (7) , se ve que la solución es la a) 3·5·7 – 1 = 104, pues 104 = 3·32 + 2 ; 104 = 5·20 + 4 ; 104 = 7·14 + 6 Las otras soluciones b) 2·4·6 = 48, al dividirlo entre 7 da de resto 0 (no 6), y la c) 104 – 15 = 89, al dividirlo entre 7 da de resto 5 (89 = 7·12 + 5) No es una forma muy ortodoxa de hacer el ejercicio, pero no se olvide que es tipo test. La solución es a) (p1*p2*....*pk) - 1

Ejercicio 4 Supongamos que hay x hojas (vértices de grado 1). El número de vértices es #V=8 + x. La suma de los grados es x·1 + 4·2 + 1·3 + 2·4 + 1·5 = x + 24. Por el Primer teorema de grafos, la suma de todos los vértices es igual al doble del número de aristas, en este caso 2·#E = 24 + x Si aplicamos la fórmula: #V = #E + 1, o bien: 2#V = 2#E + 2 ; 16 + 2x = 24 + x + 2 Y sale x = 10. La solución es a) 10

Ejercicio 5 La solución a) se excluye, pues sale 10·0,5 + 9·2 + 1·5 = 28 euros, y sólo hay 20. Si planteamos la ecuación diciendo: hay x pelotas, y yoyós, y 20 - (x+y) canicas, sale: ________________________________________________________________________________ Matemática Discreta 2ª semana – Modelo B Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora 5x + 2y + 0,5·(20-x-y) = 20 ; 10x + 4y + 20 – x – y = 40 ; 9x + 3y = 20 Como el máximo común divisor D = mcd(9,3) = 3, no divide a 20, la ecuación diofántica no tiene solución. La respuesta es b) no pudo hacer ninguna compra con esos datos.

Ejercicio 6

Como 42n = 16n, y 161 = 16 ≡ 1 mód (15) ; 162 = 256 ≡ 1 mód (15).... 16n ≡ 1 mód (15), 16 – 1 ≡ 0 mód (15) La solución es c) congruentes con 0 módulo 15. n

Ejercicio 7 Para que aparezca como máximo una letra tres veces, sería a) Que no aparezca tres veces, luego la letra central sería distinta y habría n posibilidades para la letra central y V(n-1,3) para las tres letras primeras (las tres últimas ya van colocadas por estas). Sería: n·V(n-1,3) = n·(n-1)·(n-2)·(n-3) = V(n,4) b) Que aparezca tres veces, luego la central podría ser una de las tres primeras y por tanto sería 3·V(n,3) Sumando, la solución es a) V(n,4) + 3·V(n,3).

Ejercicio 8 A la vista del grafo, hay 2n vértices de los cuales 4 son de grado 2 y 2n - 4 de grado 3. La suma de los grados es: 4·2 + 3·(2n – 4) = 8 + 6n – 12 , y ha de ser igual al doble del número de aristas; esto es 2·148 = 296. Igualando: 8 + 6n – 12 = 296 ; 6n = 300 ; n = 50 La solución es c) n = 50.

Ejercicio 9

Como 26 = 64 ≡ 1 mód (63) , y 192876= 6·32146, se tiene 2192876 = 26·32146 = (26)32146 ≡ 1 mód(63) . Luego la solución es a) 1.

Ejercicio 10 Se me ocurre hacerlo así: Tomo una matriz en la que marco primero el camino que dan: ⎛0 1 1 0 1 1⎞ ⎛0 1 1 0 1 1⎞ ⎜ ⎟ ⎜ ⎟ ⎜1 0 1 0 0 0⎟ ⎜1 0 1 1 0 1⎟ ⎜1 1 0 0 0 0⎟ ⎜1 1 0 1 1 0⎟ A=⎜ ⎟ , y ahora la completo A ' = ⎜ ⎟ ⎜ 0 0 0 0 0 0⎟ ⎜0 1 1 0 1 1⎟ ⎜1 0 0 0 0 1⎟ ⎜1 0 1 1 0 1⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎝1 0 0 0 1 0⎠ ⎝1 1 0 1 1 0⎠ añadiendo más aristas para conectar con v4, y que todos los vértices tengan grado par, en este caso 4. Convendría hacer un dibujo, primero del camino, y luego, sobre el mismo dibujo, ir añadiendo las aristas. Por tanto c) Puede ser Euleriano. Zamora, a 11 de Junio de 2.002

________________________________________________________________________________ Matemática Discreta 2ª semana – Modelo B Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Matemática Discreta - Septiembre – Modelo A Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta Septiembre (2 de septiembre de 2002) MODELO A Ejercicio 1

El coeficiente de x5 será la suma de los coeficientes de x5, que llamaremos A, el de x4, que llamaremos B, y el de x2, que llamaremos C, del desarrollo de (2+3x)5.

∑ 5

( 2 + 3x )

5

=

i =0

⎛5⎞ i 5−i ⎜ ⎟·2 ·(3 x) ⎝i⎠

⎛5⎞ ⎛ 5⎞ ⎛ 5⎞ A = ⎜ ⎟ 20 ·35 = 243 ; B = ⎜ ⎟ 21 ·34 = 5·2·81 = 810 ; C = ⎜ ⎟ 23 ·32 = 10·8·9 = 720 ⎝0⎠ ⎝1⎠ ⎝ 3⎠ Y sumando A + B + C = 243 + 810 + 720 = 1773 SOL: a)

Ejercicio 2

Se hace el cambio x2 = z, y la ecuación a resolver sería z2 – y2 = 207. Como 207 = 32·23, sus divisores son: 1, 3, 9, 23, 69 y 207, y 207 descompone en productos: 207 + 1 208 207 = 207·1 que nos da z = = = 104 que no vale, pues z = 104 no es un 2 2 número entero 69 + 3 72 69 − 3 66 207 = 69·3 que nos da z = = = 36 que da x = 6 e y = = = 33 2 2 2 2 23 + 9 32 23 − 9 14 = =7 207 = 23·9 que nos da z = = = 16 que da x = 4 e y = 2 2 2 2 Por tanto hay dos soluciones SOL: b)

Ejercicio 3 Al tener ”unos” en la diagonal principal, es un pseudografo, que tiene cuatro lazos, uno en SOL: c) cada vértice.

Ejercicio 4 Vamos a distinguir seis posiciones en la palabra: 1, 2, 3, 4, 5 y 6. En las posiciones extremas 1 y 6 han de ir vocales, luego serán VR(6,2) = 62 En las posiciones 2 y 5 han de ir consonantes (no puede haber dos vocales juntas) y son VR(20,2) = 202. En las posiciones centrales 3 y 4 pueden ir, o dos consonantes 202, o una consonante en 3 y una vocal en 4, que son 6·20, o una vocal en 3 y una consonante en 4, que son 6·20; esto es, 202 + 2·6·20 SOL: b) En total son: 62·202·(202 + 12·20) = 62·203·(20 + 12) = 62·203·32 = 62·203·25

Ejercicio 5 Para demostrar que no existe ningún grafo plano con las condiciones del ejercicio, utilizaremos el Corolario 2-4.9 (página 174 del libro de Teoría): ________________________________________________________________________________ Matemática Discreta - Septiembre – Modelo A Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora Si G = (V,E) es un grafo plano con #V ≥ 2. Entonces: #E ≤ 3#V – 6. Por el primer Teorema de grafos el número de vértices de grado impar es par, luego y puede ser 2, ó 4 ó 6. Las posibilidades son:

∑ gr(v ) = 6·6 + 2·7 = 50 = 2#E , luego #E = 25 (primer teorema de grafos) x=4;y=4; ∑ gr(v ) = 4·6 + 4·7 = 52 = 2#E , luego #E = 26 x=2;y=6; ∑ gr(v ) = 2·6 + 6·7 = 54 = 2#E , luego #E = 27

x=6;y=2;

i

i

i

Por otro lado 3·#V - 6 = 3·8 – 6 = 18, y el número de aristas es siempre mayor que 18, luego SOL: a) el grafo no es plano.

Ejercicio 6 Para que el número sea múltiplo de 11, la suma de las cifras de los extremos tiene que ser igual a la del centro, o a la del centro mas 11. Para los extremos hay VR(4,2) = 16 posibilidades. Comenzamos a probar 1 y 1 suman dos , que puede ir en el centro, y nos sale el 121; 1 y 2 suman 3, que no está entre las cifras que podemos utilizar. Si seguimos así encontramos 275, 572, 517 y 715. Luego sólo hay cinco posibilidades. SOL: b)

Ejercicio 7 El número de números enteros positivos menores que 119 y que son primos con él es Φ (119) . Como 119 = 7·17, Φ (119) = Φ (7)·Φ (17) = 6·16 = 96 SOL: b)

Ejercicio 8 Si se dibuja el grafo para 2n = 10, sale un grafo con 11 vértices y 15 aristas, formando una especie de aspas de molino de cinco brazos. En general, el vértice O es de grado 2n, y los vértices Pi son de grado dos (nótese que las aristas son: P1 P2 , P3 P4, P5 P6 ,..... , y OP1 , OP2 ,.... ), luego el grafo es euleriano (Todos los vértices son de grado par) y no es bipartito, ya que contiene ciclos de grado 3 (impar).

SOL: c)

Ejercicio 9 Hallamos primero los criterios de divisibilidad por 10 y por 12 en base 11: 110 = 1 ≡ 1 mód (10) ; 111 = 11 ≡ 1 mód (10) ; 112 = 121 ≡ 1 mód (10) esto es: 11n ≡ 1 mód (10) para todo n. Por tanto el criterio de divisibilidad por 10 en base 11 es que la suma de sus cifras sea múltiplo de 10. En nuestro caso la suma de las cifras es 30 + a + b, que nos dá que a + b ha de ser múltiplo de 10. Ahora lo hacemos para 12: 110 = 1 ≡ 1 mód (12) ; 111 = 11 ≡ -1 mód (12) ; 112 ≡ 1 mód (12) esto es: 11n ≡ (-1)n mód (12) para todo n. Por tanto el criterio de divisibilidad por 12 en base 11 es que la suma de las cifras de lugar par, menos la suma de las cifras de lugar impar sea 0, 12 ó múltiplo de 12. En nuestro caso (1 + a + 9 + 2) – (8 + 10 + b) = a – b – 6 = 0, que nos da a – b = 6 a + b = 10 ⎫ SOL: a) hay que resolver ⎬ que da a = 8 ; b = 2 a −b = 6 ⎭

________________________________________________________________________________ Matemática Discreta - Septiembre – Modelo A Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora Ejercicio 10 Como en la caja i hay por lo menos i bolas, antes de empezar a repartir ya hay: n(n + 1) n 2 − n n(n + 1) 1 + 2 + 3 + ..... + n = = bolas en las cajas. Quedan: n 2 − bolas a 2 2 2 repartir. ⎛ n2 + n − 2 ⎞ ⎟ ⎛ n2 − n ⎞ ⎛ n2 − n n2 − n ⎞ ⎜ 2 ⎜ ⎟ CR n Son CR ⎜ n, = + − = 1, ⎟ ⎜ ⎟ 2 ⎠ 2 2 ⎠ ⎜ n2 − n ⎟ ⎝ ⎝ ⎜ ⎟ 2 ⎝ ⎠ 2 2 n −n n +n−2 −1 = Ya que: n + SOL: b) 2 2 Zamora, 3 de Septiembre de 2.002

________________________________________________________________________________ Matemática Discreta - Septiembre – Modelo A Miguel Sobrino Morchón -4-

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo A Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta 26 ~ Mayo 2003 - MODELO A Ejercicio 1 Es fácil ver que la única opción que no es cierta es la c), ya que si tomamos a = 3 y b = 1, tenemos que a2 – b2 = 9 – 1 = 8 y 8, evidentemente, divide a 8.

Sol: c)

Ejercicio 2 El grafo es euleriano ya que todos sus vértices son de grado par

Figura 1

Figura 2

Figura 3

Figura 4

Para ver que no es hamiltoniano seguimos la secuencia de figuras de 1 a 4 donde al ir buscando un ciclo hamiltoniano, nos vamos quedando con los vértices de dos aristas (en la figura 2 tomamos los cuatro vértices del rectángulo) Al llegar, en la figura tres, a un vértice de grado 6, tiramos hacia el hexágono de la izquierda, quitando las cuatro aristas que sobran; al llegar (figra 4) al último vértice del hexágono, volvemos a quitar aristas y ya hemos dejado vértices que no van a poder entrar en el ciclo. Luego el grafo no admite un ciclo hamiltoniano y por tanto, no es hamiltoniano.

Sol: b)

Ejercicio 3

Por el Teorema de Wilson, como 17 es primo, 16! ≡ −1 mod (17) y por tanto, como −1 ≡ 16 mod (17), se tiene 15! ≡ 1 mod (17) ; 15 · 14! ≡ 1 mod (17) , o 15 y ≡ 1 mod (17) . Esto equivale a resolver la ecuación diofántica 17 x + 15 y = 1 . Como el m.c.d .(17,15) = 1 , y 1 = (-7) · 17 + 8 · 15, una solución de la ecuación es x = 8 ; y = -7, y por tanto 14! ≡ 8 mod (17) . El resto es 8.

Sol: a) ________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo A Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora Ejercicio 4 El significado de las entradas cij no nulas de A5 , siendo A la matriz asociada a un grafo G, es el número de caminos de longitud cinco que unen el vértice vi con el vértice v j . En este caso, si la entrada de la primera fila y la tercera columna de A5 , c13 , es distinta de cero, existe algún camino (uno de ellos seguro que de longitud 5) entre v1 y v3 .

Sol: b)

Ejercicio 5 Si calculamos el máximo común divisor de cada par de números nos sale: m.c.d .(1001,30) = 1 ; m.c.d .(797,50) = 1 ; m.c.d .(2331, 210) = 3 Para que cualquier número se pueda expresar en función de otros dos: n = ax + by , el máximo común divisor de a y b ha de dividir a n para cualquiera que sea n y eso solo es posible cuando m.c.d .(a, b) = 1 . La opción no correcta es la c)

Sol: c)

Ejercicio 6 Como las dos primeras cifras han de sumar nueve, solo puede ser con (3,6), (4,5), (5,4) y (6,3), y cada una de estas cuatro opciones habría que multiplicarlas por 3! que son las permutaciones de las otras tres cifras. Por tanto serían 4 · 3! = 4 · 6 = 24

Sol: b)

Ejercicio 7 Este ejercicio, si se considera el punto central (en el original del examen no tiene un punto para indicar que es un vértice) es un vértice, es muy fácil ver que se puede colorear con dos colores. Pero si no consideramos el centro como vértice, el grafo no sería plano, no habría tal mapa, para mi modesta opinión estaría mal planteado el ejercicio ya que se somete a distintas interpretaciones, y la solución podría ser la a) 2 colores o la d) ninguna de las anteriores. Merecería la pena que quien haya propuesto este ejercicio nos aclarara a todos su interpretación del mismo.

Sol: a) , d).... ??? Ejercicio 8 Si suponemos las variables a, b, c y d como cajas donde hay que colocar 100 objetos iguales, como nos dice que en la caja a hay por lo menos 30 objetos, en la b, 20 y en la c y en la d uno en cada una, ya habría repartidos 52, luego el problema se reduce a repartir 48 objetos iguales ⎛ 51 ⎞ Sol: a) en cuatro cajas y será: CR4,48 = C4+ 48−1,48 = C51,48 = ⎜ ⎟ ⎝ 48 ⎠

Ejercicio 9 Si “ __ “ representa los espacios donde pueden colocarse los “ceros” : __ 1 __ 1 __ 1 __ 1 __ 1 __ , tendríamos seis lugares, que habría que tomar de tres en tres ⎛ 6⎞ 6! 6·5·4 = = 20 . C6,3 = ⎜ ⎟ = 3! · 3! 3! ⎝ 3⎠

Sol: b) Luego la solución es la b) ________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo A Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora .

Ejercicio 10 Si agrupamos los días de dos en dos {1,2}, {3,4}, {5,6}, {7,8}, {9,10}, {11,12}, {13,14} y {15,16}, tenemos 8 grupos de dos días consecutivos. Dividimos 100 entre 8 y sale 12 de cociente y 4 de resto. Esto quiere decir que en el caso mas desfavorable, habría 12 horas en cada grupo y al repartir las 4 horas restantes, necesariamente habrá un par de días consecutivos en los que estudió al menos 13 horas. (Principio de Distribución)

Sol: a) Zamora, 27 de Mayo de 2.003

________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo A Miguel Sobrino Morchón -4-

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo B Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta 26 ~ Mayo 2003 - MODELO A Ejercicio 1 Si calculamos el máximo común divisor de cada par de números nos sale: m.c.d .(1001,30) = 1 ; m.c.d .(797,50) = 1 ; m.c.d .(2331, 210) = 3 Para que cualquier número se pueda expresar en función de otros dos: n = ax + by , el máximo común divisor de a y b ha de dividir a n para cualquiera que sea n y eso solo es posible cuando m.c.d .(a, b) = 1 . La opción no correcta es la c)

Sol: c)

Ejercicio 2 Si suponemos las variables a, b, c y d como cajas donde hay que colocar 100 objetos iguales, como nos dice que en la caja a hay por lo menos 30 objetos, en la b, 20 y en la c y en la d uno en cada una, ya habría repartidos 52, luego el problema se reduce a repartir 48 objetos iguales ⎛ 51 ⎞ Sol: a) en cuatro cajas y será: CR4,48 = C4+ 48−1,48 = C51,48 = ⎜ ⎟ ⎝ 48 ⎠

Ejercicio 3 Es fácil ver que la única opción que no es cierta es la c), ya que si tomamos a = 3 y b = 1, tenemos que a2 – b2 = 9 – 1 = 8 y 8, evidentemente, divide a 8.

Sol: c)

Ejercicio 4 Si “ __ “ representa los espacios donde pueden colocarse los “ceros” : __ 1 __ 1 __ 1 __ 1 __ 1 __ , tendríamos seis lugares, que habría que tomar de tres en tres ⎛ 6⎞ 6! 6·5·4 = = 20 . C6,3 = ⎜ ⎟ = 3! · 3! 3! ⎝ 3⎠ Luego la solución es la b)

Sol: b)

Ejercicio 5 Este ejercicio, si se considera el punto central (en el original del examen no tiene un punto para indicar que es un vértice) es un vértice, es muy fácil ver que se puede colorear con dos colores. Pero si no consideramos el centro como vértice, el grafo no sería plano, no habría tal mapa, para mi modesta opinión estaría mal planteado el ejercicio ya que se somete a distintas interpretaciones, y la solución podría ser la a) 2 colores o la d) ninguna de las anteriores. Merecería la pena que quien haya propuesto este ejercicio nos aclarara a todos su interpretación del mismo.

Sol: a) , d).... ??? Ejercicio 6 Si agrupamos los días de dos en dos {1,2}, {3,4}, {5,6}, {7,8}, {9,10}, {11,12}, {13,14} y {15,16}, tenemos 8 grupos de dos días consecutivos. Dividimos 100 entre 8 y sale 12 de cociente y 4 de resto. Esto quiere decir que en el caso mas desfavorable, habría 12 horas en cada grupo y al ________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo B Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora repartir las 4 horas restantes, necesariamente habrá un par de días consecutivos en los que estudió al

Sol: a)

menos 13 horas. (Principio de Distribución)

Ejercicio 7

Por el Teorema de Wilson, como 17 es primo, 16! ≡ −1 mod (17) y por tanto, como −1 ≡ 16 mod (17), se tiene 15! ≡ 1 mod (17) ; 15 · 14! ≡ 1 mod (17) , o 15 y ≡ 1 mod (17) . Esto equivale a resolver la ecuación diofántica 17 x + 15 y = 1 . Como el m.c.d .(17,15) = 1 , y 1 = (-7) · 17 + 8 · 15, una solución de la ecuación es x = 8 ; y = -7, y por tanto 14! ≡ 8 mod (17) . El resto es 8.

Sol: a) Ejercicio 8 El significado de las entradas cij no nulas de A5 , siendo A la matriz asociada a un grafo G, es el número de caminos de longitud cinco que unen el vértice vi con el vértice v j . En este caso, si la entrada de la primera fila y la tercera columna de A5 , c13 , es distinta de cero, existe algún camino (uno de ellos seguro que de longitud 5) entre v1 y v3 .

Sol: b)

Ejercicio 9 Como las dos primeras cifras han de sumar nueve, solo puede ser con (3,6), (4,5), (5,4) y (6,3), y cada una de estas cuatro opciones habría que multiplicarlas por 3! que son las permutaciones de las otras tres cifras. Por tanto serían 4 · 3! = 4 · 6 = 24 .

Sol: b)

Ejercicio 10 El grafo es euleriano ya que todos sus vértices son de grado par

Figura 1

Figura 2

Figura 3

Figura 4

________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo B Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora Para ver que no es hamiltoniano seguimos la secuencia de figuras de 1 a 4 donde al ir buscando un ciclo hamiltoniano, nos vamos quedando con los vértices de dos aristas (en la figura 2 tomamos los cuatro vértices del rectángulo) Al llegar, en la figura tres, a un vértice de grado 6, tiramos hacia el hexágono de la izquierda, quitando las cuatro aristas que sobran; al llegar (figra 4) al último vértice del hexágono, volvemos a quitar aristas y ya hemos dejado vértices que no van a poder entrar en el ciclo. Luego el grafo no admite un ciclo hamiltoniano y por tanto, no es

Sol: b)

hamiltoniano. Zamora, 27 de Mayo de 2.003

________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo B Miguel Sobrino Morchón -4-

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo E - Reserva Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta 14 ~ Junio 2003 - MODELO E Reserva Ejercicio 1 Por la Fórmula de Leibnitz el coeficiente de x 2 y3 z 3 en el desarrollo de ( x + 2 y + z ) será: 8! 8·7·6·5·4 12 ·23 ·13 ·P82,3,3 = 23 · = 8· = 8·8·7·5·2 = 4480 Sol: b) 2!3!3! 2·6 8

Ejercicio 2 Como el producto del máximo común divisor por el mínimo común múltiplo de dos números es igual al producto de ambos números, tendremos que: m·n 32 ·52 ·73 ·8 m.c .d . ( m, n ) = = = m.c.m.( m, n ) 44100

32 ·52 ·73 ·23 22 ·32 ·52 ·72

Sol: a)

= 2·7 = 14

Ejercicio 3 El grafo de la figura no es plano ya que #E = 13, #V = 6 y si aplicamos el corolario2-4.9 (página 174 L. Teoría) : “Sea G = (V, E) un grafo plano conexo, con #V > 2. Entonces #E ≤ 3#V – 6”

Sol: a)

En este caso 13 > 3· 6 – 6 = 12. No se cumple, luego el grafo no es plano.

Ejercicio 4 Se trata de hallar el resto de dividir 8401 entre 5. Como 5 es un número primo que no divide a 8, aplicamos el Pequeño Teorema de Fermat y entonces 84 ≡ 1 mod (5) . Como:

( )

8401 = 8400+1 = 84

100

· 8 ≡ 8 ≡ 3 mod (5) , el resto es 3 y el dedo es el dedo corazón.

Sol: b) Ejercicio 5 Si dos grafos G 1 y G 2 son isomorfos, sus matrices de adyacencia no tienen por que ser iguales, pero si que se puede obtener una a partir de la otra cambiando entre si filas y columnas, luego su determinante es igual u opuesto. Esto es si det (A1 ) = 0, entonces det (A2 ) = 0

Ejercicio 6

Sol: c)

( )

3

Como n es múltiplo de 3, podemos suponer que n = 3h , luego 5n = 53 h = 5h , y haciendo

(

)

5h = x , se tiene que 5n + 1 = x 3 +1 = ( x +1)· x 2 − x + 1 y por tanto, siempre es compuesto.

Sol: b) ________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo E - Reserva Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora Ejercicio 7 Se trata de establecer todas las aplicaciones posibles desde el conjunto X = {1,2,3,..100} = A ∪ B ∪ C en los seis subconjuntos C disjuntos que se pueden observar en la figura: ü Los que están solo en A A ü Los que están solo en B ü Los que están solo en C ü Los que están en A ∩ B ü Los que están en A ∩ C ü Los que están en B ∩ C En A ∩ B ∩ C no hay ningún elemento de X B Luego serán Variaciones con Repetición de 6 elementos tomados de 100 en 100, 6 100

Sol: a) Ejercicio 8 Los grafos no son isomorfos aunque tengan el mismo número de vértices, el mismo número de aristas y haya dos vértices de grado 3 y seis vértices de grado 2 en ambos grafos, pero los dos vértices de grado 3 en el grafo 1 (en rojo) son adyacentes; deberían transformarse en los dos de grado 3 del grafo dos, pero vemos en la figura que en el grafo 2 no son adyacentes. Por tanto los grafos no son isomorfos.

Sol: c) Gr a f o 1

Gr a f o 2

Ejercicio 9 Establecemos los criterios de divisibilidad entre 3 y entre 7 en base 20:

20 0 congruente con

mod (3) 1

mod (7) 1

201 = 20 congruente con

-1

-1

20 2 congruente con

1

1

20 n congruente con

( −1) n

( −1) n

Los criterios son similares: “Un número escrito en base 20 es múltiplo de tres (de siete), si la suma de las cifras que ocupan lugar par, menos la suma de las cifras que ocupan lugar impar, es cero ó múltiplo de tres (de siete)” . ________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo E - Reserva Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora Al restar doce treses menos doce doses, sale 12· 3 – 12· 2 = 12, que es múltiplo de tres, pero

Sol: b)

no lo es de siete. La solución es la b) .

Ejercicio 10 Este ejercicio se puede hacer de varias formas: Una sería dar valores a a, b, y c, por ejemplo: a = 4 ; b = 0 ; c = 1 . Entonces 5a + 7 b + 11c = 20 + 0 + 11 = 31 , múltiplo de 31, y probamos con las tres alternativas que nos dan: ü 21a + 17b + 9c = 84 + 0 + 9 = 93 , que es múltiplo de 31 (93 = 31 · 3) ü 16a + 10b − 2c = 64 + 0 − 2 = 62 , que es múltiplo de 31 (62 = 31 · 2) ü 16a + 27b + 2c = 64 + 0 + 2 = 66 , que no es múltiplo de 31 La afirmación falsa sería la c) Otra sería que, de suponer ciertas a) y b), restando, sale la hipótesis: 31 ( 5a + 7 b + 11c )

Sol: c)

Soluciones: El modelo F tiene las mismas preguntas, pero en distinto orden. Las soluciones de los dos modelos van en la tabla adjunta:

M odel o E M odel o F

1 b b

2 a b

3 a b

4 b c

5 c a

6 b a

7 a c

8 c b

9 b a

10 c c

Zamora, 14 de Junio de 2.003

________________________________________________________________________________ Junio 2003 - Matemática Discreta – Modelo E - Reserva Miguel Sobrino Morchón -4-

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Septiembre 2003 - Matemática Discreta – Modelo A Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta 2 ~ Septiembre 2003 - MODELO A Ejercicio 1

Todo número entero n se puede escribir: n = 4k + r , donde 0 ≤ r < 4 ; esto es r ∈ {0,1,2,3} Si x = n2 = ( 4k + r ) = 16k 2 + 8kr + r2 = 4 h + r 2 luego x ≡ r 2 mod ( 4 ) . Entonces: 2

•

Si r = 0 ; r 2 = 0 ≡ 0 mod ( 4 ) x es congruente con 0 módulo 4

•

Si r = 1 ; r 2 = 1 ≡ 1 mod ( 4 ) x es congruente con 1 módulo 4

•

Si r = 2 ; r 2 = 4 ≡ 0 mod ( 4 ) x es congruente con 0 módulo 4

• Si r = 3 ; r 2 = 9 ≡ 1 mod ( 4 ) x es congruente con 1 módulo 4 Las afirmaciones i) y ii) son ciertas y la iii) es falsa. Sólo dos afirmaciones son correctas.

Sol: b) Ejercicio 2 Esto es equivalente a ir colocando bolas en nueve cajas numeradas consecutivamente del 1 al 9; como en total hay 89 bolas a repartir, si lo fueramos haciendo de una en una, cuando en cada caja haya nueve bolas (81 en total), quedarían 8 bolas a repartir que siguiendo el caso más desfavorables iríamos poniendo una en cada caja y habría 8 cajas con 10 bolas y una con 9 y al tomar tres de 10 y una de 9 nos daría seguro al menos 39 bolas en cuatro cajas consecutivas. La

Sol: c)

solución es la c) 39 bolas

Ejercicio 3 Los grafos k-regulares tienen todos los vértices del mismo grado. Si tanto en el grafo G como en el G’ k es par, todos sus vértices son de grado par y, por tanto, son eulerianos. El hecho de que los dos grafos sean k-regulares no implica que k tenga que ser la misma; puede darse el siguiente caso:

Grafo G

Grafo G’

Los dos grafos tiene 5 vértices (mismo número de vértices), G es 2-regular y G’ Es 4regular (son k-regulares, con k par) y evidentemente no son isomorfos.

Sol: b)

________________________________________________________________________________ Septiembre 2003 - Matemática Discreta – Modelo A Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora Ejercicio 4 Para que un número sea múltiplo de 11, la suma de las cifras de lugar impar menos la suma de las cifras de lugar para ha de ser cero o múltiplo de 11. En el caso de números de tres cifras la diferencia de la cifra del centro y la suma de las dos de los extremos ha de ser o 0 o 11. Como las cifras de que disponemos son {2,3,5,8} , en el centro puede estar: ü 2, luego la suma de los extremos ha de ser 2 (no es posible) o 13 (5+8) y de aquí salen los números 528 y 825. ü 3, luego la suma de los extremos ha de ser 3 (no es posible) o 14 (no es posible) ü 5, luego la suma de los extremos ha de ser 5 (2+3) y de aquí salen los números 253 y 352 o 16 (8+8) y de aquí sale el 858. ü 8, luego la suma de los extremos ha de ser 8 (3+5) y de aquí salen los números 385 y 583, o 19 (no es posible).

Sol: b)

En total son siete números que cumplen las condiciones

Ejercicio 5 Por el Teorema de Euler, 214 ≡ 1 mod ( 5 ) , luego 214n +1 = 21 ⋅ 214 n ≡ 21 ≡ 1 mod ( 5 ) Por otro lado 5n es congruente con cero módulo 5 y 7 lo es con 2. En definitiva, 214n +1 − 5n + 7 ≡ 1 + 0 + 2 = 3 mod ( 5 ) , y por tanto el resto es 3

Sol: b)

Ejercicio 6

Fig. 3

Fig. 1

Fig. 4

Fig. 5

Fig. 6

Fig. 2

En la Fig. 1 puede verse que el grafo es bipartito (además, no contiene ciclos de longitud impar) ________________________________________________________________________________ Septiembre 2003 - Matemática Discreta – Modelo A Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora En la secuencia de figuras 2, 3 y 4 se intenta encontrar un ciclo hamiltoniano tomando primero los vértices de grado 2 (Fig. 2) y luego se van suprimiendo aristas de los vértices siguientes para que tengan grado 2 (Fig. 3 y 4) y ahora al prescindir de las aristas que sobran en la figura 4 se puede optar por la solución de la figura 5 o de la figura 6. En ambos casos quedan vértices desconectados, luego el grafo no es hamiltioniano. La solución es la a)

Sol: a)

Ejercicio 7 Para formar las palabras, las descompondremos en dos partes: Las letras 1ª y 5ª, y las letras 2ª, 3ª y 4ª: Primero, las letras primera y última, que han de ser vocales elegidas entre 5: VR5,2 = 52 Segundo, las tres letras del centro son dos consonantes y una vocal CVC: 5VR18,2 = 5 ⋅182 Tercero, las tres letras del centro son tres consonantes CCC: VR18,3 = 183 La primera parte se puede hacer de 52 formas, y la segunda de 5 ⋅ 182 + 18 3 = 182 (5 + 18) = 182 ⋅ 23 . En total son 182 ⋅ 52 ⋅ 23

Sol: c)

Ejercicio 8 Sepuede hacer directamente el producto en base 5, o bien, pasar a base 10 los dos números, multiplicarlos y luego pasar el resultado a base 5 2 2 1 3 4 2 5 10 60 5 15 95 61 · 97 = 5917, que ahora pasamos a base 5

2 12

61

3 19

5917

5

1183

5

236

2

1183

3

236

1

97

5 47 47

2

5

9

5

9

4

1

y la solución es 142132

Sol: a)

Ejercicio 9 Es equivalente a repartir veinticinco objetos iguales entre cinco cajas donde en la primera ha de haber al menos un objeto, en la segunda 2, en la tercera 3, en la cuarta 4 y en la quinta 5, luego hay 1+2+3+4+5 = 15 objetos ya se han repartido. Ahora habría que resolver la ecuación 14  x1 + x2 + x3 + x4 + x5 = 10 , y serían CR ( 5,10 ) = C ( 5 + 10 − 1,10 ) = C (14,10 ) =   Sol: b) 10 

Ejercicio 10 Se ve en la figura que se necesitan cuatro colores. La región exterior sería amarilla.

Sol: c) Zamora, 6 de Septiembre de 2.003 ________________________________________________________________________________ Septiembre 2003 - Matemática Discreta – Modelo A Miguel Sobrino Morchón -4-

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Junio 2004 1ª semana - Matemática Discreta – Modelo A Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta 1ª semana 24 ~ Mayo 2004 MODELO A Ejercicio 1 Formamos dos grupos: uno con las vocales, que serán variaciones ordinarias de 4 letras tomadas de dos en dos, V(4, 2), y otro con las consonantes, que serán variaciones ordinarias de 17 letras tomadas de dos en dos, V(17, 2). Luego, por el Principio de Multiplicación, habrá V(4, 2)·V(17, 2) = 12·272 = 3264 palabras distintas.

Sol: b)

Ejercicio 2 Sea x el número de botellas de vino tinto e y el precio de la botella de vino blanco. Habrá 100 – x botellas de vino blanco y el precio de la botella de vino tinto será de y + 2 euros. El problema se reduce a resolver la ecuación diofántica: x ( y + 2 ) + (100 − x ) y = 492 , que simplificada queda: 2 x + 100 y = 492 . El m.c.d. de 2 y de 100 es 2, que divide a 492, luego la ecuación tiene 1·496 0·496 = 246 ; y0 = = 0 como solución solución. Como 2 = 1·2+0·100, se resuelve y sale x0 = 2 2 particular y su solución general: 100t x = 246 + = 246 + 50t 2 2t y = 0 − = −t 2 −146 Como x ≤ 100 , se tiene que 246 + 50t ≤ 100 ⇒ t ≤ ⇒ t ≤ −3 50 Si t = −3 ⇒ x = 246 − 150 = 96 botellas de tinto y 4 de blanco Si t = −4 ⇒ x = 246 − 200 = 46 botellas de tinto y 54 de blanco Estas son las dos soluciones de la ecuación y como dice que se compra el menor número

posible de botellas de vino blanco, la solución sería x = 96 y por tanto 60 < x < 100

Sol: c)

Ejercicio 3 Las letras a, b y c han de ir necesariamente en los huecos x _ x _ x _ x, por tanto serían las permutaciones de tres, esto es 3!

Sol: a) Ejercicio 4

Grafo 2 Grafo 1 ________________________________________________________________________________ Junio 2004 1ª semana - Matemática Discreta – Modelo A Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora Los grafos 1 y 2 no son isomorfos pues, aunque tienen 9 vértices y 11 aristas, cuatro vértices de grado 3 y cinco de grado 2 , en el grafo 2 hay un vértice de grado 2 entre dos de grado 3, y en el grafo 1 no. El grafo 1 es hamiltoniano , y quedaría el siguiente ciclo al quitar una arista de los vértices que no tienen grado dos.

El grafo 2 no es hamiltoniano ya que al hacer lo mismo que en el grafo 1, quedaría un

Sol: c)

vértice desconectado.

Ejercicio 5

Como han de ser soluciones enteras positivas, se excluye el cero, luego xi ≥ 1 (es como si en cada una de las cuatro cajas hubiera al menos una bola). Luego habría que repartir 22 – 4 = 18 bolas ⎛ 21⎞ entre cuatro cajas. Esto es CR(4,18) = C (4 + 18 − 1,18) = C (21,18) = ⎜ ⎟ Sol: a) ⎝ 18 ⎠

Ejercicio 6 Se ve fácilmente que para colorear el primer mapa son necesarios cuatro colores, y para el segundo 2 . Luego la solución es ni a) ni b) 2 4

3

2 1

1 2 2

3

1

2 1

1

1

2

2 1

1

Sol: c) Ejercicio 7

Todo número n se puede expresar de la forma n = 4k + r , donde 0 ≤ r < 4 . n 2 = 16k 2 + 8kr + r 2 , y tendríamos: Para r = 0 , n 2 = 16k 2 + 0 ≡ 0 mod(8) ≡ 0 mod(4) Para r = 1 , n 2 = 16k 2 + 8k + 1 ≡ 1 mod(8) ≡ 1 mod(4)

________________________________________________________________________________ Junio 2004 1ª semana - Matemática Discreta – Modelo A Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora Para r = 2 , n 2 = 16k 2 + 16k + 4 ≡ 4 mod(8) ≡ 0 mod(4) Para r = 3 , n 2 = 16k 2 + 16k + 9 ≡ 1 mod(8) ≡ 1 mod(4) Por tanto i) y ii) son ciertas. iii) es falsa; basta con tomar 121 que es congruente con 4

Sol: b)

módulo 9

Ejercicio 8 El ejercicio 9 de la página 94 del libro de problemas dice: “Si un grafo G = (V,E) posee k 1 componentes conexas, entonces se verifica: # E ≤ ( # V − k )( #V − k + 1) 2 En nuestro caso # V = 12 y # E = 50 1 11·12 = 66 , es cierta Si k = 1 (grafo conexo) , 50 ≤ (12 − 1)(12 − 0 ) = 2 2 1 10·11 Si k = 2 (grafo con 2 componentes) , 50 ≤ (12 − 2 )(12 − 1) = = 55 , es cierta 2 2 1 9·10 = 45 , ya no es cierta Si k = 3 (grafo con 3 componentes) , 50 ≤ (12 − 3)(12 − 2 ) = 2 2 Por tanto, el grafo tiene a lo más dos componentes conexas

Sol: c)

Ejercicio 9 El primer valor de n que lo verifica es 11, excluido en el enunciado, y el siguiente sería 11 + m.c.m.(12, 13, 14) = 11 + 1092 = 1103 En efecto, 1103 + 1 = 1104 = 12·92; 1103 + 2 = 1105 = 13·85 y 1103 + 3 = 1106 = 14·79

Sol: c)

Luego 1101 < n .

Ejercicio 10 Sería C ( 6,3)·d (6 − 3) = C ( 6,3)·d ( 3) =

6! ⎡ 0 1 1 1 ⎤ ·3! − + − = 20·[3 − 1] = 40 3!3! ⎢⎣ 0! 1! 2! 3!⎥⎦

Sol: c) Zamora, 25 de Mayo de 2.004

________________________________________________________________________________ Junio 2004 1ª semana - Matemática Discreta – Modelo A Miguel Sobrino Morchón -4-

Centro Asociado de la U.N.E.D. de Zamora

________________________________________________________________________________ Junio 2004 2ª semana - Matemática Discreta – Modelo C Miguel Sobrino Morchón -1-

Centro Asociado de la U.N.E.D. de Zamora Examen de Matemática Discreta 2ª semana 7 ~ Junio ~ 2004 MODELO C Ejercicio 1

Figura 1

Figura 2

El grafo no es euleriano ya que tiene cuatro vértices de grado tres (se puede contar en la figura 1) Por otro lado si se quitan los dos vértices rojos, quedan (figura 2) tres componentes conexas y por tanto, no es hamiltoniano ya que aplicamos el Teorema 2-2.21 de la página 146, que dice “Sea G = (V,E) un grafo tal que #V ≥ 3. Si G es hamiltoniano, para cada subconjunto U de V, el subgrafo de G cuyos vértices son los de V-U y sus aristas son todas las de G que tiene extremos en V-U, tiene a lo más #U componentes” Luego ni es euleriano ni es hamiltoniano.

Sol: a)

Ejercicio 2 Se trata de las desordenaciones de 5 elementos. 5

d (5) = 5!∑ j =0

( −1)

j

⎡ 1 1 1 1 1 1 ⎤ 5! 5! 5! 5! = 5! ⎢ − + − + − ⎥ = − + − = 60 − 20 + 5 − 1 = 44 j! ⎣ 0! 1! 2! 3! 4! 5!⎦ 2! 3! 4! 5!

Sol: b) Ejercicio 3

La ecuación diofántica 84 x + 990 y = c tiene soluciones enteras si y solo si el máximo común divisor de 84 y 990, divide a c. Dicho m.c.d. es 6 que solo divide a 12 y a 18 para 10 < c < 20 , luego la ecuación no tiene soluciones enteras para todos los valores de c menos dos.

Sol: b) Ejercicio 4

El grafo G es n-regular y tiene n + 1 vértices, luego es completo y por tanto isomorfo a K n +1 Todos los grafos completos con el mismo número de vértices son isomorfos. Sus matrices de adyacencia serían todo “unos”, excepto la diagonal principal, que serían todos “ceros”

Sol: a) ________________________________________________________________________________ Junio 2004 2ª semana - Matemática Discreta – Modelo C Miguel Sobrino Morchón -2-

Centro Asociado de la U.N.E.D. de Zamora Ejercicio 5 Como: n + 1) ! n ( n − 1) ( n + 1) n n 2 − n + n 2 + n ⎛n⎞ ⎛ n + 1⎞ ( n! + = + = = n2 ⎜ ⎟ + ⎜ ⎟= 2 2 2 ⎝ 2⎠ ⎝ 2 ⎠ 2!( n-2 ) ! 2!( n + 1 − 2 ) !

Sol: c)

Para cualquier valor de n

Ejercicio 6 Veamos para p = 5 2

3

1

5

⎛0 ⎜ ⎜1 La matriz de adyacencia sería A = ⎜ 0 ⎜ ⎜0 ⎜1 ⎝

1 0 1 0 0

0 1 0 1 0

0 0 1 0 1

1⎞ ⎟ 0⎟ 0⎟ ⎟ 1⎟ 0 ⎟⎠

4

Y cumple las condiciones del enunciado. Los ceros, excepto los de la diagonal principal pueden ser unos, que supondría añadir aristas. Se ve que el grafo es hamiltoniano (con los datos del enunciado están siempre las aristas que forman el perímetro de un polígono). Puede ser no euleriano en cuanto añadamos alguna arista de tal forma que queden vértices de grado impar. Por ejemplo: 2

3

1

5

4

⎛0 ⎜ ⎜1 La matriz de adyacencia sería A = ⎜ 0 ⎜ ⎜1 ⎜1 ⎝

1 0 1 0 0

0 1 0 1 0

1 0 1 0 1

1⎞ ⎟ 0⎟ 0⎟ ⎟ 1⎟ 0 ⎟⎠

Sol: c) Ejercicio 7 Para elegir presidente hay cuatro posibilidades y para elegir Vicepresidente y Secretario son variaciones ordinarias de 7 elementos tomados de dos en dos: V ( 7, 2 ) = 7 · 6 = 42 Luego habrá 4 por 42, igual a 168 formas posibles.

________________________________________________________________________________ Junio 2004 2ª semana - Matemática Discreta – Modelo C Miguel Sobrino Morchón -3-

Centro Asociado de la U.N.E.D. de Zamora Sol: a) Ejercicio 8 Por el Pequeño Teorema de Fermat, como 5 es primo y no divide a 117, 117 4 ≡ 1 mod (5)

Por otro lado, 117 2

n

+1

= 117·117 4 h , ya que n es par

117 ≡ 2 mod (5) , y tendríamos que 117 2

n

+1

(

= 117 · 117 4

)

h

≡ 2 · 1h = 2

Sol: a) Ejercicio 9 El grafo tiene 8 vértices de grado 5, luego tiene 20 aristas, y aplicando el Corolario 2-4.9 (página 174 del libro de teoría), que dice: Sea G=(V,E) un grafo plano conexo, con #V > 2. Entonces #E ≤ 3#V – 6 En nuestro caso 20 > 3 · 8 – 6 = 18 Por tanto, el grafo no es plano. Tampoco es bipartito; si observamos la matriz de adyacencia, el grafo contiene ciclos de longitud impar. ( v2v3 , v3v6 , v6 v2 es un ciclo de longitud tres que está contenido en el grafo G) ⎛0 ⎜ ⎜0 ⎜ ⎜0 ⎜1 A=⎜ ⎜1 ⎜1 ⎜ ⎜1 ⎜1 ⎝

0

0

1 1

1

0

1

0 1

1

1

0

0 1

1

0

0

0 1

1

1

1

1 0

0

1

1

1 0

0

1

1

1 0

1

1

1

1 1

0

1 1⎞ ⎟ 1 1⎟ ⎟ 1 1⎟ 1 1⎟ ⎟ 0 1⎟ 1 0⎟ ⎟ 0 0⎟ 0 0 ⎟⎠

Sol: a) .

Ejercicio 10

La i) y la ii) son ciertas, ya que al resolver las ecuaciones diofánticas 2 x + 5 y = n y 3x + 8 y = n , el mcd ( 2,5 ) = mcd ( 3,8 ) = 1 , que siempre divide a n, nos indica que las ecuaciones

tienen solución. La iii) también es cierta pues la inecuación n − 1 <

n2 − n , es equivalente a n 2 − 3n + 4 > 0 , 2

que siempre tiene solución positiva. Por tanto son correctas las tres.

Sol: c)

Zamora, 7 de Junio de 2.004

________________________________________________________________________________ Junio 2004 2ª semana - Matemática Discreta – Modelo C Miguel Sobrino Morchón -4-