Contagem - Aula do Renato

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