UNIVERSIDADE DO ESTADO DE SANTA CATARINA
CENTRO DE CIÊNCIAS TECNOLÓGICAS – CCT
Curso de Bacharel em Ciência da Computação
Disciplina: Matemática Discreta
Professor: Rafael Stubs Parpinelli
Lista de Exercícios 05.
1) Usando o processo de indução matemática, verifique se são verdadeiras as afirmações
abaixo para todo n ∈ N:
 3n1 n
a) 2 + 5 + 8 + ... + (3n – 1) =
,n≥1
2
n n+1 2n1
b) 12 + 22 + 32 + ... + n2 =
,n≥1
6
n
 5n−3 n
c) ∑ 5k−4  =
,n≥1
2
k= 1
n
1
1
d) ∑  k  = 1 – n , n ≥ 1
2
k= 1 2
e)
n
∏  2 k =2
2
n +n
4
,n≥1
k= 1
n
f)
∑  2k−1
g)
h)
i)
j)
20 + 21 + 22 + ... + 2n = 2n +1 – 1 , n ≥ 0
2n +1 < 3n , n ≥ 2
n2 > 3n , n ≥ 4
n2 > n + 1 , n ≥ 2
= n2 , n ≥ 1
k= 1
2) Com os números 1, 2, 3, 4 e 5 podemos formar quantas dezenas?
3) Quantas dezenas contendo dois algarismos diferentes pode-se formar com os
algarismos 1, 2, 3, 4 e 5?
4) Um número binário é uma lista de zeros e uns. Um número binário com 8 dígitos é
chamado byte.
a) Quantos bytes podem-se formar?
b) Quantos bytes começam por 10 e terminam por 01?
c) Quantos bytes começam por 10 e não terminam por 01?
5) Antônio está jogando moedas. Cada jogada resulta em cara (C) ou coroa (K).
Quantos resultados possíveis ele pode obter se jogar 5 vezes sem cair 2 caras
consecutivas? Dica: faça a árvore de decisão das jogadas.
6) Suponha que os quatro últimos dígitos de um número de telefone têm que incluir
pelo menos um dígito repetido. Quantos desses números existem?
7) Uma loja de iogurte congelado permite que você escolha um sabor (baunilha,
morango, limão, cereja ou pêssego), um acompanhamento (raspas de chocolate,
castanha de caju picada ou coco ralado) e uma cobertura (creme batido ou calda de
caramelo). Quantas sobremesas diferentes são possíveis? De quantas maneiras
diferentes uma sobremesa pode ser escolhida?
8) No exercício anterior, quantas escolhas possíveis de sobremesa você tem se for
alérgico a morango e a chocolate?
9) Começa-se um jogo de computador fazendo uma seleção em cada um de três
menus. O primeiro (número de jogadores) tem quatro opções, o segundo (nível de
dificuldade) te oito e o terceiro (velocidade) tem seis. Quantas configurações
possíveis tem o jogo?
10) Uma prova de múltipla-escolha tem 20 perguntas, cada qual com quatro respostas
possíveis, e 10 perguntas adicionais, cada uma das quais com cinco respostas
possíveis. Quantas folhas de respostas diferentes são possíveis?
11) Uma prateleira contém 20 livros. De quantas maneiras diferentes esses livros
podem ser dispostos na prateleira?
12) Uma senha de usuário para acessar um sistema computacional consiste em três
letras seguidas de dois dígitos. Quantas senhas diferentes existem?
13) A, B, C e D são nós em uma rede de computadores. Existem dois caminhos entre A
e C, dois entre B e D, três entre A e B e quatro entre C e D. Por quantas rotas
diferentes é possível mandar uma mensagem de A para D?
14) Quantos números de CPF são possíveis?
15) Na linguagem de programação BASIC original, um identificador tem que ser uma
única letra ou uma letra seguida de um único dígito. Quantos identificadores
podemos formar?
16) Três cadeiras na Câmara Municipal devem ser preenchidas com pessoas de partidos
diferentes. Para pleitear as vagas, existem quatro candidatos do partido 1, três do
partido 2 e dois do partido 3. De quantas maneiras diferentes essas vagas podem ser
preenchidas?
17) Uma promoção especial de jantar permite que você escolha entre cinco entradas,
três saladas, quatro pratos principais e três bebidas. Quantos jantares diferentes são
possíveis?
18) No exercício anterior, quantos jantares diferentes são possíveis se você pode
escolher uma entrada ou uma salada mas não ambas?
19) Em um determinado estado americano, as placas dos carros começam com dois
dígitos (o primeiro não pode ser zero), seguidos de uma letra (incluindo K, W e Y),
seguidos de uma cadeia de dois a quatro dígitos (qualquer um podendo ser zero).
Quantas placas diferentes são possíveis?
20) Considere o conjunto dos inteiros com três dígitos (números entre 100 e 999):
a.
b.
c.
d.
e.
Quantos são divisíveis por 5?
Quantos não são divisíveis por 5?
Quantos são divisíveis por 4?
Quantos são divisíveis por 4 ou 5?
Quantos são divisíveis por 4 e 5?
19) Um cliente está encomendando um computador. Ele tem as seguintes escolhas: o
monitor pode ser de 17, 19, 21 ou 23 polegadas; o processador pode ser de 1.5, 1.7, 2.0,
2.8 ou 3.3 GHz; o acionador de CD pode ser de 24, 32 ou 64 vezes; a memória RAM
pode ter 256MB, 512MB ou 1 GB; a placa de faz é opcional; a placa de som é opcional.
a. Quantas configurações diferentes são possíveis?
b. Quantas máquinas diferentes podem ser encontradas com um processador de 2.8
GHz?
c. Quantas máquinas diferentes podem ser encomendadas com um monitor de 21
polegadas mas sem placa de som e sem placa de faz?
d. Quantas máquinas diferentes podem ser encomendadas sem monitor?
20) Uma determinada votação é feita com cada pessoa colocando um pedaço de papel
rosa, branco ou verde em um chapéu. Os papéis são retirados um a um e a primeira
cor que recebe dois votos ganha a eleição. Desenhe uma árvore de decisão para
encontrar o número de maneiras em que se pode desenvolver essa votação.
21) Escreva a expressão que determina o Princípio da Inclusão e Exclusão para quatro
conjuntos: A, B, C e D.
22) Em um grupo de 42 turistas, todos falam inglês ou francês; 35 falam inglês e 18
falam francês. Quantos falam inglês e francês?
23) Para cada um dos casos a seguir, encontre |A|, |B|, |A ∩ B| e |A ∪ B|:
a. A = {a, b, c, d} e B = {e, f, g, h}
b. A = {2, 4, 6, 8} e B = {2, 3, 5, 7}
c. A = {x | x é inteiro entre 1 e 5} e B = {x | x é inteiro entre 3 e 7}
d. Se |A ∪ B| = 20, |A| = 10 e |B| = 15, encontre |A ∩ B|. Faça um diagrama.
e. Se |A ∪ B| = 10, |A| = 8 e |A ∩ B| = 4, quantos elementos tem o conjunto B?
24) Sejam A e B subconjuntos de um conjunto universo U. Sabendo-se que |U| = 60,
|A| = 32, |B| = 40 e |A ∩ B| = 23, encontre:
a. |A ∪ B|
b. |U − |A ∪ B| |
c. |A'|
d. |A' ∩ B'|
e. |B'|
f. |A' ∩ B|
g. |A' ∪ B'|
25)Todos os convidados em um jantar bebem café ou chá; 13 bebem café, 10 bebem
chá e 4 bebem tanto café quanto chá. Quantas pessoas há nesse grupo?
26) Em um grupo de 24 pessoas que gostam de rock, música sertaneja ou música
clássica, 14 gostam de rock, 17 de música clássica, 11 de rock e música sertaneja, 9
de rock e música clássica, 13 de música clássica e música sertaneja e 8 gostam dos
três tipos de música. Quantas gostam de música sertaneja?
27) Dezenove produtos diferentes para bochechar anunciam as seguintes propriedades:
12 afirmam que refrescam o hálito, 10 que previnem gengivite, 11 afirmam que
reduzem a formação de placas, 6 afirmam que refrescam o hálito e reduzem a
formação de placas, 5 anunciam que previnem gengivite e refrescam o hálito e 5
dizem que previnem gengivite e reduzem a formação de placas.
a. Quantos produtos anunciam que têm todas as três propriedades?
b. Quantos produtos dizem que refrescam o hálito mas não afirmam reduzir a
formação de placas?
26) Quantas cartas devem ser retiradas de um baralho padrão com 52 cartas para se
obter, com certeza, duas cartas do mesmo naipe?
27) Se 12 cartas forem retiradas de um baralho padrão, pelo menos duas delas devem
ser do mesmo naipe?
28) Prove que, se quatro números forem escolhidos do conjunto {1, 2, 3, 4, 5, 6}, pelo
menos um par tem que somar 7. (Dica: encontre todos os pares de número do
conjunto que some 7.)
29) Em um grupo de 25 pessoas, é verdade que existem pelo menos 3 pessoas que
nasceram no mesmo mês?