+Conjuntos+contáveis

Prévia do material em texto

Conjuntos contáveis 
Conjuntos Contáveis e Incontáveis 
Em um conjunto finito S, podemos sempre designar um elemento como o 
primeiro, s1; outro elemento como o segundo, s2, e assim por diante. Se houver 
k elementos no conjunto, esses elementos podem ser listados na ordem que 
selecionarmos: 
20:33:37 
Conjuntos contáveis 
20:33:37 
Conjuntos contáveis 
20:33:38 
Conjuntos contáveis 
20:33:38 
Conjuntos contáveis 
20:33:38 
Contagem: princípios básicos 
A análise combinatória trata da determinação do número de possibilidades lógicas de 
algum evento, sem necessariamente identificar todos os casos. 
Regra da soma 
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. 
Exemplo: 
Suponha que existe oito professores do sexo masculino e cinco professores do sexo feminino 
ministrando aulas de cálculo. De quantas maneiras o aluno pode escolher um professor de 
cálculo? 
Resposta: 8 + 5 = 13 maneiras. 
20:33:38 
Contagem: princípios básicos 
Exemplo: 
Suponha que E é o evento de escolher um número primo menor do que 10, e suponha que F 
é o evento de escolher um número par menor que 10. de quantas maneiras é possível 
acontecer os eventos E ou F? 
Resposta: 4 + 4 - 1 = 7 maneiras. 
Evento E: {2, 3, 5, 7} 
Evento F: {2, 4, 6, 8} 
O elemento 2 satisfaz tanto ao evento E quanto ao evento F. 
20:33:38 
Contagem: princípios básicos 
Exemplo: 
Suponha que E é o evento de escolher um número primo entre 10 e 20, e suponha que F é o 
evento de escolher um número par entre 10 e 20. De quantas maneiras é possível acontecer 
os eventos E ou F? 
Resposta: 4 + 4 = 8 maneiras. 
Evento E: {11, 13, 17, 19} 
Evento F: {12, 14, 16, 18} 
Nenhum evento E pertence ao evento F. 
20:33:40 
Contagem: princípios básicos 
A regra do produto 
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 n1*n2 maneiras de realizar o procedimento. 
20:33:40 
Contagem: princípios básicos 
Exemplo: 
Suponha que uma placa de carro contém duas letras seguidas por três algarismos, sendo o 
primeiro dígito não nulo. Quantas placas de carro podem ser impressas? 
Resposta: 26 * 26 * 9 * 10 * 10 = 608.400 placas distintas podem ser impressas. 
Exemplo: 
De quantas maneiras uma organização com 26 membros pode eleger um presidente, um 
tesoureiro e um secretário. (assuma que ninguém pode assumir mais de um cargo). 
Resposta: 26 * 25 * 24 = 15.600 maneiras. 
20:33:40 
Contagem: princípios básicos 
Interpretações teóricas: 
 
Sejam A e B dois conjuntos quaisquer, então: 
 
1. Princípio da regra da soma: se A e B são disjuntos, então: 
n(A U B) = n(A) + n(B) 
2. Princípio da regra do produto: seja A x B o produto cartesiano dos conjuntos A e B, então: 
n(A x B) = n(A)*n(B) 
20:33:40 
Contagem: princípios básicos 
20:33:41 
Contagem: princípios básicos 
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? 
n(AUB) = n(A) + n(B) – n(A∩B) = 25 + 13 – 8 = 30 
20:33:41 
Contagem: princípios básicos 
F – francês 
65 
A – Alemão 
45 
R – Russo 
42 
8 
12 
17 7 
28 18 
10 
20:33:41 
Contagem: princípios básicos Exemplo: 
Numa turma de 40, muitos estudantes estão colecionando as fotografias de seus astros de 
rock favoritos. 18 estudantes têm a fotografia dos Beatles, 16 estudantes têm a fotografia dos 
Rolling Stones e 12 estudantes têm a fotografia de Elvis Presley. Existem 7 estudantes que 
têm fotografias de ambos Beatles e Rolling Stones, 5 estudantes têm as fotografias de ambos 
Beatles e Elvis Presley, e 3 estudantes têm fotografias de ambos Rolling Stones e Elvis Presley. 
Finalmente existem 2 estudantes que possuem fotografias de todos os três grupos. Pergunta: 
quantos estudantes na turma não têm fotografia de nenhum dos grupos de rock? 
B - 18 
R – 16 
E – 12 
2 
5 
3 1 
8 8 
6 
U - 40 
20:33:42 
Contagem: princípios básicos 
Notação fatorial 
O produto dos inteiros positivos de 1 até n, inclusive, é denotado por n! (lê-se “n fatorial”): 
 
n! = 1*2*3……(n-2)*(n-1)*n 
Outras definições: 
1! = 1 e n! = n*(n-1)! 
0! = 1 
Exemplo: 
1. 2! = 
2. 3! = 
3. 4! = 
4. 5! = 
5. 6! = 
1*2 = 2 
1*2*3 = 6 
4*3! = 24 
5*4! = 120 
6*5! = 720 
20:33:42 
Contagem: princípios básicos 
Exemplos: 
20:33:42 
Contagem: princípios básicos 
20:33:42 
Contagem: princípios básicos 
Exemplos: 
20:33:43 
Contagem: princípios básicos 
Observações: 
 
 
Como vimos Cn,0 é a quantidade de subconjuntos com 0 elementos que se pode 
obter de um conjunto de n elementos. 
Com 0 elementos só existe um subconjunto que é Ø 
Exemplos 
20:33:43 
Contagem: princípios básicos 
20:33:43 
Contagem: princípios básicos 
20:33:44 
Contagem: princípios básicos 
0 1 
1 1x + 1y 
2 1x2 + 2xy + 1y2 
3 1 x3+ 3x2 y + 3xy2+ 1y3 
4 1 x4 + 4x3 y + 6x2y2 + 4x y3 + 1 y4 
5 1 x5 + 5x4 y + 10x3y2 + 10x2 y3 + 5x y4 + 1 y5 
20:33:44 
Contagem: princípios básicos 
1 linha 0 
1 1 linha 1 
1 2 1 linha 2 
1 3 3 1 linha 3 
1 4 6 4 1 linha 4 
1 5 10 10 5 1 linha 5 
1 6 15 20 15 6 1 
Se tirarmos as variáveis obtemos o Triângulo de Pascal. 
 Observamos que os números que estão em cada linha do triângulo são os 
mesmos que os coeficientes do desenvolvimento de cada potência do 
binômio ( x + y). 
20:33:44 
Contagem: princípios básicos 
Qual o desenvolvimento do binômio (x + y)6 ? 
(x + y)6 = 1 x6 + 6x5 y + 15x4y2 + 20x3 y3 + 15x2 y4 + 6x y5 + 1 y6 
20:33:44 
Contagem: princípios básicos 
Há uma turma de 40 garotas. Existem 18 garotas que gostam de jogar xadrez, 23 que gostam 
de jogar futebol. Várias delas gostam de ciclismo. O número daquelas que gostam de jogar 
tanto xadrez quanto futebol é 9. Existem 7 garotas que gostam de xadrez e ciclismo, 12 
delas gostam de futebol e ciclismo. Existem 4 garotas que gostam de todas as três 
atividades. Adicionalmente, sabemos que todas gostam de alguma dessas atividades. 
Quantas garotas gostam de ciclismo? 
𝒏 𝑨 ∪ 𝑩 ∪ 𝑪
= 𝒏 𝑨 + 𝒏 𝑩 + 𝒏 𝑪 − 𝒏 𝑨 ∩ 𝑩 − 𝒏 𝑨 ∩ 𝑪 − 𝒏 𝑩 ∩ 𝑪 + 𝒏(𝑨 ∩ 𝑩 ∩ 𝑪) 
 40 = 𝟏𝟖 + 𝟐𝟑 + 𝒏 𝑪 − 𝟗 − 𝟏𝟐 − 𝟕 + 𝟒 
 𝒏 𝑪 = 𝟐𝟑 
4 8 
3 
6 
6 
8 
U = 40 
Xadrez (18) = A 
Futebol (23) = B 
Ciclismo (?) = C 
20:33:44 
Contagem: princípios básicos 
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? 
A – conjuntos dos calouros de computação 
B – conjuntos dos calouros de matemática 
A ∩ B – conjuntos dos calouros que fazem matemática e computação 
AUB – conjuntos dos calouros que fazem matemática ou computação 
n(AUB) = n(A) + n(B) – n(A∩B) = 453 + 567 – 299 = 721 
1807 – 721 = 1086 calouros não fazem nem computação nem matemática 
20:33:48 
Contagem: princípios básicos 
20:33:48 
Contagem: princípios básicos 
Resolva: 
 
𝟏𝟑!
𝟏𝟏!
 
7!
10!
 
𝟏𝟑 ∗ 𝟏𝟐 ∗ 𝟏𝟏!
𝟏𝟏!= 𝟏𝟑 ∗ 𝟏𝟐 = 𝟏𝟓𝟔 
𝟕!
𝟏𝟎 ∗ 𝟗 ∗ 𝟖 ∗ 𝟕!
=
𝟏
𝟏𝟎 ∗ 𝟗 ∗ 𝟖
=
𝟏
𝟕𝟐𝟎
 
20:33:48 
Contagem: princípios básicos 
Existem 22 estudantes do sexo feminino e 18 estudantes do sexo masculino em uma sala 
de aula. Quantos estudantes existem no total? 
Total = 22 + 18 = 40. 
Dentre as 32 pessoas que guardam papel ou garrafas (ou ambos) para reciclar, 30 guardam 
papel e 14 guardam garrafas. Ache o número m de pessoas que (a) guardam ambos, (b) 
guardam apenas papel e (c) guardam apenas garrafas. 
Resposta: =(P ∩ G) = n(P) + n(G) – n(P U G) = 30 +14 – 32 = 12 – Guardam ambos 
=(P \ G) = n(P) – n(P ∩ G) = 30 -12 = 28 – Guardam papel 
=(G \ P) = n(G) – n(P ∩ G) = 14 -12 = 2 – Guardam garrafas 
20:33:48 
Contagem: princípios básicos 
Princípio da casa do pombo 
Se n casas de pombos são ocupadas por n + 1 ou mais pombos, então pelo menos 
uma casa é ocupada por mais de um pombo. 
Esse princípio pode ser aplicado a muitos problemas para os quais queremos 
mostrar que uma determinada situação ocorre. 
Fonte: pt.wikipedia.org 
20:33:48 
Contagem: princípios básicos 
Princípio da casa de pombos generalizado: 
Se n casas de pombo são ocupadas por kn + 1 ou mais pombos, onde k é um 
inteiro positivo, então pelo menos uma casa de pombo é ocupada por k + 1 ou 
mais pombos. 
20:33:48 
Contagem: princípios básicos 
Exemplo: 
•Quantos professores são necessários em uma determinada escola, para termos 
certeza que dois professores tenham nascido no mesmo mês. 
n =12 (casas de pombo) … k + 1 = 2 (pombos) … k = 1 …. Kn+1… 1*12 + 1 = 13. 
• Agora suponha que que voce queira saber quantos professores a escola tem 
que ter, para ter certeza que 4 professores nasceram no mesmo mês. 
n =12 (casas de pombo) … k + 1 = 4 (pombos) … k = 3 …. Kn+1… 3*12 + 1 = 37. 
•Suponha que um saco de lavanderia contém muitas meias vermelhas, brancas e 
azuis. Então é necessário pegar quantas meias para ter certeza de obter um par 
com uma única cor. 
n =3 (casas de pombo) … k + 1 = 2 (pombos) … k = 1 …. Kn+1… 1*3 + 1 = 4. 
20:33:50 
Contagem: princípios básicos 
Suponha que um saco de lavanderia contém muitas meias pretas e brancas. 
Ache o número de meias que é preciso escolher, para se obter um par da mesma 
cor. 
 
20:33:50 
Contagem: princípios básicos 
Exemplo: 
Ache o número mínimo de estudantes de uma turma que garante que pelo menos 
3 deles nasceram no mesmo mês. 
 
20:33:50 
Contagem: princípios básicos 
Suponha que um saco de lavanderia contém muitas meias vermelhas, brancas e 
azuis. Ache o número de meias que é preciso escolher, para se obter dois pares 
(quatro meias) da mesma cor. 
 
20:33:50 
Contagem: princípios básicos 
Exemplo: 
Damos 50 tiros num alvo com forma de quadrado, cujo lado é de 70cm de comprimento: 
somos atiradores um tanto bons, pois todos os nossos tiros atingem o alvo. Prove que 
existem dois tiros que estão mais próximos que 15 cm. 
70 cm 
Dividindo o alvo em “pedaços” de 10cm, teremos 49 pedaços: 
10 cm 
10 cm 
20:33:53 
Contagem: princípios básicos 
Exemplo: 
Ache o número mínimo de estudanTes necessários que garanta que cinco deles estejam na 
mesma turma. (Primeira série, segunda série, terceira série e quarta série). 
𝑛 = 4 
𝑘 + 1 = 5 … 𝑘 = 4 
𝒌𝒏 + 𝟏 = 𝟒 ∗ 𝟒 + 𝟏 = 𝟏𝟕 alunos. 
20:33:53 
Contagem: princípios básicos 
Problemas variados: 
Uma amostra de 80 proprietários de automóveis revelou que 24 possuiam vans e 62 
possuíam carros que não eram vans. Ache o número k de pessoas que possuem ambos, 
vans e outros tipos de carros. 
𝒏 𝑽 ∪ 𝑶 = 𝒏 𝑽 + 𝒏 𝑶 − 𝒏(𝑽 ∩ 𝑶) 
𝟖𝟎 = 𝟐𝟒 + 𝟔𝟐 − 𝒏(𝑽 ∩ 𝑶) 
𝒏(𝑽 ∩ 𝑶) = 𝟔 
20:33:53 
Contagem: princípios básicos 
Exemplo: 
Em programa de televisão, um candidato deve responder 21 perguntas. A primeira pergunta 
vale 1 ponto, a segunda 2 pontos, a terceira 4 pontos, e assim sucessivamente, dobrando 
sempre. O candidato responde a todas as perguntas e ganha os pontos correspondentes as 
respostas que acertou, mesmo que erre algumas. Sendo assim, responda: 
a) Qual o número de pontos que o candidato faria se acertar todas as perguntas? 
b) Quantas e quais as perguntas o candidato acertou se o número de pontos obtidos 
for igual a 571.113? 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
 
1 
 
2 
 
4 
 
8 
 
16 
 
32 
 
64 
 
128 
 
256 
 
512 
 
1.024 
 
2.048 
 
4.096 
 
8.192 
 
16.384 
 
32.768 
 
65.536 
 
131.072 262.144 524.288 1.048.576 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 
20:33:54 
Contagem: princípios básicos 
Exemplo: 
Em um bosque há 180 árvores. Sabe-se que cada árvore tem pelo menos 30 folhas e que 
nenhuma tem mais de 200 folhas. Podemos concluir que: 
 
A. Existe pelo menos uma árvore com 200 folhas. 
B. Existem pelo menos duas árvores com o mesmo número de folhas. 
C. Existe alguma árvore com 115 folhas. 
D. O número total de folhas é certamente maior que 6000. 
E. O número médio de folhas por árvore é 115. 
20:33:54 
Contagem: princípios básicos 
Exemplo: 
20:33:54 
Contagem: princípios básicos 
Exemplo: 
20:33:54 
Todos os pontos de um plano são pintados de azul ou vermelho. 
Prove que podemos encontrar dois pontos da mesma cor que 
apresentam a mesma distância. 
Solução: Basta imaginarmos um triângulo equilátero de lado igual a . 
Como são duas cores (casas) e três pontos (pombos). Pelo princípio da 
casa dos pombos teremos dois da mesma cor. 
Contagem: princípios básicos 
Exemplo: 
 
Escolhe-se cinco pontos aleatoriamente sobre uma superfície de um quadrado de lado 2. 
Mostre que há um par de pontos tais que a distância entre eles é no máximo 2. 
20:33:55 
1 1 
1 
1 
d 
𝑑 = 12 + 12 
𝑑 = 2