GAN 00167 – Matemática Discreta
Professores Renata de Freitas e Petrucio Viana
Lista C
1. Um pacote de livros consiste de dois livros, cada um sobre uma matéria diferente.
(a) Se uma pessoa possui cinco livros diferentes de Matemática e sete livros
diferentes de Fı́sica, quantos pacotes diferentes ela pode formar?
(b) Se uma pessoa possui cinco livros diferentes de Matemática, sete livros
diferentes de Fı́sica e nove livros diferentes de Teoria da Computação,
quantos pacotes diferentes ela pode formar?
2. Dado um conjunto de homens e um conjunto de mulheres, ambos os conjuntos
com o mesmo número de elementos, uma quadrilha de festa junina consiste de
um conjunto de pares, tal que: (i) cada par é formado por um homem e uma
mulher; (ii) cada homem e cada mulher está em um único par. Determine, sem
listá-las, quantas quadrilhas de festa junina podem ser formadas se dispomos
de doze homens e doze mulheres.
3. Uma comissão é um conjunto de pessoas formado por três homens e três
mulheres.
(a) Se dispomos de oito homens e cinco mulheres, quantas comissões podem
ser formadas?
(b) Se dispomos de quinze homens e dez mulheres, dentre os quais estão
Renata e Marcelo, quantas comissões podem ser formadas, dado que ou
Renata está na comissão, ou Marcelo está na comissão, ou ambos Renata
e Marcelo estão na comissão?
4. Quantos numerais de cinco ou seis algarismos significativos podem ser formados com os algarismos 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9, sendo que os de cinco
algarismos representam números pares e os de seis algarismos representam
números ı́mpares?
5. Uma moeda é lançada vinte vezes. Um registro é uma anotação da sequência
de resultados (cara ou coroa) obtidos. Determine quantos registros existem
nos quais o número de caras é igual ao número de coroas.
6. Uma classificação de uma corrida com dez participantes é uma anotação da
ordem em que eles cruzam a linha de chegada. Se todos cruzam a linha de
chegada, determine quantas classificações são possı́veis:
(a) Se não ocorre empate em nenhuma das posições;
(b) Se três participantes chegam empatados na segunda posição e não ocorre
empate em nenhuma das outras posições.
7. Um baralho comum consiste de 52 cartas particionadas em quatro naipes:
♥ (copas), ♠ (espadas), ♦ (ouros) e ♣ (paus). Cada naipe consiste de 13
cartas: os números 2, 3, 4, 5, 6, 7, 8, 9, 10 e as figuras J (valete), Q (dama), K
(rei) e A (ás). Uma extração consiste de três cartas retiradas de um baralho
comum, sucessivamente e sem reposição. Quantas extrações existem nas quais
a primeira carta é de ♦ e a segunda é um 7?
8. Prove que os seguintes conjuntos são enumeráveis.
(a) N∗ ∪ {b}
(b) N∗ ∪ {a1 , a2 }
(c) N∗ ∪ {p1 , p2 , p3 }
(d) N∗ ∪ {c1 , c2 , . . . , cn }
(e) N∗ ∪ {h1 , h2 , . . . , hn , . . .} = N ∪ {hi : i ∈ N∗ }
(f) N∗ ∪ {hi : i ∈ N∗ } ∪ {gj : j ∈ N∗ }
(g) N∗ ∪ Z
(h) Z
(i) N∗ ∪ {hi : i ∈ N∗ } ∪ {gj : j ∈ N∗ } ∪ {fk : k ∈ N∗ }
(j) N∗ ∪ {h1 i : i ∈ N∗ } ∪ {h2 i : i ∈ N∗ } ∪ · · · ∪ {hm i : i ∈ N∗ }
(k) N∗ ∪ {h1 i : i ∈ N∗ } ∪ {h2 i : i ∈ N∗ } ∪ · · · ∪ {hm i : i ∈ N∗ } ∪ · · ·
(l) N∗ ∪ Q
(m) Q
9. Sabendo que #N < R e que #A ≤ #B quando existe uma função injetiva
f : A → B, prove que os conjuntos a seguir não são enumeráveis.
(a) I = {x ∈ R : x é irracional}
(b) (0, 1) = {x ∈ R : 0 < x < 1}
(c) R × R
(d) C
2