Aula 03 - Princípio da Inclusão Exclusão

Prévia do material em texto

1
 
 
Aula 3 
 
 
PRINCÍPIO DA INCLUSÃO-EXCLUSÃO 
 
 
 
Objetivo 
Utilizar o Princípio da Inclusão-Exclusão em alguns problemas de contagem. 
 
 
Exemplo 1 
 Em relação à palavra MISTO, quantos são os anagramas que 
a) começam por M? 
b) têm O na segunda posição? 
c) começam por M e têm O na segunda posição? 
d) começam por M ou têm O na segunda posição? 
 
a) Se os anagramas começam por M, a primeira posição está fixada, restando 4 
elementos (I ,S, T, O) para permutarem nas demais posições. 
M _ _ _ _ 
 ↑ ↑ ↑ ↑ 
 4 3 2 1 
Temos P4 = 4!=24 anagramas começando por M. 
 
b) Tendo O na segunda posição, usando o mesmo raciocínio do item a, temos P4= 4! = 24 
anagramas. 
 
c) Duas letras estão fixas: M e O. As demais letras podem permutar nas outras 3 
posições. 
M O _ _ _ 
 ↑ ↑ ↑ 
 3 2 1 
Temos então P3 = 3! = 6 anagramas. 
 
d) Neste item poderíamos pensar que bastaria somar os resultados obtidos em (a) e (b) e 
obtermos 24 + 24= 48 anagramas. 
 
Mas, veja, por exemplo, o anagrama MOTIS. Ele foi contado em (a) quando 
fixamos M na primeira posição e também foi contado em (b) quando fixamos O na 
segunda posição. Portanto, ao somarmos os resultados de (a) e (b) alguns anagramas 
foram contados duas vezes. 
 
 
Em Análise Combinatória, nenhum elemento poderá ser contado mais de uma 
vez, assim como não podemos nos esquecer de contar algum deles. 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 2
 
 
Foram contados duas vezes os anagramas que têm M na primeira posição e O na 
segunda posição, ou seja, 6 anagramas e, portanto, devem ser excluídos uma vez. 
 
Logo, o número de anagramas que começam por M ou têm O na segunda posição 
é igual a 24 + 24 – 6 = 42. 
 
 
 
Na realidade, o que usamos no item (d) foi o Princípio da Inclusão-Exclusão da 
Teoria dos Conjuntos. Ele nos fornece o número de elementos da união de um número 
finito de conjuntos finitos não necessariamente disjuntos. 
 
 
 Sejam A o conjunto dos anagramas que começam por M e B o conjunto dos 
anagramas que têm O na segunda posição. 
 
Denotemos por n(A) ou #A o número de elementos de A. 
 
O diagrama abaixo mostra a situação descrita no exemplo 1. 
 
 
 
Temos que n(A ∩ B) = 6, n(A – B) = n(B – A) = 18. 
 
 
 
 
Princípio da Inclusão-Exclusão (para dois conjuntos) 
 
Se A e B são conjuntos finitos então 
 
n(A ∪ B) = n(A) + n(B) – n(A ∩ B) (1) 
 
 
 
Exemplo 2 
 
Quantos são os anagramas da palavra MISTO que têm M na primeira posição 
ou O na segunda posição ou S no final? 
 
 
Seja C o conjunto dos anagramas da palavra MISTO que têm S na última posição. 
 
Desejamos n(A ∪B∪C). 
 
Tendo somente um elemento fixo n(C) = 4! = 24. 
Fundação CECIERJ Maria de Fatima Soares da Silva
 3
 
 
Como vimos no exemplo 1 não podemos apenas somar 24 + 24 + 24. 
Utilizando o Princípio da Inclusão-Exclusão para dois conjuntos e outros resultados da 
Teoria dos Conjuntos podemos escrever: 
 
n(A∪B∪C) = n[ (A ∪ B) ∪ C] = (por (1)) 
 
 = n(A ∪ B) + n(C) - n[ (A ∪ B) ∩ C] (resultado da teoria dos conjuntos) 
 
 = n(A ∪ B) + n(C) - n[ (A ∩ C) ∪ (B ∩ C)] (por (1) duas vezes) 
 
 = n(A) + n(B) – n(A∩B) + n(C) - {n(A∩C) + n(B∩C) – n[(A∩C) ∩ (B∩C)] } 
 
 = n(A) + n(B) + n(C) - n(A∩B) - n(A∩C) - n(B∩C) + n(A∩B∩C) 
 
 
O resultado anterior é o Princípio da Inclusão-Exclusão para 3 conjuntos 
finitos. 
 
 Voltando ao exemplo 2, já vimos que n(A) = n(B) = n(C) = 24 e n(A∩B) = 6 
Temos que n(B∩C) = n(A∩C) = 3! = 6, pois duas posições estão fixadas, e 
n(A∩B∩C)=2! = 2 
 
Concluindo, o número de anagramas da palavra MISTO que têm M na primeira 
posição ou O na segunda posição ou S no final é 24 + 24 + 24 – 6 - 6 - 6 + 2 = 56. 
 
 
Exemplo 3 
 
 Quantos são os números inteiros positivos menores ou iguais a 600 que são 
divisíveis por 3, 4 ou 5? 
 
Sejam: 
A o conjunto dos números inteiros positivos menores ou iguais a 600 divisíveis por 3; 
B o conjunto dos números inteiros positivos menores ou iguais a 600 divisíveis por 4; 
C o conjunto dos números inteiros positivos menores ou iguais a 600 divisíveis por 5; 
 
Pede-se n( A B C∪ ∪ ). 
 
Pelo Princípio da Inclusão-Exclusão temos que 
n( A B C∪ ∪ ) = n(A) + n(B) + n(C) – n( A B∩ ) – n( A C∩ ) – n(B C∩ ) + n( A B C∩ ∩ ) 
 
Observemos, inicialmente, que os números 3, 4 e 5 são primos entre si, logo não 
há inclusão de conjuntos. Portanto, AU B U C não pode ser escrita como a união de 
apenas dois dos conjuntos A, B e C. Logo, temos que usar o princípio da inclusão-
exclusão para 3 conjuntos. 
 
Calculemos, inicialmente o número de elementos de A = {3, 6, 9, ..., 600}. 
Pode-se dizer que os elementos de A são da forma 3k para k pertencente ao 
conjunto {1, 2, 3, ... , 200} e, portanto, n(A) = 200. 
Podemos também observar que os elementos de A estão em uma progressão 
aritmética onde o primeiro termo é 3 e a razão também é 3 e ak = 600 onde k = n(A). 
Fundação CECIERJ Maria de Fatima Soares da Silva
 4
 
 
Da fórmula do termo geral de uma PA, ak = a1 + (k – 1)r, temos 600 = 3 + 3k – 3, 
logo k = n(A) = 600
3
 = 200. 
Da mesma forma obtemos: 
 
n(B) = 600
4
 = 150; n(C) = 600
5
 = 120; 
n( A B∩ ) = 600
3.4
 = 600
12
 = 50; n( A C∩ ) = 600
3.5
 = 600
15
 = 40; 
n( B C∩ ) = 600
4.5
 = 600
20
 = 30; n( A B C∩ ∩ ) = 600
3.4.5
 = 600
60
 = 10 
 
Logo, 
 
n(( A B C∪ ∪ ) = 200 + 150 + 120 –50 – 40 – 30 + 10 = 360 
 
 
No caso geral, isto é, no caso do número de elementos da união de n conjuntos 
finitos temos: 
 
 
Princípio da Inclusão-Exclusão 
 
Se Ai , 1 ≤ i ≤ n, são conjuntos finitos então n(A1 ∪ A2 ∪ ... ∪ An) = 
=∑
=
n
i
iAn
1
)( - ∑
≤<≤
∩
nji
ji AAn
1
)( + ∑
≤<<≤
∩∩
nkji
kji AAAn
1
)( - ... + (-1)n-1 n( nAAA ∩∩∩ ...21 ) 
 
Exercícios propostos 
1 – Sendo A, B e C conjuntos finitos, mostre que 
n[(A ∪ B) ∩ C] = n[(A ∩ C) ∪ (B ∩ C)] 
 
2 - Quantos inteiros entre 1 e 1000 são divisíveis por 3 ou 7? R.: 428 
 
3- Quantos são os anagramas da palavra AGRIDOCE que 
a) têm a letra O na 3ª posição; 
b) terminam por vogal; 
c) terminam por consoante e começam com vogal; 
d) têm a letra O na 3ª posição ou a letra I na 2ª posição; 
e) têm a letra O na 3ª posição ou a letra I na 3ª posição; 
f) têm as letras D, O e C juntas e em qualquer posição ; 
g) têm as letras D, O e C juntas e nessa ordem; 
h) têm as letras A na primeira posição ou O na segunda posição ou E na quarta posição? 
i) têm as letras A na primeira posição ou O na segunda posição ou E na quarta posição 
ou D na última posição? 
R.:a) 5040; b) 20160; c) 11520; d) 9360; e) 10080; f) 4320; g) 720; h) 13080; 
i) 16296 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 5
 
 
4 – Em uma universidade, m professores se distribuem em 8 bancas examinadoras de 
modo que cada professor participe exatamente de duas bancas e cada duas bancas têm 
exatamente um professor em comum. Qual é o valor de m? R.: 28 
 
5 – Quantos são os anagramas da palavra INTERVALO que têm aletra E na primeira 
posição, mas não têm a letra R na última posição? R.: 35280 
 
6 – Quantos inteiros de 1 a 100000 são divisíveis por 2, 3, 4 ou 5? R.: 73334 
 
7- Quantos números inteiros positivos de 1 a 1000000 são 
a) quadrados perfeitos? R.: 1000 
b) cubos perfeitos? R.: 100 
c) quadrados perfeitos ou cubos perfeitos? R.: 1090 
d) nem quadrados perfeitos nem cubos perfeitos? R.: 998910 
 
8 – (FUVEST) Seis times de futebol, entre os quais estão A e B, vão disputar um 
campeonato. Suponha que na classificação final não existam empates. 
Um indivíduo fez duas apostas sobre a classificação final. Na primeira, apostou 
que A não seria campeão; na segunda, apostou que B não seria o último colocado. Em 
quantas das 720 classificações possíveis esse indivíduo ganha as duas apostas? 
 R.: 504 
 
9 - De quantas maneiras se podem sentar, em fila, 3 brasileiros, 3 peruanos e 3 
argentinos de modo que não haja 3 compatriotas juntos? R.: 283824 
 
10 - Demonstre o caso geral do Princípio da Inclusão-Exclusão. 
 
Fundação CECIERJ Maria de Fatima Soares da Silva