Qual é o número mínimo de pessoas que devemos reunir para que tenhamos certeza de que entre elas há pelo menos duas que fazem aniversário no mesmo mês?

Grátis

Índice Show

• Pré-visualização | Página 1 de 1
• Qual o número mínimo de pessoa que devemos reunir para que tenhamos a certeza de que?
• Quantas pessoas no mínimo devemos juntar para termos certeza de que pelo menos duas fazem aniversário no mesmo dia considerando um ano com 365 dias?
• Qual o número mínimo de pessoas que deve haver em um grupo?
• Qual é o número mínimo de pessoas que deve haver em um grupo para que possamos garantir que nele há pelo menos 7 pessoas nascidas no mesmo mês?

28 pág.

• Denunciar

Pré-visualização | Página 1 de 1

Prof. Ricardo Mesquita 
Princípio da Casa de Pombos 
Princípio da Multiplicação 
Em que pé estamos... 
 
 
 
 
 
 
Sumário 
 Princípio da Adição 
 Princípio da Casa de Pombos 
 Árvores de Decisão 
 Princípio da Multiplicação 
03/28 
Princípio da Adição 
Se A e B são eventos disjuntos com n1 e n2 resultados possíveis, 
respectivamente, então o número total de possibilidades para o 
evento “A ou B” é n1 + n2. 
 
Exemplo: Um pai deseja presentear seu filho com apenas um 
presente, bola ou carrinho. Chegando à loja ele encontra 9 tipos 
de bolas diferentes e 10 tipos de carrinho diferentes. Quantas 
são as possibilidades de escolha do presente? 
 
Solução: Os eventos são disjuntos com n1 = 9 e n2 = 10 então 
existem n1 + n2 = 19 possibilidades de escolha. 
 
04/28 
Princípio da Adição 
Exemplo: Supondo que exista cinemas, e teatros em sua cidade, e 
que tenham entrado em cartaz 3 filmes e 2 peças de teatro diferentes 
para passarem no próximo sábado, e que você tenha dinheiro para 
assistir a apenas um dos eventos. Quantos são os programas que você 
pode fazer neste sábado? 
 
Solução: 
A = { f | f é um filme} = {F1,F2, F3}, e 
B = { t|t é uma peça de teatro} = {T1, T2} 
Temos que A e B são disjuntos, ou seja, A  B = , logo, A  B = 
{F1, F2, F3, T1, T2} 
 
Assim ao todo são 3+2 = 5 programas. 
 
05/28 
Princípio da Casa de Pombos 
 O princípio do pombal ou princípio da casa dos 
pombos é a afirmação de que se n pombos devem ser postos 
em m casas, e se n > m, então pelo menos uma casa irá conter 
mais de um pombo. 
6 
Na figura: n=10 e m = 9 (atenção na 
primeira casa) 
 Também conhecido como Teorema de Dirichlet ou princípio das gavetas de Dirichlet, pois 
supõe-se que o primeiro relato deste princípio foi feito por Dirichlet em 1834, com o nome 
de Schubfach prinzip ("princípio das gavetas"). 
06/28 
Princípio da Casa de Pombos 
(Generalizado) 
 
Se N objetos devem ser colocados em k caixas, então existirá pelo menos 
uma caixa que conterá, no mínimo, 𝑁/𝑘 objetos. 
 
07/28 
8 
Exemplo 1: Qual o número mínimo de pessoas que devemos reunir para que 
tenhamos certeza de que duas entre elas fazem aniversário no mesmo mês? 
Princípio da Casa de Pombos 
Resposta: O número mínimo de pessoas é 13. 
Justificativa: Para este problema, temos: 
• Casas: meses do ano (12) 
• Pombos: pessoas (13) 
• Relação: associamos cada pessoa ao seu mês de nascimento. 
Pelo princípio das casas de pombos, como temos 12 casas e 13 pombos, uma 
das casas receberá pelo menos 2 pombos, ou seja, um dos meses terá dois 
aniversariantes. 
08/28 
 
9 
09/28 
 
10 
10/28 
Princípio da Casa de Pombos 
 
11 
Resposta: N = 5  5 + 1 = 26 estudantes. 
Princípio da Casa de Pombos 
11/28 
Aplicando a regra... 
Ex: Dentre 100 pessoas mostre que haverá um mês em que ao menos 
9 pessoas farão aniversário 
 
O princípio da casa de pombos diz que “se N objetos devem ser colocados em k 
caixas, então existirá pelo menos uma caixa que conterá, no mínimo, 𝑁/𝑘 objetos.” 
 
Temos aqui, N = 100 e k = 12, então, existirá um mês em que 
 
 𝑁/𝑘 = 100/12 = 8,33 = 9 
 
pessoas farão aniversário. 
12 
12/28 
Exemplo 
Mostre que em um conjunto de 5 inteiros (não necessariamente 
consecutivos) existem 2 com o mesmo resto quando dividido por 4. 
 
Os possíveis restos quando dividimos um número por 4, são: 0, 1, 2, 
3 (4 restos) 
 
Se tenho 5 inteiros, então quando divididos por 4 terão 5 restos. 
 
Assim como temos 4 restos distintos 2 deverão ser iguais. 
 
13/28 
Árvores de Decisão 
 Uma árvore é um tipo particular de um grafo onde não 
existem ciclos. 
São importantes estruturas de dados! 
 É uma estrutura muito útil para registrar todas as 
possibilidades em situações em que os eventos ocorrem em 
ordem. 
14/28 
Usando uma Árvore de Decisão 
Exemplo: Sejam as seguintes regras para decisão de um 
torneio entre os times A e B: 
 
 Cada jogo tem sempre um vencedor. 
 O time para ser campeão deve vencer dois jogos consecutivos 
ou um total de três jogos. 
 
De quantas formas diferentes pode-se terminar o torneio? 
15/28 
Resultado: 
 
 
 
 
 
 
 
 
 
 Resposta: 10 formas, no total. 
16/28 
Árvore de Decisão 
 
Exemplo: Considere um sistema computacional que possui 
quatro unidades de I/O, A, B, C e D, e três processadores X, Y e 
Z. Qualquer unidade de I/O pode ser conectada a um 
processador. Quantas possibilidades existem de se conectar uma 
unidade de I/O com um processador? 
18/28 
Árvore de Decisão 
 
 
 
 
 
 
 
 
 
 
 Resposta: 12 possibilidades 
18/28 
Árvore de Decisão 
Exemplo: Considere o seguinte problema. As posições de 
presidente, tesoureiro e secretário têm que ser escolhidas entre 
4 pessoas: A, B, C e D. Além disso, temos duas restrições: 
i. A não pode ser presidente; 
ii. C ou D deve ser o secretário. 
Quantas escolhas distintas podem existir? 
19/28 
Árvore de Decisão 
 
 
 
 
 
 
 
 
 
 R: 8 escolhas 
20/28 
Princípio da Multiplicação 
 
 
 
 
Exemplo: Um código de identificação é formado por uma 
sequência de quatro símbolos escolhidos de um conjunto 
formado pelas 26 letras do alfabeto e os 10 dígitos. Quantos 
códigos de identificação diferentes existem... 
a. se a repetição de símbolos é permitida? 
b. se a repetição de símbolos não é permitida? 
21/28 
Princípio da Multiplicação 
Respostas: 
a. 36  36  36  36 = 1.679.616 códigos 
b. 36  35  34  33 = 1.413.720 códigos 
22/28 
Princípio da Multiplicação 
 Vamos retornar ao problema da escolha do presidente, tesoureiro 
e secretário: 
Considere o seguinte problema. As posições de presidente, tesoureiro e 
secretário têm que ser escolhidas entre 4 pessoas: A, B, C e D. Além disso, temos 
duas restrições: 
i. A não pode ser presidente; 
ii. C ou D deve ser o secretário. 
Quantas escolhas distintas podem existir? 
 Temos 2 possibilidades para secretário (C ou D); 
 Para presidente também são duas possibilidades, já que A e a 
pessoa escolhida para secretário não podem ser escolhidas; 
 Para tesoureiro restam duas pessoas; 
Assim, temos: 2  2  2 = 8 possibilidades 
23/28 
Outro Exemplo: 
 Quantos inteiros de três dígitos são divisíveis por 5? 
Os números candidatos terminam com 0 ou 5 
24/28 
Exercícios 
1. Quantas placas de carro podem ser feitas (com três letras e 
quatro dígitos)? 
2. Os números de celulares tinham 8 dígitos. 
a. Quantas linhas são possíveis nesta configuração? 
b. Depois, acrescentou-se um “9” na frente do número. 
Isso possibilitou quantas linhas a mais? 
c. Finalmente, os números de celulares passaram a ter 9 
dígitos. Quantas linhas são possíveis nesta 
configuração? 
 
25/28 
Exercícios 
3. Um restaurante oferece 4 tipos de entrada, 10 pratos principais 
e 5 tipos de sobremesa. Se um freguês deste restaurante decide 
tentar uma refeição diferente a cada noite, quanto tempo levará 
para esgotar todas as possibilidades? 
4. Seja um cadeado que utiliza anéis rotativos, em vez de chave. 
Considere que este cadeado trabalhe com uma chave numérica 
de 5 dígitos. 
a. Quantas possibilidades de chave numérica existem? 
b. Se uma pessoa consiga testar 5 chaves por minuto, quanto 
tempo esta pessoa demoraria para testar todas as 
possibilidades? 
 
26/28 
Exercícios 
5. Quantos inteiros múltiplos de 5 existem entre 1000 
(inclusive) e 4999? 
6. As palavras de um certo código são formadas por 2 letras e 
2 algarismos, de tal forma que não há letras ou algarismos 
iguais. Assim, a palavra LY45 é palavra deste código, 
enquanto que AA23 não é palavra deste código, pois repete 
a letra A. Quantas palavras existem neste código? 
27/28 
Praticar!!

Qual o número mínimo de pessoa que devemos reunir para que tenhamos a certeza de que?

Quantas pessoas no mínimo devemos juntar para termos certeza de que pelo menos duas fazem aniversário no mesmo dia considerando um ano com 365 dias?

Qual o número mínimo de pessoas que deve haver em um grupo?

Qual é o número mínimo de pessoas que deve haver em um grupo para que possamos garantir que nele há pelo menos 7 pessoas nascidas no mesmo mês?