7/26/2019 Exmenes de Matemtica Discreta
1/105
7/26/2019 Exmenes de Matemtica Discreta
2/105
7/26/2019 Exmenes de Matemtica Discreta
3/105
7/26/2019 Exmenes de Matemtica Discreta
4/105
12 + 22 + 32 + ... + (n 1)2 + n2 =n(n+ 1)(2n+ 1)
6
f : A B
A
f
f(a) =f(b)
a= b
f
A
B
a
b
c
a
c
7/26/2019 Exmenes de Matemtica Discreta
5/105
12 + 22 + 32 + ... + (n 1)2 + n2 =n(n+ 1)(2n+ 1)
6
n= 1
12 = 1 =1 2 3
6
n
n + 1
12 + ... + n2 + (n+ 1)2 =(n + 1)(n+ 2)(2n+ 3)
6
12 + ... + n2 + (n+ 1)2 = n(n+ 1)(2n+ 1)6
+ (n+ 1)2.
(n+ 1)(n+ 2)(2n+ 3)
6 .
a1,...,an
s:= 0
i= 1
n
s= 0
j =i + 1
n
s= 0
ai=aj
s:= 1
s= 0
r:=
r:=
r
7/26/2019 Exmenes de Matemtica Discreta
6/105
O(n2)
i
n
j
n i
f : A B
A
f
f(a) =f(b)
a= b
f
A
B
A
n
A
1, 2,...,n
B
1, 2,...,m
m
B
f(1), f(2),...,f(n)
f
A
a
b
c
a
c
a
b
b
a= (a0, a1,...,an)b, b , cp:= a0, i:= 0
(i < n)i:= i + 1p:= p + aib
i
p
b
7/26/2019 Exmenes de Matemtica Discreta
7/105
x 3(mod5)x 5(mod7)
x 9(mod11).
A
B
A
B
210
2210
22210
52 283
5 4 28 27 26
5 4 283
x
y
xayb
a
b
a+ b = n
18 17
9 17
7/26/2019 Exmenes de Matemtica Discreta
8/105
182
5!
5!/4
5!/5
(3 2 36)/(39 38 37)
(4 3 2 36)/(39 38 37)
(3 3 2 36)/(39 38 37)
n
p
n
3
pn3(1 p)3
3i=0n
i
pni(1 p)i
A
X
A
E(X)
E
F
E
F
7/26/2019 Exmenes de Matemtica Discreta
9/105
F
E
a
b
mcd(a, b) = 1
mcd(a + b, a b) = 1
mcd(a + b, a b) = 3
mcd(a + b, a b) = 1
mcd(a + b, a b) = 2
mcd(a + b, a b) = 21
mcd(a + b, a b) = 3
mcd(234, 567)
7/26/2019 Exmenes de Matemtica Discreta
10/105
3 5 = 15
x 3(mod5)x 5(mod7)
x 9(mod11).
5 7 11 = 385
A
B
A
B
210
2210
22210
n
2n
52 283
7/26/2019 Exmenes de Matemtica Discreta
11/105
5 4 28 27 26
5 4 283
x
y
n
xayb
a
b
a+ b = n
18 17
9 17
18
a
b
b= 17 a
a
a
0
17
5!
5!/4
5!/5
5!
(3 2 36)/(39 38 37) (4 3 2 36)/(39 38 37)
(3 3 2 36)/(39 38 37)
3/39
7/26/2019 Exmenes de Matemtica Discreta
12/105
2/38
36/38
(3 2 36)/(39 38 37).
n
p
n
3pn3(1 p)3
3i=0nip
ni
(1 p)i
A
X
A
E(X)
p1,...,pn
p1 ... pn + 1
pi
7/26/2019 Exmenes de Matemtica Discreta
13/105
103 2
E
F
E
F
F
E
a
b
a > b
mcd(a, b) = 1
mcd(a + b, a b) = 1
mcd(a + b, a b) = 3
mcd(a + b, a b) = 1
mcd(a + b, a b) = 2
mcd(a + b, a b) = 21
mcd(a + b, a b) = 3
p= mcd(a + b, a b)
a + b= ps
a b= pt
2a= p(s + t)
2b= p(s t).
p
2a
2b
p
mcd(2a, 2b)
p= 2
p
a
b
p= 1
7/26/2019 Exmenes de Matemtica Discreta
14/105
mcd(234, 567)
7/26/2019 Exmenes de Matemtica Discreta
15/105
x 2(mod5)x 4(mod7)
x 8(mod11).
(3 2 36)/(39 38 37)
(4 3 2 36)/(39 38 37)
(3 3 2 36)/(39 38 37)
x
y
xayb
a
b
a+ b = n
18 17
9 17
7/26/2019 Exmenes de Matemtica Discreta
16/105
182
52 282
5 4 28 27
5 4 282
6!/4
5! 6!/5
n
p
n
3
pn3(1 p)3
3i=0n
i
pni(1 p)i
B
X
A
E(X)
a
b
mcd(a, b) = 1
mcd(a + b, a b) = 1
mcd(a + b, a b) = 3
mcd(a + b, a b) = 1
mcd(a + b, a b) = 2
mcd(a + b, a b) = 21
mcd(a + b, a b) = 3
7/26/2019 Exmenes de Matemtica Discreta
17/105
mcd(234, 567)
A
B
A
B
27
2227
227
E
F
E
F
F
E
7/26/2019 Exmenes de Matemtica Discreta
18/105
4 2 = 8
x 2(mod5)x 4(mod7)
x 8(mod11).
5 7 11 = 385
(3 2 36)/(39 38 37)
(4 3 2 36)/(39 38 37)
(3 3 2 36)/(39 38 37)
3/39
2/38
7/26/2019 Exmenes de Matemtica Discreta
19/105
36/38
(3 2 36)/(39 38 37).
p1,...,pn
p1 ... pn + 1
pi
x
y
xayb
a
b
a+ b = n
18 17
9 17
18
a
b
b= 17 a
a
a
0
17
52 282
5 4 28 27
5 4 282
7/26/2019 Exmenes de Matemtica Discreta
20/105
7/26/2019 Exmenes de Matemtica Discreta
21/105
p= mcd(a + b, a b)
a + b= ps
a b= pt
2a= p(s + t)
2b= p(s t).
p
2a
2b
p
mcd(2a, 2b)
p= 2
p
a
b
p= 1
mcd(234, 567)
A
B
A
B
27
2227
227
n
2n
7/26/2019 Exmenes de Matemtica Discreta
22/105
E
F
E
F
F
E
7/26/2019 Exmenes de Matemtica Discreta
23/105
a R
a > 0
n
(1 + a)n 1 + an.
((p q) (q r)) (p r).
f : Z7 Z7
f(a) =5a+ 1
Z7
f
g: Z7 Z7
g f
(g f)(a) =g(f(a))
x3 mod 5
x5 mod 7
x2 mod 2
a1, a2,...,an
a
1 b n +1
a
b
7/26/2019 Exmenes de Matemtica Discreta
24/105
a R
a > 0
n
(1 + a)n 1 + an.
n= 1
1 + a 1 + a.
n
n + 1
(1 + a)n+1 = (1 + a)n(1 + a) (1 + an)(1 + a)
(1 + an)(1 + a) = 1 + a + an+ a2n.
1 + a + an+ a2n 1 + a(n + 1) = 1 + an + a.
a2n 0,
a >0
((p q) (q r)) (p r).
p:= F
r:= V
q:= V
(p q) :=V
(q r) :=V
((p q) (q r)) :=V .
7/26/2019 Exmenes de Matemtica Discreta
25/105
(p r) :=F
V F
U
A
U A
P((x, y)) :=el alumno x ha aprobado la asignatura y.
xUy A (P(x, y)).
x Uy A P(x, y).
f : Z7 Z7
f(a) =5a + 1
Z7
f
f(0) = 1f(1) = 6f(2) = 4f(3) = 2f(4) = 0f(5) = 5f(6) = 3
f
g: Z7 Z7
g f
(g f)(a) =g(f(a))
f
g
g(b) = 3b + 4
7/26/2019 Exmenes de Matemtica Discreta
26/105
g(f(a)) =g(5a + 1) = 3(5a+ 1) + 4 =a + 3 + 4 =a
x 3 mod 5
x 5 mod 7
x 2 mod 2
572 = 70
x= 68 + 70k
k
a1, a2,...,an
a
1 b n +1
a
b
a1, a2,...,an; a, bc:= abab:=a
b + 1
nd:= aiai:= cc:= d
an+1:=c
a1,...,an+1
7/26/2019 Exmenes de Matemtica Discreta
27/105
t R
t > 0
n
(1 + t)n 1 + tn.
((p q) (q r)) (p r).
f : Z7 Z7
f(a) =3a + 1
Z7
f
g: Z7 Z7
g f
(g f)(a) =g(f(a))
x4 mod 5
x5 mod 7
x2 mod 2
a1, a2,...,an
a
1 b n +1
a
b
7/26/2019 Exmenes de Matemtica Discreta
28/105
t R
t > 0
n
(1 + t)n 1 + tn.
n= 1
1 + t 1 + t.
n
n + 1
(1 + t)n+1 = (1 + t)n(1 + t) (1 + tn)(1 + t)
(1 + tn)(1 + t) = 1 + t + tn + t2
n.
1 + t + tn + t2n 1 + t(n + 1) = 1 + tn + t.
t2n 0,
t >0
((p q) (q r)) (p r).
p:= V
r:= V
q:= V
(p q) :=V
(q r) :=V
((p q) (q r)) :=V .
7/26/2019 Exmenes de Matemtica Discreta
29/105
(p r) :=V
V F
U
A
U A
P((x, y)) :=el alumno x ha aprobado la asignatura y.
xUy A (P(x, y)).
x Uy A P(x, y).
f : Z7 Z7
f(a) =3a + 1
Z7
f
f(0) = 1f(1) = 4f(2) = 0f(3) = 3f(4) = 6f(5) = 2f(6) = 5
f
g:Z7
Z7
g f
(g f)(a) =g(f(a))
f
g
g(b) = 5b + 2
g(f(a)) =g(3a + 1) = 5(3a+ 1) + 2 =a + 5 + 2 = a
7/26/2019 Exmenes de Matemtica Discreta
30/105
x 4 mod 5
x 5 mod 7
x 2 mod 2
572 = 70
x= 54 + 70k
k
a1, a2,...,an
a
1 b n +1
a
b
a1, a2,...,an; a, bc:= abab:=a
b + 1
nd:= aiai:= cc:= d
an+1:=c
a1,...,an+1
7/26/2019 Exmenes de Matemtica Discreta
31/105
7/26/2019 Exmenes de Matemtica Discreta
32/105
A3 :=
20 37 29 37 28 21 18 46 29 33 31 21 33 45 2837 38 49 63 41 42 34 62 31 41 43 36 33 65 3829 49 40 57 39 33 25 61 36 43 48 28 42 60 4037 63 57 72 60 44 41 80 46 55 61 45 54 80 5928 41 39 60 40 40 29 60 29 40 48 35 33 59 4321 42 33 44 40 26 24 52 27 30 37 30 34 51 5918 34 25 41 29 24 16 40 20 25 35 19 24 36 3246 62 61 80 60 52 40 74 40 54 65 39 52 78 5829 31 36 46 29 27 20 40 22 28 35 19 29 45 2733 41 43 55 40 32 25 54 28 32 38 26 32 55 35
31 43 48 61 48 37 35 65 35 38 44 39 35 65 4521 36 28 45 35 30 19 39 19 26 39 20 25 37 3633 33 42 54 33 34 24 52 29 32 35 25 28 53 3045 65 60 80 59 51 36 78 45 55 65 37 53 76 5928 38 40 59 43 39 32 58 27 35 45 36 30 59 40
A
A
G
G
p
q
G
g
g
G
7/26/2019 Exmenes de Matemtica Discreta
33/105
7/26/2019 Exmenes de Matemtica Discreta
34/105
A3 :=
20 37 29 37 28 21 18 46 29 33 31 21 33 45 2837 38 49 63 41 42 34 62 31 41 43 36 33 65 3829 49 40 57 39 33 25 61 36 43 48 28 42 60 4037 63 57 72 60 44 41 80 46 55 61 45 54 80 5928 41 39 60 40 40 29 60 29 40 48 35 33 59 4321 42 33 44 40 26 24 52 27 30 37 30 34 51 5918 34 25 41 29 24 16 40 20 25 35 19 24 36 3246 62 61 80 60 52 40 74 40 54 65 39 52 78 5829 31 36 46 29 27 20 40 22 28 35 19 29 45 2733 41 43 55 40 32 25 54 28 32 38 26 32 55 35
31 43 48 61 48 37 35 65 35 38 44 39 35 65 4521 36 28 45 35 30 19 39 19 26 39 20 25 37 3633 33 42 54 33 34 24 52 29 32 35 25 28 53 3045 65 60 80 59 51 36 78 45 55 65 37 53 76 5928 38 40 59 43 39 32 58 27 35 45 36 30 59 40
1515
(6, 9, 8, 12, 8, 7, 5, 12, 6, 7, 9, 6, 7, 12, 8).
122/2 = 61
A
A
G
A3
(1, 3)
A3
7/26/2019 Exmenes de Matemtica Discreta
35/105
1a13
13a3
(1, 3)
A
G
p
q
p= 3/15 q= 1 p= 12/15.
1 (12/15)5.
G
g
g
N15
g
g(1) = 6, g(2) = 9, g(3) = 8, g(4) = 12, g(5) = 8, g(6) = 7, g(7) = 5, g(8) = 12,
g(9) = 6, g(10) = 7, g(11) = 9, g(12) = 6, g(13) = 7, g(14) = 12, g(15) = 8.
(6 + 9 + 8 + 12 + 8 + 7 + 5 + 12 + 6 + 7 + 9 + 6 + 7 + 12 + 8)/15.
G
K15
(15 14)/2.
|V|
G
105 61
7/26/2019 Exmenes de Matemtica Discreta
36/105
Z6
Z6={0, 1, 2, 3, 4, 5},
f : Z6 Z6
f(x) = 2x.
f
7/26/2019 Exmenes de Matemtica Discreta
37/105
A=
0 1 1 1 0 0 11 0 0 1 0 0 0
1 0 0 1 0 0 01 1 1 0 0 1 10 0 0 0 0 1 00 0 0 1 1 0 11 0 0 1 0 1 0
7/26/2019 Exmenes de Matemtica Discreta
38/105
N7
R
a, b N7, (aRb (a + b)< 5) .
7/26/2019 Exmenes de Matemtica Discreta
39/105
a :=
n :=
e:=
a (n e)a (a e)n
a
V
a e
V
a
a
F
a := V
a:= V
n:= F
e
7/26/2019 Exmenes de Matemtica Discreta
40/105
z= 1 + ... + n= n(n 1)/2.
x 1 mod 2x 1 mod 3x 2 mod 7
2 3 7 = 42
37 + 42k k Z.
37+42 = 79
Z6
Z6={0, 1, 2, 3, 4, 5},
f : Z6 Z6
f(x) = 2x.
f
f(0) = 0
f(3) = 0
a Z6
g(a) = 1
7/26/2019 Exmenes de Matemtica Discreta
41/105
11!
10!
10!/11! = 1/11
2 9!
10 2 9!
10 2 9!/11! = 2/11.
0.0015
1 0.9995
A=
0 1 1 1 0 0 1
1 0 0 1 0 0 01 0 0 1 0 0 01 1 1 0 0 1 10 0 0 0 0 1 00 0 0 1 1 0 11 0 0 1 0 1 0
7/26/2019 Exmenes de Matemtica Discreta
42/105
N85
N84
N4
E :={(1, 1), (2, 2), (3, 3), (4, 4)}
7/26/2019 Exmenes de Matemtica Discreta
43/105
E:={(1, 2), (1, 2), (3, 3), (4, 4)}
E:={(1, 2), (1, 2), (3, 4), (3, 4)}E:={(1, 2), (2, 3), (3, 4), (4, 1)}E :={(1, 2), (2, 3), (3, 1), (4, 4)}
N7
R
a, b N7, (aRb (a + b)< 5) .
N7
R:= {(1, 1), (1, 2), (2, 1), (1, 3), (3, 1), (2, 2)}.
(7, 7) / R
a+ b < 5
b+a < 5
(1, 2), (2, 1) R
(3, 1), (1, 3) R
(3, 3) /R
Ct = R {(3, 3)}
7/26/2019 Exmenes de Matemtica Discreta
44/105
P(x)
Q(x)
x 2(mod3)x 5(mod7)
x 1(mod5)
n N
7/26/2019 Exmenes de Matemtica Discreta
45/105
0 1 0 0 1 01 0 1 0 0 10 1 0 1 0 00 0 1 0 1 01 0 0 1 0 00 1 0 0 0 0
p = 0.1
G=(V, A)
0 1 0 0 0 0 0 01 0 1 1 0 0 0 00 1 0 1 0 0 0 0
0 1 1 0 0 0 0 00 0 0 0 0 1 0 00 0 0 0 1 0 1 00 0 0 0 0 1 0 10 0 0 0 0 0 1 0
7/26/2019 Exmenes de Matemtica Discreta
46/105
G
(1, 5)
(V, A {(1, 5)})
G
(V, A {(1, 5)})
A= {1, 2, 3, 4, 8, 7, 54, 34, 52, 21, 11, 12, 13, 16, 112}.
A
a, b A
aRb
a b0(mod3)
R
A
A
R
7/26/2019 Exmenes de Matemtica Discreta
47/105
P(x)
Q(x)
x U(P(x) Q(x))
xU (P(x) Q(x))
x U(P(x) Q(x))
7/26/2019 Exmenes de Matemtica Discreta
48/105
x 2(mod3)x 5(mod7)x 1(mod5)
3 7 5 = 105
x= 26 + 105k k Z.
n N
c:= 1 + (1 + 2) + (1 + 2 + 3) + ... + (1 + 2 + ... + n)
j
n
i
j
0 1 0 0 1 01 0 1 0 0 10 1 0 1 0 00 0 1 0 1 01 0 0 1 0 00 1 0 0 0 0
7/26/2019 Exmenes de Matemtica Discreta
49/105
p = 0.1
p= 0.1
6i=2
6
i
pi(1 p)1i.
(1, 2)
(1, 5), (5, 4), (4, 3), (3, 2)
p(1 (1 p)4).
G=
(V, A)
0 1 0 0 0 0 0 01 0 1 1 0 0 0 00 1 0 1 0 0 0 00 1 1 0 0 0 0 00 0 0 0 0 1 0 00 0 0 0 1 0 1 00 0 0 0 0 1 0 10 0 0 0 0 0 1 0
G
(1, 5)
(V, A {(1, 5)})
7/26/2019 Exmenes de Matemtica Discreta
50/105
7/26/2019 Exmenes de Matemtica Discreta
51/105
42n 1
n
7/26/2019 Exmenes de Matemtica Discreta
52/105
42n 1
n
42 1 = 15
t Z
42n 1 = 15t.
42(n+1) 1
42(n+1) 1 = 42n+2 1 = 42 42n 1.
42(n+1) 1 = 42 (15t + 1) 1 = 42 15t + 16 1 = 42 15t + 15.
a1,...,anc:= 0
i= 2
n
j = 1
i 1
aj =ai
c:= j
j :=n+ 1
i:= n + 1
c:= 0
c:=
c
7/26/2019 Exmenes de Matemtica Discreta
53/105
i 1
j
T(n)
T(n) = 3 + 3 2 + 2 + 3 3 + 2 + 3 4 + 2 + .. + 3 n + 2 + 1
c
i
O(T(n)) =O(n2).
7/26/2019 Exmenes de Matemtica Discreta
54/105
1 + 2 + 2
2
+ ... + 2
n
= 2
n+1
1
7/26/2019 Exmenes de Matemtica Discreta
55/105
1 + 2 + 2
2
+ ... + 2
n
= 2
n+1
1
n= 1
1 + 2 = 22 1
1 + 2 + ... + 2n + 2n+1 = (1 + 2 + .. + 2n) + 2n+1,
1 + 2 + ... + 2n
+ 2n+1
= 2n+1
1 + 2n+1
= 2n+2
1.
a1
anS := 0
i= 2
n
S := 0if ai < ai 1 S:= 1
S= 0
r:=
r:= ai1
r
7/26/2019 Exmenes de Matemtica Discreta
56/105
G= (V, E)
0 0 1 1 0 0 0 0 0 1 0 0 0 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 1 0 0 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 1 0 0 0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1 0 1 00 0 0 0 0 0 0 0 1 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 1 00 0 0 0 0 0 0 0 0 0 1 0 1 0 01 0 0 1 0 0 0 0 0 0 0 0 0 0 0
G
7/26/2019 Exmenes de Matemtica Discreta
57/105
H = (V, E)
V = V
E =
E {{10, 2}, {2, 9}}
H
H
H
H
102
7/26/2019 Exmenes de Matemtica Discreta
58/105
G=(V, E)
0 0 1 1 0 0 0 0 0 1 0 0 0 0 10 0 0 0 1 0 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 1 0 0 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 1 0 0 0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 1 0 1 00 0 0 0 0 0 0 0 1 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 1 00 0 0 0 0 0 0 0 0 0 1 0 1 0 01 0 0 1 0 0 0 0 0 0 0 0 0 0 0
4, 1, 3, 3, 2, 3, 2, 2, 2, 2, 3, 3, 2, 2, 2.
7/26/2019 Exmenes de Matemtica Discreta
59/105
(Vi, Ei)
i {1, 2, 3}
V1 = {1, 4, 3, 10, 15}, V2 = {2, 5, 6, 7, 8}, V3={9, 11, 12, 13, 14}
E1 = {{1, 3}, {1, 15}, {1, 10}, {10, 3}, {4, 3}, {15, 4}, {1, 4}}
E2={{2, 5}, {6, 5}, {6, 7}, {7, 8}, {8, 6}}
E3={{11, 9}, {11, 12}, {12, 9}, {11, 14}, {12, 13}, {13, 14}}
G
{10, 2}
{2, 9}
4, 3, 10, 1, 15, 4
11, 9, 12, 13, 14, 11
H = (V
, E
)
V
= V
E
=E {{10, 2}, {2, 9}}
H
H
7/26/2019 Exmenes de Matemtica Discreta
60/105
{6, 8}
{3, 10}
{3, 4}
{15, 4}
{9, 12}
{11, 14}
H
{6, 8}
{6, 7}
H
102
{10, 2}
{2, 5}
2 102
{2, 5}
{5, 6}
{6, 7}
{6, 8}
{7, 8}
2 102 + 102(2 102(1 102) + 104)
7/26/2019 Exmenes de Matemtica Discreta
61/105
G= (V, E)
0 1 1 1 0 0 0 0 0 1 0 0 0 1 1
1 0 0 0 1 0 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 1 0 0 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 1 1 0 0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 0 1 1 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 1 0 1 00 0 0 0 0 0 0 0 1 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 0 01 0 0 0 0 0 0 0 0 0 1 0 0 0 01 0 0 1 0 0 0 0 0 0 0 0 0 0 0
G
G
7/26/2019 Exmenes de Matemtica Discreta
62/105
G
G
n
7n
11n 1
G = (V, E)
|V| = 30
a1
an
b
p= 1
a1
an
b
p
ai, b Z
p N {1})
b
p
A
B
A:= (p q) (r s)
B:= (p r) (q s)
A
B
G = (V, E)
M
M=
0 1 0 11 0 0 10 0 0 11 1 1 0
7/26/2019 Exmenes de Matemtica Discreta
63/105
V
G
R
v, w V
vRw
G
v
w
R
M
k
7/26/2019 Exmenes de Matemtica Discreta
64/105
G= (V, E)
0 1 1 1 0 0 0 0 0 1 0 0 0 1 1
1 0 0 0 1 0 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 1 0 0 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 1 1 0 0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 0 1 1 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 1 0 1 00 0 0 0 0 0 0 0 1 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 0 01 0 0 0 0 0 0 0 0 0 1 0 0 0 01 0 0 1 0 0 0 0 0 0 0 0 0 0 0
G
G
G
7/26/2019 Exmenes de Matemtica Discreta
65/105
G
G
G
{3, 10}
{3, 4}
{4, 15}
{7, 8}
{11, 14}
{11, 12}
n
7n
11n 1
71 = 7
n= 1
7n
k
7n =2k+ 1
7n+1 = 7 7n = 7 (2k+ 1) = 2 (7k+ 3) + 1.
111 1 = 10 = 2 5
n= 1
11n 1
k
11n = 5k+ 1
11n+1 1 = 11 11n 1 = 11(5k+ 1) 1 =
11 5k+ 11 1 = 55k+ 10 = 5(11k+ 2).
G = (V, E)
|V| = 30
7/26/2019 Exmenes de Matemtica Discreta
66/105
K30
15 29
a1
an
b
p = 1
a1
an
b
p
ai, b Z
p N {1})
b
p
a1
an
b
p
j := 0
i= 1
n
ai b mod p= 0
j :=j + 1
cj :=ai
j = 0
r :=
r:= c1,...,cj
r
n
n
A
B
A:= (p q) (r s)
B:= (p r) (q s)
A
B
A
B
p, q, r, s
A
B
B
pr
q s
p
r
q
s
A
p
r
7/26/2019 Exmenes de Matemtica Discreta
67/105
q
s
A
A
G = (V, E)
M
M=
0 1 0 11 0 0 10 0 0 11 1 1 0
V
G
R
v, w V
vRw
G
v
w
R
M
M2
M2
M2
M=
2 1 1 11 2 1 11 1 1 01 1 0 3
1 1 1 11 1 1 11 1 1 01 1 0 1
1R2
2R1
3R2
2R4
7/26/2019 Exmenes de Matemtica Discreta
68/105
k
4
3
7
2
7 4 +
7
2
4
2
+
7
3
4
3
+
7
4
4
4
7
2
4
2
+
7
3
4
1
+
7
4
7
2
4
2
6 3
7/26/2019 Exmenes de Matemtica Discreta
69/105
n
5n
21n 1
G =(V, E)
7/26/2019 Exmenes de Matemtica Discreta
70/105
0 1 1 1 0 0 0 0 0 1 0 0 0 1 11 0 0 0 1 0 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 1 0 0 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 1 1 0 0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 0 1 1 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 1 0 1 00 0 0 0 0 0 0 0 1 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 0 01 0 0 0 0 0 0 0 0 0 1 0 0 0 01 0 0 1 0 0 0 0 0 0 0 0 0 0 0
G
G
G
G
G = (V, E)
|V| = 40
a1
an
b
p= 1
a1
an
b
p
ai, b Z
p N {1})
b
p
G = (V, E)
M
7/26/2019 Exmenes de Matemtica Discreta
71/105
M=
0 1 0 11 0 0 10 0 0 11 1 1 0
V
G
R
v, w V
vRw
G
v
w
R
M
A
B
A:= (t q) (u s)
B:= (t u)(q s)
A
B
k
7/26/2019 Exmenes de Matemtica Discreta
72/105
n
5n
21n 1
51 = 5
n= 1
5n
k
5n =2k+ 1
5n+1 = 5 5n = 5 (2k+ 1) = 2 (5k+ 2) + 1.
211 1 = 20 = 4 5
n= 1
21n 1
k
21n = 5k+ 1
21n+1 1 = 21 21n 1 = 21(5k+ 1) 1 =
21 5k+ 21 1 = 21 5k+ 20 = 5(21k+ 4).
G= (V, E)
7/26/2019 Exmenes de Matemtica Discreta
73/105
0 1 1 1 0 0 0 0 0 1 0 0 0 1 11 0 0 0 1 0 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 1 0 0 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 1 1 0 0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 0 1 1 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 1 0 1 00 0 0 0 0 0 0 0 1 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 0 01 0 0 0 0 0 0 0 0 0 1 0 0 0 01 0 0 1 0 0 0 0 0 0 0 0 0 0 0
G
G
G
G
G
7/26/2019 Exmenes de Matemtica Discreta
74/105
G
{3, 10}
{3, 4}
{4, 15}
{7, 8}
{11, 14}
{11, 12}
G = (V, E)
|V| = 40
K40
20 29
a1
an
b
p = 1
a1
an
b
p
ai, b Z
p N {1})
b
p
a1
an
b
p
j := 0
i= 1
n
ai b mod p= 0
j :=j + 1
cj :=ai
j = 0
r :=
r:= c1,...,cj
r
n
n
G
= (V
, E
)
M
M=
0 1 0 11 0 0 10 0 0 11 1 1 0
7/26/2019 Exmenes de Matemtica Discreta
75/105
V
G
R
v, w V
vRw
G
v
w
R
M
M2
M2
M2
M=
2 1 1 11 2 1 11 1 1 01 1 0 3
1 1 1 11 1 1 11 1 1 01 1 0 1
1R2
2R1
3R2
2R4
A
B
A:= (t q) (u s)
B:= (t u)(q s)
A
B
A
B
t,q,u,s
A
B
B
tu
q s
t
u
q
s
A
7/26/2019 Exmenes de Matemtica Discreta
76/105
t
u
q
s
A
A
k
72
7 4 +
7
2
4
2
+
7
3
4
3
+
7
4
4
4
7
2
4
4
+
7
3
4
3
+
7
4
4
2
+
7
5
4
1
+
7
6
7
2
4
2
6 3
7/26/2019 Exmenes de Matemtica Discreta
77/105
n
ni=11
i(i + 1)=
n
n+ 1
G= (V, E)
0 0 1 1 0 0 0 0 0 1 0 0 0 1 10 0 0 0 1 0 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 1 0 0 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 1 1 0 0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 0 1 1 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 1 0 1 00 0 0 0 0 0 0 0 1 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 0 11 0 0 0 0 0 0 0 0 0 1 0 0 0 01 0 0 1 0 0 0 0 0 0 0 0 1 0 0
7/26/2019 Exmenes de Matemtica Discreta
78/105
G
G
G
G
G
n
n
a
b
b >1
n= ab
A1 := (p q)A2 := (r q)A3 :=r
B:=p
A1
A2
A3
B
G = (V, E)
M
V
7/26/2019 Exmenes de Matemtica Discreta
79/105
M=
0 1 0 1 01 0 0 1 00 0 0 1 01 1 1 0 00 0 0 0 0
R
u
v
R
V/R
p= 1/3
0.8
n
n n
7/26/2019 Exmenes de Matemtica Discreta
80/105
7/26/2019 Exmenes de Matemtica Discreta
81/105
n
ni=11
i(i + 1)=
n
n+ 1
n= 1
1i=11
i(i + 1)= 1/2 = 1/(1 + 1).
n
n + 1
n+1i=11
i(i + 1)= ni=1
1
i(i + 1)+
1
(n + 1)(n+ 2).
n+1i=1 1i(i + 1)= n
n + 1+ 1
(n + 1)(n+ 2).
G= (V, E)
7/26/2019 Exmenes de Matemtica Discreta
82/105
0 0 1 1 0 0 0 0 0 1 0 0 0 1 10 0 0 0 1 0 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 1 0 0 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 1 1 0 0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 0 1 1 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 1 0 1 00 0 0 0 0 0 0 0 1 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 0 11 0 0 0 0 0 0 0 0 0 1 0 0 0 01 0 0 1 0 0 0 0 0 0 0 0 1 0 0
G
(5, 1, 3, 3, 2, 4, 2, 2, 3, 2, 3, 3, 2, 2, 3).
G
G
(5, 1, 3, 3, 2, 4, 2, 2, 3, 2, 3, 3, 2, 2, 3).
G
G
7/26/2019 Exmenes de Matemtica Discreta
83/105
(13, 15), (11, 12), (3, 4)
(3, 10), (1, 15), (6, 7).
V
V :={1, 2, 3, 4}.
E
E=
E={(1, 2)}
E={(1, 2), (1, 3)}
E={(1, 2), (4, 3)}
E={(1, 2), (1, 3), (2, 4)}
E={(1, 2), (1, 3), (1, 4)}
E={(1, 2), (1, 3), (2, 3)}
E={(1, 2), (1, 3), (2, 4), (3, 4)}
E={(1, 2), (1, 3), (2, 4), (1, 4)}
E={(1, 2), (1, 3), (2, 4), (1, 4), (3, 4)}
K4
n
n
a
b
b >1
n= ab
n
v:= 0
i = 2
n 1
n
v= 0
n mod i= 0
i:= n + 1
j :=i
j < n
j :=j j
7/26/2019 Exmenes de Matemtica Discreta
84/105
j =n
v= 1
i:= i + 1
v= 0
s:
s:=
s
i= 2
9mod 2 = 0
i= 3
9mod 3 = 0
j = 3
j
7/26/2019 Exmenes de Matemtica Discreta
85/105
p q
p
q
p q
p q
p q
G = (V, E)
M
V
M=
0 1 0 1 0
1 0 0 1 00 0 0 1 01 1 1 0 00 0 0 0 0
R
u
v
V ={1, 2, 3, 4, 5}
R:= {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (2, 1), (1, 3),(3, 1), (1, 4), (4, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3)}
R
R
a
b
b
a
a
b
b
c
a
c
I+ M+ M2 + M3 + M4
7/26/2019 Exmenes de Matemtica Discreta
86/105
1 1 1 1 01 1 1 1 01 1 1 1 01 1 1 1 00 0 0 0 1
V/R
V/R= {1, 5}.
p= 1/3
(2/3)3
1(2/3)3
0.8
n
p(n) = 1 23
n
.
p(n) 0.8
q(n) = ( 23
)n 0.2
q(1), q(2),...
n= 4
7/26/2019 Exmenes de Matemtica Discreta
87/105
7/26/2019 Exmenes de Matemtica Discreta
88/105
93
n
n n
n2
n
n
n
2n+ 2
7/26/2019 Exmenes de Matemtica Discreta
89/105
p
q
(pq)
pq
n 2
(p1 ... pn)
p1 ... pn
p1
pn
a1
an
n
Z11
Z11
234 + 2798
34128
2765 7895943021
5x + 3 7 mod 11.
7/26/2019 Exmenes de Matemtica Discreta
90/105
p
q
(p q)
p q
n 2
(p1 ...pn)
p1 ... pn
p1
pn
n= 2
p1 ... pn pn+1
(p1 ... pn) pn+1
(p1 ... pn pn+1)
((p1 ... pn) pn+1).
(p1 ... pn) pn+1.
(p1 ... pn) pn+1.
p1 ... pn pn+1.
7/26/2019 Exmenes de Matemtica Discreta
91/105
7/26/2019 Exmenes de Matemtica Discreta
92/105
234 + 2798 4 + 3 2 mod 5
34128 (1)128 1 mod 5
2765 7895943021 0 mod 5
5x 4 mod 11.
5 9 1 mod 11
x 3 mod 11.
{11k+ 3 : k Z}.
7/26/2019 Exmenes de Matemtica Discreta
93/105
n N,
2nk=1
(2k 1) = 4n2.
x 1 mod 5
x 5 mod 11x 2 mod 3,
7/26/2019 Exmenes de Matemtica Discreta
94/105
n N,
2nk=1
(2k 1) = 4n2.
n= 1,
2nk=0
(2k 1) =2
k=1
(2k 1) = 1 + 3 = 4 = 4n2.
2nk=1
(2k 1) = 4n2.
2(n+1)k=1
(2k 1) = 4(n + 1)2.
2(n+1)k=1
(2k 1) =2n+2k=1
(2k 1) =2nk=1
(2k 1)+[2(2n+1) 1]+[2(2n+2)1]
= 4n2 + (4n+ 1) + (4n + 3) = 4n2 + 8n+ 4 = 4(n+ 1)2.
n N,
2nk=1
(2k 1) = 4n2.
7/26/2019 Exmenes de Matemtica Discreta
95/105
a1, a2, a3, , an.
i n, ai
7= 4i:= i + 1
i > n
s:=
s:= ai
s
n,
n
x 1 mod 5
x 5 mod 11
x 2 mod 3,
P = 3 5 11 = 165.
x0 = 1 q1 33 + 5 q2 15 + 2 q3 55,
33 q1 1 mod 5, 15 q2 1 mod 11, 55 q3 1 mod 3,
3 q1 1 mod 5, 4 q2 1 mod 11, q3 1 mod 3.
q1 = 2, q2 = 3
q3 = 1
x0= 1 2 33 + 5 3 15 + 2 1 55 =
7/26/2019 Exmenes de Matemtica Discreta
96/105
= 66+225+110 = 66+60+110 mod 165 = 236 mod 165 = 71 mod 165.
x= 71 + 165k,
k Z.
S
S
S
S :
p(S|S) =p(S S)
p(S) .
S = {(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)}
S S = {(2, 4), (4, 2)}.
p(S|S) =p(S S)
p(S) =
2
5.
9 8 8 7 = 4032
7/26/2019 Exmenes de Matemtica Discreta
97/105
n
nk=1
(2k)3 = 2n2(n+ 1)2.
a1,
an,
a1,
an
a1,
an
7/26/2019 Exmenes de Matemtica Discreta
98/105
b
c
a1
an
a1
an
b
c
p
q
O1
O2
O3
P1
P2
P3
P4
P5
(O1, P1), (O2, P2), (O2, P4), (O2, P5), (O3, P3).
R
N7
R= {(1, 1), (2, 2), (4, 5), (3, 3), (4, 4), (5, 4), (5, 5), (6, 6),
(5, 6), (2, 3), (4, 6), (6, 5), (6, 4), (7, 7), (3, 2)}.
7/26/2019 Exmenes de Matemtica Discreta
99/105
2143 + 80100
224 2513
27
312013
G = (V, E)
A
A :=
0 1 1 0 1 1 0 01 0 1 0 1 1 0 0
1 1 0 1 1 0 0 00 0 1 0 1 0 0 01 1 1 1 0 1 1 01 1 0 0 1 0 1 00 0 0 0 1 1 0 00 0 0 0 0 0 0 0
G
G
G
G
7/26/2019 Exmenes de Matemtica Discreta
100/105
a :=
s :=
e:=
H1 := (a s),
H2:= (e s),
H3:=e.
T :=a
(H1 H2 H3) T .
a:= F, s:= F, e:= v.
7/26/2019 Exmenes de Matemtica Discreta
101/105
F
P
fF
p P
P(p, f) :=
p
f
L(p) :=
p
fFp P (P(p, f) L(p)).
fFp P (P(p, f) L(p)).
n
nk=1
(2k)3 = 2n2(n+ 1)2.
23
= 2 1 22
n+1k=1(2k)3 = nk=1(2k)
3 + 23(n + 1)3.
n+1k=1(2k)3 = 2n2(n+ 1)2 + 23(n+ 1)3.
2(n+ 1)2
2(n+ 1)2(n2 + 22(n + 1)) = 2(n+ 1)2(n + 2)2
a1,
an,
a1,
7/26/2019 Exmenes de Matemtica Discreta
102/105
an
a1,
an
a1,...,an
as:= 0
i= 1
n
s:= 0
a= ai
s:= 1
s
b
a1,...,anb1 := a1
j := 2
i= 2
n
pertenece(ai, b) = 0
bj :=ai
j :=j + 1
b
b
c
a1
an
a1
an
b
c
a1,...,an
b
cj:= 1
i= 1
n
ai mod c= 0
ai mod b= 0
bj :=ai
j :=j + 1
b
p
q
7/26/2019 Exmenes de Matemtica Discreta
103/105
7/26/2019 Exmenes de Matemtica Discreta
104/105
(5, 6), (2, 3), (4, 6), (6, 5), (6, 4), (7, 7), (3, 2)}.
R
.
(x, y)R,
(y, x) R.
(2, 3)
(3, 2)
R.
(4, 5), (5, 6) R
(4, 6)R, (4, 6), (6, 5) R
(4, 5) R,
(6, 5), (5, 4) R
(6, 4)R, (6, 4), (4, 5) R
(6, 5) R.
R
R
C1 = {1}, C2={2, 3}, C4={4, 5, 6}, C7 = {7}.
2143 + 80100 3 mod 5
224 2513 4 mod 5 3mod 5 2 mod 5
27 (22)3 2 3 mod 5
312013 343003
3 3 mod 5
G = (V, E)
A
7/26/2019 Exmenes de Matemtica Discreta
105/105
A :=
0 1 1 0 1 1 0 01 0 1 0 1 1 0 01 1 0 1 1 0 0 00 0 1 0 1 0 0 01 1 1 1 0 1 1 01 1 0 0 1 0 1 00 0 0 0 1 1 0 00 0 0 0 0 0 0 0
G
G
G
G
v5, v4, v3, v2, v1, v3, v5, v2, v6, v5, v7, v6, v1, v5