Lista 7 - Matemática Discreta - 2014/01
Combinatória
1. Com os números 1, 2, 3, 4 e 5 podemos formar quantas dezenas? R:25
2. Quantas dezenas contendo dois algarismos diferentes pode-se formar com os algarismos 1, 2, 3, 4 e
5? R: 20
3. 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? R: 256
(b) Quantos bytes começam por 10 e terminam por 01? R: 16
(c) Quantos bytes começam por 10 e não terminam por 01? R: 48
4. 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? R: 13
Dica: faça a árvore de decisão das jogadas.
5. 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? R: 30, 90.
6. No exercı́cio anterior, quantas escolhas possı́veis de sobremesa você tem se for alérgico a morango e
a chocolate? R: 16
7. 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) tem oito e o terceiro
(velocidade) tem seis. Quantas configurações possı́veis tem o jogo? R: 192
8. 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?
9. Uma prateleira contém 20 livros. De quantas maneiras diferentes esses livros podem ser dispostos na
prateleira? R: 20!
10. Uma senha de usuário para acessar um sistema computacional consiste em três letras seguidas de
dois dı́gitos. Quantas senhas diferentes existem? R: 1757600
11. 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?
12. Quantos números de CPF são possı́veis? R: 91 0
13. 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? R: 286
14. 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?
15. 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? R: 180
16. No exercı́cio anterior, quantos jantares diferentes são possı́veis se você pode escolher uma entrada ou
uma salada, mas não ambas?
17. Em um determinado estado americano, as placas dos carros começam com dois dı́gitos (o primeiro não
1
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? R: 25.974.000
18. Considere o conjunto dos inteiros com três dı́gitos:
(a) Quantos são divisı́veis por 5? R: 180
(b) Quantos não são divisı́veis por 5? R: 720
(c) Quantos são divisı́veis por 4? R: 225
(d) Quantos são divisı́veis por 4 e 5? R: 54
(e) Quantos são divisı́veis por 4 ou 5? R: 351
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. R: 33
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. 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 3e7}.
(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?
23. 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 ′ |
24. 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? R: 11
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? R: 19
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
2
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?
28. Quantas cartas devem ser retiradas de um baralho padrão com 52 cartas para se obter, com certeza,
duas cartas do mesmo naipe?
29. Se 12 cartas forem retiradas de um baralho padrão, pelo menos duas delas devem ser do mesmo
naipe?
30. 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.)
31. Em um grupo de 25 pessoas, é verdade que existem pelo menos 3 pessoas que nasceram no mesmo
mês?
32. Num setor de uma consultoria de informática tem 30 programadores: 12 desses programam em Java,
7 em C++ e 3 em ambas as linguagens. Quantos desses programadores não trabalham nem com Java
e nem com C++?
33. Numa empresa com 40 funcionários, sabe-se que 25 um salário mensal menor que R$ 3.500,00 e que
20 tem um salário superior à R$ 1.600,00. Quantos funcionários desta empresa:
(a) Recebem entre R$ 1.600,00 e R$ 3.500,00?
(b) Quantos recebem menos de R$ 1.600,00?
(c) Quantos recebem mais de R$ 3.500,00?
34. Num setor de uma consultoria de informática tem 30 programadores: 1 nas três linguagens, 12 desses
programam em Java, 7 em C++, 3 em Java e C++ e 7 programadores em PHP, desses 2 programam
em C++ e outros 2 em Java. Quantos desse programadores trabalham com Java ou C++, ou ainda,
PHP?
35. O controle de qualidade em uma fábrica retirou 40 peças de uma linha de produção com defeitos
na pintura, na embalagem ou na parte elétrica. Dentre essas peças, 28 tinham defeito na pintura,
17 tinham a embalagem defeituosa, 13 tinham defeitos na parte elétrica, 6 tinham tanto na pintura
quanto na embalagem, 7 tinham defeitos de embalagem e na parte elétrica e 10 tinham defeito na
pintura e na parte elétrica. Alguma peça tinha todos os três tipos de defeito?
36. Entre os 214 clientes de um banco que têm conta corrente ou poupança, 189 têm conta corrente, 73
têm poupança normal, 114 têm poupança multidata e 69 têm tanto conta corrente quanto poupança
normal. Não é permitido a um cliente ter o mesmo tempo poupança normal e poupança multidata.
(a) Quantos clientes têm conta corrente e poupança multidata?
(b) Quantos clientes têm conta corrente, mas não têm poupança?
37. Uma pesquisa entre 150 alunos de faculdades revelam que 83 têm carros, 97 têm bicicleta, 28 têm
motocicletas, 53 têm carro e bicicleta, 14 têm carro e moto, 7 têm bicicleta e moto e 2 têm todos os
três.
(a) Quantos estudantes têm apenas uma bicicleta?
(b) Quantos estudantes não têm nenhum dos três?
38. Uma Pesquisa a respeito do preferencia de filmes foi realizada num grupo de 1200 pessoas. Todos
os entrevistados afirmaram que preferem ao menos uma das seguintes categorias: ação (A), comédia
(C), drama (D) ou suspense (S). Foram coletados os seguintes dados:
|A| = |S|,
|C| = |D|,
3
|D| = 2|A|,
|A ∩ C| = |A ∩ D| = |A ∩ S| = |C ∩ D| = |C ∩ S| = |D ∩ S|
|A ∩ C ∩ D| = |A ∩ C ∩ S| = |A ∩ D ∩ S| = |C ∩ D ∩ S|.
Sabendo-se que a metade dos entrevistados que preferem filmes de ação afirmam que também gostam
de filmes de comédia, que os que preferem filmes de comédia, drama e ação é igual à um quarto dos
que gostam de suspense e que 4% dos entrevistados gostam das quatro categorias citadas, determine
o número de entrevistados que preferem filmes:
(a) de suspense;
(b) de comédia;
(c) de drama e suspense;
(d) de ação, comédia e drama;
(e) apenas de ação;
(f) de comédia e drama, mas não de ação;
(g) de drama ou suspense, mas não de comédia.
39. Um saco contém contas de duas cores: branca e preta. Qual o menor número de contas que precisam
ser retiradas do saco, sem olhar, de modo que possamos garantir que duas das contas retiradas sejam
da mesma cor?
40. Uma floresta tem um milhão de pinheiros. Sabe-se que nenhum pinheiro tem mais de 600.000 espinhos.
Mostre que pelo menos dois dos pinheiros na floresta têm que ter o mesmo número de espinhos.
41. A cidade de Leningrado tem cinco milhões de habitantes. Sabendo que nenhuma pessoa tem mais
de um milhão de cabelos em sua cabeça, mostre que pelo menos dois dos habitantes têm que ter o
mesmo número de cabelos em suas cabeças.
42. Vinte e cinco engradados de maçãs foram entregues em uma loja. As maçãs são de três tipos
diferentes, mas todas as maçãs em cada engradado são do mesmo tipo. Mostre que pelo menos
nove dos engradados contêm o mesmo tipo de maçãs.
43. Dados 11 números naturais diferentes, nenhum maior do que 20, prove que podemos escolher dois
deles tais que um divide o outro.
44. Cinquenta e um pontos estão espalhados dentro de um quadrado com 1 metro de lado. Prove que
algum conjunto contendo três desses pontos pode ser coberto por um quadrado com 20 centı́metros
de lado.
45. Dados doze inteiros, mostre que é possı́vel escolher dois deles de modo que sua diferença seja divisı́vel
por 11.
46. Prove que podemos escolher um subconjunto de um conjunto de dez inteiros dados tal que a soma
de seus elementos é divisı́vel por 10.
47. Quinze meninos juntaram 100 nozes. Prove que dois deles juntaram o mesmo número de nozes.
4