Lista de Exercícios Matemática Discreta - Árvores de Decisão e Contagem

3ª Lista de Exercícios Matemática Discreta I Turmas C01DC01GC01N Tópicos abordados Árvores de Decisão Princípio da Inclusão e Exclusão Princípios básicos de contagem Permutações Arranjos e Combinações 1 Numa reunião de 200 estudantes de Ciência da Computação 100 já cursaram Matemática Discreta I MD1 85 já cursaram Algoritmos e Programação I AP1 120 já cursaram Circuitos Elétricos e Eletrônicos CEE 45 já cursaram MD1 e AP1 55 já cursaram MD1 e CEE 50 já cursaram AP1 e CEE e 15 não cursaram nenhuma das três Quantos cursaram exatamente duas dessas disciplinas 2 Use uma árvore de decisão para determinar o numero de subconjuntos de 3 7 9 11 24 com a propriedade de que a soma dos elementos no subconjunto seja menor ou igual a 27 3 Um exame de multipla escolha contem 10 questoes Ha quatro respostas possiveis para cada questao a De quantas maneiras um estudante pode responder as questoes do exame se responder a todas as questoes b De quantas maneiras um estudante pode responder as questoes do exame se ele pode deixar respostas em branco 4 Quantas sequências binárias com um a seis bits existem 5 Quantas sequências de tres digitos decimais a nao sao formadas pelo mesmo digito tres vezes b comecam com um digito impar c tem exatamente dois digitos que sao o numero 4 6 Suponha que uma senha para um sistema computacional deva ter exatamente 8 caracteres em que cada caractere na senha e uma letra minuscula uma letra maiuscula um digito decimal ou um dos seis caracteres especiais e a Quantas senhas diferentes estao disponiveis para esse sistema b Quantas dessas senhas contêm pelo menos uma ocorrência de pelo menos um dos seis caracteres especiais c Se demora um microssegundo 106 𝑠 ou 0000001 𝑠 para um hacker checar se cada senha possivel e a sua senha quantos anos demoraria para o hacker tentar todas as senhas possiveis 7 Certo sistema usa sequências binárias com 6 8 e 10 bits para codificar instruções Essas sequências devem cumprir com as seguintes condições Devem começar por 00 e terminar por 11 Não podem ser balanceadas isto é as quantidades de zeros e de uns nelas devem ser diferentes a Calcule a quantidade de sequências binárias com 6 8 e 10 bits que começam por 00 terminam por 11 e são balanceadas isto é têm a mesma quantidade de zeros e uns b Calcule a quantidade de instruções que podem ser codificadas usando o sistema de sequências descrito no enunciado do exercício 8 Uma pessoa deve construir um roteiro escolhendo uma sequência de 5 cidades para visitar entre 10 cidades disponíveis a Quantos roteiros diferentes existem b Se a quantidade de cidades disponíveis for dobrada passando a ser de 20 cidades em quanto aumenta a quantidade de roteiros em relação ao valor do item a c Se a quantidade de cidades a serem visitadas for dobrada e o total de cidades também passando a ser de 10 cidades e de 20 cidades respectivamente em quanto aumenta a quantidade de roteiros em relação ao valor do item a 9 Considere as sequências decimais com cinco dígitos a Quantas têm números múltiplos de três nas duas primeiras posições e números que não são múltiplos de três nas demais b Quantas têm exatamente três dígitos múltiplos de 3 Questão 1 Numa reunião de 200 estudantes de Ciência da Computação 100 já cursaram Matemática Discreta I MD1 85 já cursaram Algoritmos e Programação I AP1 120 já cursaram Circuitos Elétricos e Eletrônicos CEE 45 já cursaram MD1 e AP1 55 já cursaram MD1 e CEE 50 já cursaram AP1 e CEE e 15 não cursaram nenhuma das três Quantos cursaram exatamente duas dessas disciplinas Usar o princípio da inclusãoexclusão O número de estudantes que cursaram pelo menos uma dessas disciplinas é 100 MD1 85 AP1 120 CEE 45 MD1 e AP1 55 MD1 e CEE 50 AP1 e CEE x MD1 AP1 e CEE 200 15 185 onde x é o número de estudantes que cursaram as três disciplinas Resolvendo para x temos x 15 Agora podemos calcular o número de estudantes que cursaram exatamente duas dessas disciplinas como 45 MD1 e AP1 55 MD1 e CEE 50 AP1 e CEE 2 15 MD1 AP1 e CEE 120 Portanto 120 estudantes cursaram exatamente duas dessas disciplinas Questão 2 Use uma árvore de decisão para determinar o número de subconjuntos de 3 7 9 11 24 com a propriedade de que a soma dos elementos no subconjunto seja menor ou igual a 27 1 Começamos com um nó raiz que representa o conjunto vazio e uma soma de 0 2 Para cada elemento no conjunto 3 7 9 11 24 crie dois ramos a partir de cada nó na árvore um ramo inclui o elemento no subconjunto e adiciona seu valor à soma enquanto o outro ramo não inclui o elemento e mantém a soma inalterada 3 Se a soma em qualquer nó exceder 27 não crie mais ramos a partir desse nó 4 Quando todos os elementos tiverem sido considerados conte o número de nós folha na árvore Esse número é igual ao número de subconjuntos que satisfazem a propriedade desejada 3 377 3793979 Neste caso existem 10 subconjuntos que satisfazem a propriedade desejada 3 7 9 11 37 39 311 79 e 711 Questão 3 Um exame de múltipla escolha contém 10 questões Há quatro respostas possíveis para cada questão a De quantas maneiras um estudante pode responder às questões do exame se responder a todas as questões Um estudante pode responder às questões do exame de 410 1048576 maneiras diferentes se responder a todas as questões Isso porque para cada uma das 10 questões ele tem 4 opções de resposta b De quantas maneiras um estudante pode responder às questões do exame se ele pode deixar respostas em branco Se um estudante pode deixar respostas em branco então ele tem 5 opções para cada uma das 10 questões 4 opções de resposta mais a opção de deixar em branco Portanto ele pode responder às questões do exame de 510 9765625 maneiras diferentes Questão 4 Quantas sequências binárias com um a seis bits existem Uma sequência binária é uma sequência de bits onde cada bit pode ter valor 0 ou 1 Portanto o número de sequências binárias com n bits é dado por 2n onde 2 é o número de escolhas possíveis para cada bit 0 ou 1 Assim o número de sequências binárias com 1 bit é 21 2 2 bits é 22 4 3 bits é 23 8 4 bits é 24 16 5 bits é 25 32 6 bits é 26 64 Portanto há 2 sequências binárias com 1 bit 4 sequências binárias com 2 bits 8 sequências binárias com 3 bits 16 sequências binárias com 4 bits 32 sequências binárias com 5 bits e 64 sequências binárias com 6 bits Questão 5 Quantas sequências de três dígitos decimais a não são formadas pelo mesmo dígito três vezes Existem 10 opções para cada um dos três dígitos então existem 10 x 10 x 10 1000 sequências de três dígitos decimais Desses existem 10 sequências que são formadas pelo mesmo dígito três vezes 000 111 222 999 Portanto existem 1000 10 990 sequências de três dígitos decimais que não são formadas pelo mesmo dígito três vezes b começam com um dígito ímpar Existem 5 opções para o primeiro dígito 1 3 5 7 ou 9 e 10 opções para cada um dos outros dois dígitos Portanto existem 5 x 10 x 10 500 sequências de três dígitos decimais que começam com um dígito ímpar c têm exatamente dois dígitos que são o número 4 Existem duas opções para a posição do dígito que não é o número 4 primeiro ou segundo e 9 opções para o valor desse dígito qualquer coisa exceto o número 4 Portanto existem 2 x 9 18 sequências de três dígitos decimais que têm exatamente dois dígitos que são o número 4 Questão 6 Suponha que uma senha para um sistema computacional deva ter exatamente 8 caracteres em que cada caractere na senha é uma letra minúscula uma letra maiúscula um dígito decimal ou um dos seis caracteres especiais e a Quantas senhas diferentes estão disponíveis para esse sistema Existem 26 letras minúsculas 26 letras maiúsculas 10 dígitos decimais e 6 caracteres especiais Portanto existem 26 26 10 6 68 caracteres possíveis para cada posição na senha Como a senha deve ter exatamente 8 caracteres o número total de senhas diferentes disponíveis para esse sistema é de 688 457163239653376 b Quantas dessas senhas contêm pelo menos uma ocorrência de pelo menos um dos seis caracteres especiais O número de senhas que contêm pelo menos um caractere especial é igual ao número total de senhas menos o número de senhas que não contêm nenhum caractere especial O número de senhas que não contêm nenhum caractere especial é 628 onde 62 é o número total de caracteres possíveis sem os caracteres especiais Portanto o número de senhas que contêm pelo menos um caractere especial é 688 628 c Se demora um microssegundo 106 ou 0000001 para um hacker checar se 𝑠 𝑠 cada senha possível é a sua senha quantos anos demoraria para o hacker tentar todas as senhas possíveis O número total de senhas possíveis é 688 457163239653376 Se demora um microssegundo para um hacker checar cada senha possível então demoraria 457163239653376 0000001 457163239653376 segundos para o hacker tentar todas as senhas possíveis Isso é equivalente a aproximadamente 145 anos Questão 7 Certo sistema usa sequências binárias com 6 8 e 10 bits para codificar instruções Essas sequências devem cumprir com as seguintes condições Devem começar por 00 e terminar por 11 Não podem ser balanceadas isto é as quantidades de zeros e de uns nelas devem ser diferentes a Calcule a quantidade de sequências binárias com 6 8 e 10 bits que começam por 00 terminam por 11 e são balanceadas isto é têm a mesma quantidade de zeros e uns Para calcular a quantidade de sequências binárias com 6 8 e 10 bits que começam por 00 terminam por 11 e são balanceadas isto é têm a mesma quantidade de zeros e uns podemos usar o princípio da contagem Para sequências de 6 bits que começam por 00 e terminam por 11 temos apenas dois bits restantes para preencher Como a sequência deve ser balanceada esses dois bits devem ser um zero e um um Portanto há apenas uma sequência de 6 bits que atende às condições 001011 Para sequências de 8 bits que começam por 00 e terminam por 11 temos quatro bits restantes para preencher Como a sequência deve ser balanceada esses quatro bits devem ser dois zeros e dois uns Portanto há C42 6 sequências de 8 bits que atendem às condições 00001111 00100111 00101011 00110011 01001011 e 01010111 Para sequências de 10 bits que começam por 00 e terminam por 11 temos seis bits restantes para preencher Como a sequência deve ser balanceada esses seis bits devem ser três zeros e três uns Portanto há C63 20 sequências de 10 bits que atendem às condições Em resumo Há uma sequência binária com 6 bits que começa por 00 termina por 11 e é balanceada Há seis sequências binárias com 8 bits que começam por 00 terminam por 11 e são balanceadas Há vinte sequências binárias com 10 bits que começam por 00 terminam por 11 e são balanceadas b Calcule a quantidade de instruções que podem ser codificadas usando o sistema de sequências descrito no enunciado do exercício Para calcular a quantidade de instruções que podem ser codificadas usando o sistema de sequências descrito no enunciado do exercício precisamos calcular a quantidade de sequências binárias com 6 8 e 10 bits que começam por 00 terminam por 11 e não são balanceadas isto é têm quantidades diferentes de zeros e uns Para sequências de 6 bits que começam por 00 e terminam por 11 temos apenas dois bits restantes para preencher Como a sequência não pode ser balanceada esses dois bits devem ser ambos zeros ou ambos uns Portanto há duas sequências de 6 bits que atendem às condições 000011 e 001111 Para sequências de 8 bits que começam por 00 e terminam por 11 temos quatro bits restantes para preencher Como a sequência não pode ser balanceada esses quatro bits devem ter pelo menos três zeros ou pelo menos três uns Portanto há C43 C44 4 1 5 sequências com pelo menos três zeros e C43 C44 4 1 5 sequências com pelo menos três uns No total há 5 5 10 sequências de 8 bits que atendem às condições Para sequências de 10 bits que começam por 00 e terminam por 11 temos seis bits restantes para preencher Como a sequência não pode ser balanceada esses seis bits devem ter pelo menos quatro zeros ou pelo menos quatro uns Portanto há C64 C65 C66 15 6 1 22 sequências com pelo menos quatro zeros e C64 C65 C66 15 6 1 22 sequências com pelo menos quatro uns No total há 22 22 44 sequências de 10 bits que atendem às condições Somando todas as possibilidades para as três diferentes quantidades de bits 68 e10 temos um total de 2 sequências de seis bits 10 sequências de oito bits 44 sequências de dez bits56 instruções diferentes que podem ser codificadas usando o sistema descrito no enunciado do exercício Questão 8 Uma pessoa deve construir um roteiro escolhendo uma sequência de 5 cidades para visitar entre 10 cidades disponíveis a Quantos roteiros diferentes existem A quantidade de roteiros diferentes que podem ser criados ao escolher 5 cidades entre as 10 disponíveis é de Isso pode ser calculado usando a fórmula de arranjo Anp n np onde n é o número total de elementos e p é o número de elementos escolhidos Substituindo n 10 e p 5 temos C105 252 roteiros diferentes Ou seja existem 252 maneiras diferentes de escolher um conjunto de 5 cidades a partir de um conjunto de 10 cidades b Se a quantidade de cidades disponíveis for dobrada passando a ser de 20 cidades em quanto aumenta a quantidade de roteiros em relação ao valor do item a Se a quantidade de cidades disponíveis for dobrada passando a ser de 20 cidades o número de roteiros diferentes que uma pessoa pode construir é dado pelo número de arranjos de 20 elementos tomados 5 a 5 Isso pode ser calculado usando a fórmula de arranjo Anp n np onde n é o número total de elementos e p é o número de elementos escolhidos Substituindo n 20 e p 5 temos A205 20 205 20 15 20 x 19 x 18 x 17 x 16 1 x 2 x 3 x 4 x 5 1860480 Portanto existem 1860480 roteiros diferentes que uma pessoa pode construir c Se a quantidade de cidades a serem visitadas for dobrada e o total de cidades também passando a ser de 10 cidades e de 20 cidades respectivamente em quanto aumenta a quantidade de roteiros em relação ao valor do item a Se a quantidade de cidades a serem visitadas for dobrada e o total de cidades também passando a ser de 10 cidades e de 20 cidades respectivamente o número de roteiros diferentes que uma pessoa pode construir é dado pelo número de arranjos de 20 elementos tomados 10 a 10 Isso pode ser calculado usando a fórmula de arranjo Anp n np onde n é o número total de elementos e p é o número de elementos escolhidos Substituindo n 20 e p 10 temos A2010 20 2010 20 10 20 x 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 670442572800 Portanto existem 670442572800 roteiros diferentes que uma pessoa pode construir Comparando com o valor do item a que era de 30240 roteiros diferentes o aumento na quantidade de roteiros é de 670442572800 30240 670442542560 roteiros Isso representa um aumento de aproximadamente 22176 vezes em relação ao valor do item a Questão 9 Considere as sequências decimais com cinco dígitos a Quantas têm números múltiplos de três nas duas primeiras posições e números que não são múltiplos de três nas demais Existem 3 opções para cada uma das duas primeiras posições 0 3 ou 6 e 7 opções para cada uma das outras três posições 0 1 2 4 5 7 ou 8 Portanto o número total de sequências decimais com cinco dígitos que atendem às condições é 3 x 3 x 7 x 7 x 7 3087 b Quantas têm exatamente três dígitos múltiplos de 3 Para ter exatamente três dígitos múltiplos de 3 em uma sequência decimal de cinco dígitos precisamos escolher 3 das 5 posições para colocar os dígitos múltiplos de 3 Isso pode ser feito de C53 10 maneiras diferentes Para cada uma dessas escolhas existem 3 opções para cada uma das três posições escolhidas 0 3 ou 6 e 7 opções para cada uma das outras duas posições 0 1 2 4 5 7 ou 8 Portanto o número total de sequências decimais com cinco dígitos que atendem às condições é 10 x 3 x 3 x 3 x 7 x 7 13230