Lista Matemática Discreta

Prévia do material em texto

2017.2 CB 0661 - MATEMÁTICA DISCRETA (PROF. FABRICIO)
LISTA 2 (09/10/2017)
Cada
√
denota um nível de dificuldade:
√
fácil,
√√
médio e
√√√
difícil.
1.(
√
) Prove ou desprove:
(a) Se f : A→ A e g : A→ A são duas funções, então f ◦ g 6= g ◦ f .
(b) Se f é uma função, então f ◦ f−1 é também uma função.
(c) Se f : A→ A é bijetora, então f ◦ f−1 = {(a, a) | a ∈ A} (ou seja, f ◦ f−1 é a função identidade).
(d) Se f , g e h são funções, então (f ◦ g) ◦ h = f ◦ (g ◦ h).
2.(
√√
) Prove que os seguintes conjuntos são infinitos enumeráveis.
(a) O conjunto de todos os números inteiros pares.
(b) O conjunto dos números racionais.
(c) A união de k conjuntos infinitos enumeráveis A1, · · · , Ak.
3.(
√√
) Prove que o conjunto dos números reais entre 0 e 1 é infinito não enumerável.
4.(
√√√
) Construa uma bijeção entre os seguintes conjuntos:
(a) R e R− {0}.
(b) R e (−1, 1).
(c) [−1, 1] e (−1, 1).
5.(
√
) Para cada conjunto abaixo, dê um argumento para mostrar se o conjunto é finito ou infinito enumerável
ou infinito não enumerável.
(a) A = {n7 : n ∈ N}
(b) B = {n109 : n ∈ N}
(c) A ∪B
(d) A ∩B
(e) A×B
6.(
√
) Prove por indução que se k ∈ N e k ≥ 64, então existem a ∈ N e b ∈ N tais que k = 5a+ 17b.
7.(
√
) Mostre, por indução em k, que se k ∈ N, então k(k + 1)(k + 2) é divisível por 3.
8.(
√√√
) Mostre que se n ∈ N− {0} é uma potência de 2 (n = 2k, para algum k ∈ N), e uma função T : N→ R é tal
que
T (1) = 0
T (n) = T (n/2) + 1, n > 1,
então T (n) = log n (logaritmo na base 2), para todo n potência de 2.
9.(
√√
) Seja F : N → N o número de Fibonacci, onde que F (0) = 0, F (1) = 1 e F (n) = F (n − 1) + F (n − 2) para
n ≥ 2. Mostre, por indução em n, que
F (n) =
1√
5
{(
1 +
√
5
2
)n
−
(
1−√5
2
)n}
10.(
√√
) Prove, de forma combinatória, que, se n > 0, então:(
n
0
)
−
(
n
1
)
+
(
n
2
)
−
(
n
3
)
+ · · · ±
(
n
n
)
= 0
1
11.(
√√√
) Prove, de forma combinatória, que se n ≥ k ≥ m ≥ 0 são inteiros, então:(
n
k
)(
k
m
)
=
(
n
m
)(
n−m
k −m
)
12.(
√
) Sejam A, B e C conjuntos finitos. Prove ou refute: se |A ∪B ∪ C| = |A|+ |B|+ |C|, então A, B e C devem
ser disjuntos dois a dois.
13.(
√√
) Quantos números de seis algarismos não tem três algarismos consecutivos iguais? Argumente sua re-
sposta.
14.(
√
) Há quatro grandes grupos de pessoas, cada um com mil membros. Dois quaisquer desses grupos tem cem
membros em comum. Três quaisquer desses grupos têm dez membros em comum. E há uma pessoa em
todos os quatro grupos. Quantas pessoas há no total?
15.(
√√√
) Considere um grupo com n pessoas. Prove que:
(a) Existem duas pessoas que possuem a mesma quantidade de amigos no grupo.
(b) Para que toda pessoa possa conhecer indiretamente todas as outras (x conhece alguém, que conhece
alguém, que conhece alguém, etc, que conhece y, para todo par de pessoas x e y), é preciso que existam
ao menos n− 1 laços de amizade.
2