Baixe o app para aproveitar ainda mais
Prévia do material em texto
Contagem Renato Ramos da Silva Universidade Federal de Lavras renato.ramos@dcc.ufla.br 8 de janeiro de 2016 Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 1 / 32 Overview 1 Princípios Básicos de Contagem 2 Princípio da Inclusão-Exclusão 3 Princípio da Casa do Pombo Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 2 / 32 Regra do Produto Teorema Suponha que um procedimento pode ser quebrado em uma seqüência que duas tarefas. Se existem n1 maneiras de fazer a primeira tarefa e n2 maneiras de fazer a segunda tarefa após a finalização da primeira. Então existem n1n2 maneiras de realizar o procedimento. Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 3 / 32 Exemplo Exemplo 1 Uma nova companhia com apenas dois empregados, João e José, aluga um andar de um prédio com 12 salas. Quantas formas diferentes há para designar as diferentes salas para esses dois empregados? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 4 / 32 Exemplo Exemplo 1 Uma nova companhia com apenas dois empregados, João e José, aluga um andar de um prédio com 12 salas. Quantas formas diferentes há para designar as diferentes salas para esses dois empregados? Resposta João =⇒ 12 José =⇒ 11 Pela regra do produto, temos 12× 11 = 132 Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 5 / 32 Exemplo Exemplo 2 As cadeiras de uma auditório serão rotuladas com uma letra e um inteiro positivo menor ou igual a 100. Qual é o maior número de cadeiras que podem ser rotuladas de maneira diferente? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 6 / 32 Exemplo Exemplo 2 As cadeiras de uma auditório serão rotuladas com uma letra e um inteiro positivo menor ou igual a 100. Qual é o maior número de cadeiras que podem ser rotuladas de maneira diferente? Resposta Letras =⇒ 26 Números =⇒ 100 Pela regra do produto, temos 26× 100 = 2600 formas diferentes de etiquetar as cadeiras Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 7 / 32 Exemplo Exemplo 3 Quantos números binários diferentes pode-se ter com comprimento igual a 7? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 8 / 32 Exemplo Exemplo 3 Quantos números binários diferentes pode-se ter com comprimento igual a 7? Resposta cada bit=⇒ 2 comprimento =⇒ 7 Pela regra do produto, temos 27 = 128 diferentes números binários Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 9 / 32 Regra da Soma Teorema Se uma primeira tarefa pode ser realizada de n1 maneiras e a segunda tarefa pode ser realizada de n2 maneiras E essas tarefas não podem ser realizadas ao mesmo tempo Então, existem n1 + n2 maneiras de realizar uma dessas tarefas. Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 10 / 32 Exemplo Exemplo 1 Suponha que um dos professores ou um dos alunos será escolhido como um representante de um comitê universitário. De quantas maneiras é possível selecionar um representante sabendo que são 37 professores e 87 alunos? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 11 / 32 Exemplo Exemplo 1 Suponha que um dos professores ou um dos alunos será escolhido como um representante de um comitê universitário. De quantas maneiras é possível selecionar um representante sabendo que são 37 professores e 87 alunos? Resposta Professores =⇒ 37 Alunos =⇒ 83 Pela regra da soma, temos 37+ 83 = 120 Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 12 / 32 Exemplo Exemplo 2 Um estudante pode escolher um projeto de três listas existentes. Cada uma das listas contém 23, 15 e 19 possíveis projetos, respectivamente. Qual a quantidade de possíveis escolhas de projetos? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 13 / 32 Exemplo Exemplo 2 Um estudante pode escolher um projeto de três listas existentes. Cada uma das listas contém 23, 15 e 19 possíveis projetos, respectivamente. Qual a quantidade de possíveis escolhas de projetos? Resposta Pela regra da soma, temos 23+ 15+ 19 = 57 formas diferentes de etiquetar as cadeiras Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 14 / 32 Exemplo Exemplo Completo 1 Em uma versão da linguagem BASIC, o nome de uma variável é uma string com um ou dois caracteres alfanuméricos, sabendo que caracteres maiúsculos e minúsculos não são distinguidos. O nome da variável deve começar por uma letra e deve ser diferente de cinco strings com dois caracteres que são palavras reservadas da linguagem. Quantos nomes diferentes de variáveis podem ser criados nessa versão de BASIC? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 15 / 32 Exemplo Resposta número de nomes de variáveis diferentes =⇒ V número de nomes com um caractere =⇒ V1 número de nomes com dois caracteres =⇒ V2 Pela regra da soma, temos V = V1 + V2 V1 = 26 e V2 = 26× 36− 5 = 931 Dessa forma, V = 957 Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 16 / 32 Exemplo Exemplo Completo 2 Cada usuário em um sistema computacional possui uma senha de tamanho 6, 7 ou 8 caracteres. Cada caractere é uma letra maiúscula ou um dígito. Cada senha deve conter pelo menos um dígito. Quantas senhas são possíveis nesse sistema? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 17 / 32 Exemplo Exemplo Completo 2 Cada usuário em um sistema computacional possui uma senha de tamanho 6, 7 ou 8 caracteres. Cada caractere é uma letra maiúscula ou um dígito. Cada senha deve conter pelo menos um dígito. Quantas senhas são possíveis nesse sistema? Resposta P = P6 + P7 + P8 P6 = 366 − 266 = 1867866560 P7 = 367 − 267 = 70332353920 P8 = 368 − 268 = 2612282842880 P = 2684483063360 Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 18 / 32 Princípio da Inclusão-Exclusão Exemplo 1 Uma classe de matemática discreta tem 25 estudantes de computação, 13 estudantes de matemática e 8 estudantes de matemática e computação. A classe possui quantos estudantes? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 19 / 32 Exemplo Exemplo 1 Uma classe de matemática discreta tem 25 estudantes de computação, 13 estudantes de matemática e 8 estudantes de matemática e computação. A classe possui quantos estudantes? Resposta | A ∪ B |=| A | + | B | − | A ∩ B | = 25+ 13− 8 = 30 Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 20 / 32 Exemplo Exemplo 2 Suponha que existam 1807 calouros na faculdade. Do total, 453 são de computação, 567 de matemática e 299 estão fazendo dois cursos, matemática e computação. Quantos não estão fazendo nem computação nem matemática? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 21 / 32 Exemplo Exemplo 2 Suponha que existam 1807 calouros na faculdade. Do total, 453 são de computação, 567 de matemática e 299 estão fazendo dois cursos, matemática e computação. Quantos não estão fazendo nem computação nem matemática? Resposta | A ∪ B |=| A | + | B | − | A ∩ B | = 453+ 567− 299 = 721 1807− 721 = 1086 calouros não fazem nem computação nem matemática Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 22 / 32 Exemplo Exemplo 3 1232 estudantes fazem curso de espanhol, 879 francês, 114 russo. 103 fazem espanhol e francês, 23 espanhol e russo e 14 francês e russo. 2092 estudantes fazem pelo menos um curso de espanhol, francês ou russo. Quantos estudantes fazem os três cursos? Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 23 / 32 Exemplo Exemplo 3 1232 estudantes fazem curso de espanhol, 879 francês, 114 russo. 103 fazem espanhol e francês, 23 espanhol e russo e 14 francês e russo. 2092 estudantes fazem pelo menos um curso de espanhol, francês ourusso. Quantos estudantes fazem os três cursos? Resposta | E |= 1232 | F |= 879 | R |= 114 | E ∩ F |= 103 | E ∩ R |= 23 | F ∩ R |= 14 | E ∪ F ∪ R |=| E | + | F | + | R | − | E ∩ F | − | E ∩ R | − | F ∩ R | + | E ∩ F ∩ R | 2092 = 1232+ 879+ 114− 103− 23− 14+ | E ∩ F ∩ R | | E ∩ F ∩ R |= 7 Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 24 / 32 Princípio da Casa do Pombo Teorema Se k+1 ou mais objetos são colocados em k caixas, então existe pelo menos uma caixa que contém dois ou mais objetos. Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 25 / 32 Exemplo Exemplo 1 Dentre um grupo de 367 pessoas, deve existir pelo menos duas que têm o mesmo dia de aniversário. Resposta Pois têm-se apenas 366 possíveis dias de nascimento. Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 26 / 32 Exemplo Exemplo 2 Em um grupo com 27 palavras em inglês, deve existir pelo menos duas que começam com a mesma letra. Resposta Uma vez que existem 26 letras no alfabeto da língua inglesa. Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 27 / 32 Princípio da Casa do Pombo Generalizado Teorema Se n objetos são colocados em k caixas, então existe pelo menos uma caixa com dn/ke objetos Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 28 / 32 Exemplo Exemplo 1 Entre 100 pessoas, quantas nasceram no mesmo mês? Resposta d100/12e = 9 Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 29 / 32 Exemplo Exemplo 2 Qual é o número mínimo de estudantes em uma classe de matemática discreta de forma que pelo menos seis receberão a mesma pontuação? Adote que existem cinco pontuações: A, B, C, D e F. Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 30 / 32 Exemplo Exemplo 2 Qual é o número mínimo de estudantes em uma classe de matemática discreta de forma que pelo menos seis receberão a mesma pontuação? Adote que existem cinco pontuações: A, B, C, D e F. Resposta dn/5e = 6 n = 5× 5+ 1 = 26 Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 31 / 32 The End Renato Ramos da Silva (UFLA) Short title 8 de janeiro de 2016 32 / 32 Princípios Básicos de Contagem Princípio da Inclusão-Exclusão Princípio da Casa do Pombo
Compartilhar