APÓSTILA DE MATEMÁTICA DISCRETA

Prévia do material em texto

FUNDAMENTOS DE
 MATEMÁTICA DISCRETA
 
 G E O R G E C A B R A L M OURÃO
 PRINCÍPIOS DA MULTIPLICAÇÃO E DA ADIÇÃO
1. Princípio da multiplicação
 Se existem resultados possíveis para um primeiro evento e para um segundo, então existem ·. resultados possíveis para a sequência dos dois eventos.
Veja:
 Uma criança pode escolher uma entre duas balas, uma rosa e uma preta e um entre três chicletes, um amarelo, um verde e um branco. Quantos conjuntos diferentes a criança pode ter?
2. Princípio da Adição
 Se A e B são eventos diferentes com e resultados possíveis, respectivamente, então o número total de possibilidades para o evento “A ou B” é + .
Veja:
 Um consumidor deseja comprar um veículo de uma concessionária. A concessionária tem 25 automóveis e 17 caminhões em estoque. Quantas escolhas possíveis o consumidor tem?
 
 01
 EXERCÍCIOS
01. Quantos números naturais de três algarismos podem ser formados com os algarismos 1, 2, 6, 8 e 9?
02. Quantos números naturais de três algarismos distintos podem ser formados com os algarismos 1, 2, 6, 8 e 9?
03. Quantos números naturais de quatro algarismos distintos podem ser formados com os algarismos 0, 1, 2, 6, 8 e 9?
04. Duas linhas de ônibus vão de uma cidade A para uma cidade B e três linhas vão da cidade B para uma cidade C. De quantos modos diferentes um usuário dessas linhas pode ir de A para C, passando por B?
05. Quantos números naturais de quatro algarismos distintos podem ser formados com os algarismos 0, 3, 4, 5, 6, 7, 8 e 9?
 06. Oito atletas participam de uma corrida. Serão premiados apenas os três primeiros lugares. De quantas maneiras diferentes os 	prêmios podem ser distribuídos?
07. 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?
08. No exercício 07, quantas escolhas possíveis de sobremesa você tem se for alérgico a morango e a chocolate?
09. Uma senha de usuário para acessar um sistema computacional consiste em três letras seguidas de dois dígitos. Quantas senhas diferentes existem? 
010. No sistema computacional do exercício anterior, quantas senhas existem se for possível distinguir entre letras maiúsculas e minúsculas?
011. 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 pode-se mandar uma mensagem de A para D?
012. Quantos números de três dígitos menores do que 600 podem ser formados usando-se os algarismos 8, 6, 4 e 2? 02
013. Um prédio comprou um novo sistema de fechaduras para seus 175 apartamentos. Uma fechadura é aberta digitando-se um código de dois algarismos. O síndico do edifício fez uma compra inteligente?
 14. Um palíndromo é uma cadeia de caracteres que é lida da mesma forma normalmente ou de trás para frente. Quantos palíndromos de cinco letras são possíveis na língua portuguesa?
 
 15. Pode-se encomendar um carro novo com as seguintes opções de escolha: 10 cores externas; 7 cores internas; transmissão automática, com 3 marchas ou com 5 marchas; com ou sem ar condicionado; com ou sem direção hidráulica; com ou sem o pacote adicional que inclui trava elétrica das portas e desembaçador traseiro. Quantos carros diferentes podem ser encomendados? 
 
 03
 PRINCÍPIO DAS CASAS DE POMBO
 Se mais de K itens são colocados em K caixas, então pelo menos uma caixa contém mais de um item.
Ex. 1) Quantas pessoas têm que estar presentes em uma sala para garantir que duas têm o último nome começando com a mesma letra?
Ex. 2) Quantas vezes é preciso jogar um dado de modo a garantir que um mesmo valor apareça duas vezes?
 PERMUTAÇÃO
 Um arranjo ordenado de objetos é chamado de permutação: = n!
Ex.1) De quantas maneiras diferentes seis pessoas podem formar uma fila indiana?
Ex. 2) De quantas maneiras diferentes podemos dispor numa mesma prateleira de uma estante, cinco livros de discreta e quatro de física, de modo que livros da mesma matéria permaneçam juntos?
 
Ex. 3) Com a palavra DISCRETA:
a) Quantos anagramas podemos formar?
b) Quantos anagramas começam por T?
c) Quantos anagramas começam por S e terminam por D? 
d) Quantos anagramas começam por vogal?
e) Quantos anagramas terminam por consoante?
f) Quantos anagramas começam por vogal e terminam por consoante?
g) Quantos anagramas começam por vogal ou terminam por consoante?
h) Quantos anagramas apresentam as letras C, R e E juntas e nessa ordem?
i) Quantos anagramas apresentam as letras C, R e E juntas?
Em geral, é dado pela fórmula
 = 
 04
Ex. 1) Quantas palavras de quatro letras ( que podem não fazer sentido) podem ser formadas a partir da palavra “DISCRETA” se nenhuma letra pode ser repetida?
Ex.2) Em um campeonato de futebol, participam 15 equipes. Quantos resultados são possíveis para os três primeiros lugares?
PERMUTAÇÃO COM ELEMENTOS REPETIDOS
A permutação com elementos repetidos é dada pela fórmula
 
Ex. 1) Determinar o número de anagramas da palavra MATEMATICA.
Ex. 2) Determinar o número de anagramas da palavra MATEMATICA que começam pela letra T.
 
PERMUTAÇÕES CIRCULARES
Utilizamos a fórmula: 
Ex. De quantas formas nove crianças podem formar uma roda?
 05
 EXERCÍCIOS
01. Calcule o valor das expressões a seguir:
 a) P(7,2) b) P(8,5) c) P(6,4) d) P(n, n-1) 
02. De quantas maneiras diferentes podemos ordenar 9 objetos?
03. Os 14 times locais de futebol júnior estão listados no jornal. Quantas listas são possíveis?
04. Quantas permutações das letras na palavra COMPÚTAR existem? Quantas delas terminam com uma vogal?
05.Num ônibus há exatamente cinco lugares vagos. Os próximos cinco passageiros que embarcarem poderão ocupar esses lugares vagos de quantas maneiras diferentes?
06. De quantos modos diferentes podemos dispor quatro livros de matemática, três de história e dois de geografia numa mesma prateleira de uma estante de modo que livros de mesma matéria permaneçam juntos?
07. De quantos modos podemos dispor cinco meninas e quatro meninos em fila indiana de modo que crianças de mesmo sexo não fiquem juntas?
08. Quantos números podemos obter permutando apenas os algarismos pares do número 32456 e mantendo os algarismos ímpares em suas respectivas posições?
09. Quantos números naturais de cinco algarismos distintos podemos formar com os algarismos 1, 2, 3, 4 e 5 de modo que os algarismos ímpares permaneçam sempre juntos?
10. Com a palavra EDITORA:
 a) quantos anagramas podemos formar?
 b) quantos anagramas começampela letra T?
 c) quantos anagramas começam pela sílaba TO?
 d) quantos anagramas começam por vogal?
 e) quantos anagramas terminam por consoante?
 f) quantos anagramas começam por vogal e terminam por consoante?
 g) quantos anagramas começam por vogal ou terminam por consoante? 
 h) quantos anagramas apresentam as letras E, D e T juntas e nessa ordem?
 i) quantos anagramas apresentam as letras E, D e T juntas?
 j) quantos anagramas não apresentam as letras E, D e T juntas?
 06
11. Determine o número de anagramas da palavra VIOLINO.
12. Qual é o número de anagramas da palavra BANANA?
13. Obtenha o número de anagramas da palavra TAMPA. 
14. Quantas permutações distintas existem das letras na palavra HAVAIANO? Quantas delas começam com H?
15. Quantas permutações distintas existem das letras na palavra APALACHICOLA? Quantas delas têm os dois Ls juntos?
16. Uma livraria tem uma prateleira onde estão expostos cinco, três e quatro exemplares, respectivamente, dos três livros mais vendidos. Quantos arranjos diferentes desses livros podem ser feitos se livros com mesmo título não são distinguíveis?
 
 07
 EXERCÍCIOS
01. Com os algarismos 2, 3, 4, 5 e 6, desejamos formar números de 3 algarismos.
 a) Quantos números podemos formar?
 b) Quantos números de algarismos distintos podemos formar?
 c) Quantos números pares de algarismos distintos podemos formar? 
02. Quantos números ímpares de quatro algarismos distintos podemos formar com os algarismos 0, 1, 2, 3, 5, 6 e 7?
03. Quantos são os números pares de três algarismos distintos que podem ser formados com os algarismos 0, 1, 4, 6 e 7?
04. Com os algarismos 1, 2, 5, 7, 8 e 9, deseja-se formar números de 3 algarismos. 
 a) Quantos números podem ser formados?
 b) Quantos deles são ímpares? 
 c) Quantos dos números formados possuem algarismos distintos?
 d) Quantos são os números ímpares formados com algarismos distintos?
05. Com os algarismos 0, 1, 2, 3, 4, 5 e 7, deseja-se formar números de 4 algarismos.
 a) Quantos são esses números?
 b) Quantos desses números são pares?
 c) Quantos desses números são ímpares?
 d) Quantos são os números formados por algarismos distintos?
 e) Quantos são os números pares formados por algarismos distintos? 
 f) Quantos são os múltiplos de 10, formados por algarismos distintos?
06. Quantos são os anagramas da palavra MARTE? 
07. Dada a palavra PEROBA, vamos determinar o número de anagramas que têm as letras E, R, O:
 a) sempre juntas e nessa ordem.
 b) sempre juntas.
08. Quantos são os anagramas da palavra FÓRMULA?
09. Dada a palavra CONTAGEM, pede-se:
 a) quantos são os anagramas que começam pela letra C?
 b) quantos são os anagramas que começam por C e terminam por M? 
 c) quantos são os anagramas que possuem as letras N, T, A juntas e nessa ordem?
 d) quantos são os anagramas que têm as letras N, T, A juntas? 08
10. Em quantos anagramas da palavra ENGLOBAR pode ser lida a palavra:
 a) BOLA? b) GOL?
11. Em um sistema de emplacamento de veículos, as placas são iniciadas com 2 vogais seguidas de 3 dígitos. Qual é o número máximo de veículos que pode ser licenciado nesse sistema?
12. Com os algarismos 0, 1, 3, 4, 5, 6 e 9, quantos números pares de 4 algarismos distintos podemos formar?
13. Com os algarismos 1, 2, 3, 4, 5, 6 e 7, quantos números de 4 algarismos distintos podemos escrever?
14. Quantos números de 4 algarismos distintos podemos formar com os algarismos 0, 1, 2, 4, 5, 6 e 7?
15. Com os algarismos 3, 5, 6, 7, 8 e 9, quantos números ímpares de 3 algarismos distintos podemos formar?
16. Calcular o número de anagramas da palavra FLORESTA.
17. Calcular os anagramas da palavra CAPÍTULO, que não têm 2 vogais juntas.
18. Com os algarismos 3, 4, 5, 6 e 7, pergunta-se:
 a) quantos números de 5 algarismos distintos podemos formar?
 b) quantos números ímpares de 5 algarismos distintos podemos formar?
 c) quantos números pares de 5 algarismos distintos podemos formar?
 d) quantos números de algarismos distintos maiores que 40.000 podemos formar?
19. Quantos são os anagramas da palavra PORTUGAL?
20. Quantos são os anagramas da palavra MÉDICO que não têm 2 vogais juntas?
21. Quantos são os anagramas da palavra EDITORA que não têm 2 vogais juntas?
22. Quantos números de 6 algarismos podemos escrever, utilizando os algarismos 2, 2, 3, 3, 3 e 4?
23. Quantos são os anagramas da palavra PROFESSOR? 
 09
24. Uma firma deseja contratar 6 homens e 3 rapazes. De quantas maneiras pode fazer a seleção, se tem disponível 9 homens e 5 rapazes?
25. De quantos modos diferentes se podem organizar, em um fila de 12 cadeiras, 5 brasileiros, 4 italianos e 3 alemães, de modo que as pessoas de mesma nacionalidade fiquem sempre juntas?
 10 
 C O M B I N A Ç Ã O
 Algumas vezes queremos selecionar r objetos de um conjunto de n objetos, mas não nos importamos com a ordem. Nesse caso estamos contando o número de combinações de r objetos distintos escolhidos entre n objetos distintos, que denotaremos por . Para cada uma dessas combinações, existem r maneiras de ordenar os r objetos escolhidos. Pelo princípio da multiplicação, o número de permutações de r objetos distintos escolhidos entre n objetos é o produto do número de escolhas possíveis dos objetos, pelo número de maneiras de ordenar os objetos escolhidos, r. Logo,
 ou 
Ex.1) Numa sessão em que estão presentes 12 senadores, cinco serão escolhidos para uma comissão que vai estudar um projeto do governo. De quantos modos diferentes poderá ser formada a comissão?
Ex.2) De uma novela participam seis atores e oito atrizes. Para uma cena que será filmada na Alemanha, apenas sete participantes deverão viajar, sendo dois atores e cinco atrizes. De quantos modos podem ser escolhidos os participantes desta cena?
Ex.3) Oito clubes de futebol disputaram um campeonato em dois turnos. No final, dois clubes empataram na primeira colocação, havendo mais um jogo de desempate. Quantos jogos foram disputados?
Ex. 4) De quantas formas podemos escolher cinco cartas de um baralho de 52 cartas, sem levar em conta a ordem delas, de modo que em cada escolha haja pelo menos um rei? 
 
 11
 
 EXERCÍCIOS
1. Calcule o valor das expressões a seguir:
 a) C(10,7) b) C(9,2) c) C(8,6) d) C(n, n-1)
2. O controle de qualidade quer verificar 25 processadores dos 300 produzidos por dia. De quantas maneiras isso pode ser feito?
3. Um time de futebol tem 18 jogadores entre titulares (11) e reservas. De quantas maneiras pode-se escolher o time titular?
4. De quantas maneiras pode-se selecionar um júri de 5 homens e 7 mulheres em um conjunto de 17 homens e 23 mulheres?
5. De quantas maneiras uma bibliotecária pode selecionar 4 romances e 3 peças teatrais em uma coleção de 21 romances e 11 peças?
 Os exercícios 6 a 9 tratam da seguinte situação: entreos funcionários de uma companhia, 7 trabalham em projeto, 14 em produção, 4 em testes, 5 em vendas, 2 em contabilidade e 3 em marketing. Deve-se formar uma comissão de seis pessoas para se encontrar com a diretoria.
6. De quantas maneiras pode-se formar uma comissão se deve haver um membro de cada departamento?
7. De quantas maneiras pode-se formar uma comissão se deve haver exatamente duas pessoas da área de produção?
8. De quantas maneiras pode-se formar uma comissão se o departamento de contabilidade não deve ser representado e o de marketing deve ter exatamente um representante?
9. De quantas maneiras pode-se formar uma comissão se a produção deve ter pelo menos dois representantes?
 
 12 
 EXERCÍCIOS
 Os exercícios 01 a 13 estão relacionados a mãos de 5 cartas retiradas de um baralho comum com 52 cartas.
01. Quantas mãos contêm quatro damas?
02. Quantas mãos contêm três cartas de espadas e duas de copas?
03. Quantas mãos contêm apenas cartas de ouro?
04. Quantas mãos contêm cartas de todos os quatro naipes?
05. Quantas mãos contêm apenas figuras?
06. Quantas mãos contêm um par (isto é, exatamente duas cartas do mesmo tipo)?
07. Quantas mãos contêm uma trinca (isto é, exatamente três cartas do mesmo tipo mais duas cartas que não formam um par)?
08. Quantas mãos contêm uma seqüência (isto é, cinco cartas consecutivas, por exemplo, ás, 2, 3, 4, 5 ou 10, valete, dama, rei, ás – os ases podem ser colocados no início ou no final)?
09. Quantas mãos contêm um flush (isto é, cinco cartas do mesmo naipe)?
10. Quantas mãos contêm uma trinca e um par?
11. Quantas mãos contêm quatro cartas do mesmo tipo?
12. Quantas mãos contêm uma seqüência do mesmo naipe (cinco cartas consecutivas, por exemplo, ás, 2, 3, 4, 5, do mesmo naipe)?
13. Quantas mãos contêm uma seqüência real (isto é, uma seqüência com 10, valete, dama, rei e ás do mesmo naipe)?
 Nos exercícios 14 a 18, 14 cópias de um módulo de código vão ser executadas paralelamente em processadores idênticos, organizados em dois grupos que se comunicam, A e B. O grupo A contém 16 processadores, e o grupo B, 32.
 13
14. Encontre o número de maneiras de se escolher os processadores.
15. Encontre o número de maneiras de se escolher os processadores se todos os módulos têm que ser executados no grupo B.
16. Encontre o número de maneiras de se escolher os processadores se 8 módulos devem ser processados no grupo A e 6 no grupo B.
17. Encontre o número de maneiras de se escolher os processadores se o grupo A tem 3 processadores ruins e o grupo B tem 2.
18. Encontre o número de maneiras de se escolher os processadores se exatamente dois módulos devem ser processados no grupo B.
 
 Nos exercícios 19 a 22, um conjunto de quatro moedas é selecionado de uma caixa contendo cinco moedas de dez centavos e sete moedas de vinte e cinco centavos.
19. Encontre o número de conjuntos de quatro moedas.
20. Encontre o número de conjuntos nos quais duas moedas são de dez centavos e duas são de vinte e cinco centavos.
21. Encontre o número de conjuntos compostos apenas de moedas de dez centavos ou apenas de moedas de vinte e cinco centavos.
22. Encontre o número de conjuntos com três ou mais moedas de vinte e cinco centavos.
 Os exercícios 23 a 26 se referem a uma rede de computadores com 60 nós.
23. A rede é projetada para continuar funcionando se dois dos nós falharem. De quantas maneiras pode ocorrer uma dessas falhas?
24. De quantas maneiras um ou dois nós podem falhar?
25. Se um dos nós falhar, de quantas maneiras pode-se selecionar sete nós sem que se encontre o nó que não funciona?
26. Se dois nós falharem, de quantas maneiras pode-se selecionar sete nós de modo a encontrar exatamente um dos nós que não funciona?
 14
 Nos exercícios 27 a 30, deve-se formar uma comissão com três pessoas escolhidas entre cinco pessoas pertencentes a partidos que apóiam o governo, três que pertencem a partidos de oposição e quatro que pertencem a partidos independentes.
27. De quantas maneiras pode-se escolher essa comissão?
28. De quantas maneiras pode-se escolher essa comissão se ela deve incluir pela menos uma pessoa pertencente a um partido independente?
29. De quantas maneiras pode-se escolher essa comissão se ela não pode incluir ao mesmo tempo pessoas pertencentes a partidos que apóiam o governo e pessoas de partidos da oposição?
30. De quantas maneiras pode-se escolher essa comissão se ela deve incluir pelo menos uma pessoa pertencente a um partido que apóia o governo e pelo menos uma pessoa de partido da oposição?
 Nos exercícios 31 a 34, uma anfitriã deseja convidar 6 pessoas para jantar de uma lista de 14 amigos.
31. De quantas maneiras ela pode escolher seus convidados? 
32. De quantas maneiras ela pode escolher seus convidados se seis de seus amigos são maçantes, seis são interessantes e ela quer convidar pelo menos um de cada tipo?
33. De quantas maneiras ela pode escolher seus convidados se dois de seus amigos não gostam um do outro e, se um deles vier, o outro não vem?
34. De quantas maneiras ela pode escolher seus convidados se dois de seus amigos gostam muito um do outro e um deles não vem sem o outro?
35. Vinte e cinco pessoas, inclusive George e Teresa, são candidatos a participar de uma comissão formada por cinco pessoas. Se essa comissão tem que incluir George ou Teresa, de quantas maneiras ela pode ser selecionada?
36. Um estudante precisa selecionar 5 disciplinas, entre 12, para o próximo semestre e uma delas tem que ser História ou Geografia. De quantas maneiras o estudante pode escolher suas disciplinas?
37. Quantas mãos de 5 cartas, retiradas de um baralho padrão com 52 cartas, contêm exatamente 4 ases e 1 carta de paus? 15