md aula10 2014 1

Prévia do material em texto

4 – Princípio de Inclusão e Exclusão 
 
 
 Estamos interessados na obtenção de uma fórmula que nos forneça o 
número total de elementos na união de um número finito de conjuntos. 
 
 
4.1 – União de n conjuntos 
 
 
Exemplo 4.1 
 
 Numa classe de 30 alunos, 14 falam inglês, 5 falam alemão e 3 falam inglês 
e alemão. Quantos alunos falam pelo menos uma língua dentre inglês e alemão? 
 
Solução 
 
 Seja A o conjunto dos que falam inglês e B o conjunto dos que falam 
alemão. Não podemos aqui somar simplesmente 14 com 5, pois estariam sendo 
contados duas vezes aqueles que falam os dois idiomas. Nesse caso, 
 
B)n(An(B)n(A)n I−+= . 
 
 
 
Observação 
 
→n(X) cardinalidade do conjunto X ( (X)# ) 
 
 
Exemplo 4.2 
 
Quantos inteiros entre 1 e 3600, inclusive, são divisíveis por 3, 5 ou 7? 
 
Solução 
 
 Representamos por A , B e C os conjuntos dos inteiros que são divisíveis, 
respectivamente, por 3, 5 e 7. Temos assim que: 
 
1200
3
3600
n(A) =



= . 
720
5
3600
n(B) =



= 
514
7
3600
n(C) =



= 
240
15
3600B)n(A =



=I 
171
21
3600C)n(A =



=I 
102
35
3600C)n(B =



=I 
34
105
3600C)Bn(A =



=II 
 
 
Observação 
 
→



7
3600
o maior inteiro menor ou igual a 
7
3600
 
 
 
 
C)Bn(AC)n(BC)n(AB)n(An(C)n(B)n(A)n IIIII +−−−++= 
 
 =1200+720+514-240-171-102+34=1955 
 
 
 
 
Observação 
 
→++ n(C)n(B)n(A) conta os números divisíveis por 3 e 5, 3 e 7, e 5 e 7 
 duas vezes 
 
→−−− C)n(AC)n(AB)n(A III remove a dupla contagem 
 
→C)Bn(A II os números que são divisíveis por 3, 5 e 7 foram contados 
 3 vezes e removidos 3 vezes e com esse termo são 
 acrescentados 
 
 
 
Teorema 4.1 (Princípio de inclusão e exclusão) 
 
 O número de elementos na união de n conjuntos finitos 1A , 2A , 3A , ..., 
nA é dada por 
 
∑∑∑
≤<<≤≤<≤=
+−=
nkji1
kji
nji1
ji
n
1i
in21 )AAn(A)An(A)n(A)A...An(A IIIUUU 
∑
≤<<<≤
−
npkji1
pkji )AAAn(A III +...+ )A...An(A1)( n211-n III− . (4.1) 
 
 
Demonstração 
 
 Um elemento que pertença a p , para n1,2,3,...,p = , dos conjuntos iA 
deve ser contado por (4.1) exatamente uma vez. Considere um elemento 
pertencente a exatamente p conjuntos, 
p21 iii A,...,A,A . Este elemento será 
contado p vezes em 
 
∑
=
n
1i
i )n(A . 
 
Em 
 
∑
≤<≤ nji1
ji )An(A I 
 
será contado 2pC , em 
∑
≤<<≤ nkji1
kji )AAn(A II 
 
3
pC , e assim sucessivamente até o termo 
 
)A...An(A n21 III , 
 
que nos dará uma contribuição igual a 1. Somando todas as contribuições teremos 
 
p
p
1p3
p
2
p
1
p C)1(...CCC −−+−+− . 
Sabemos que 
 
p
p
0i
ipii
p b)(abaC +=∑
=
−
. 
 
Tomando 1a −= e 1b = na expressão acima, vem que 
 
01)1(C)1(...CCCC11)(C pppp3p2p1p0p
p
0i
ipii
p =+−=−+−−+−=−∑
=
−
 . 
 
 
Isto implica que a soma 
 
1C)1(...CCC pp1p3p2p1p =−+−+− − , 
pois 1C0p = . 
 
 
Exemplo 4.3 
 
Quantos são os inteiros entre 1 e 42000, inclusive, que não são divisíveis 
por 2, por 3 e nem por 7? 
 
Solução 
 
Temos que: 
 
,42000}{1,2,3,...A = 
 
IN}k 2k,x|A{xA1 ∈=∈= 
 
IN}k 3k,x|A{xA2 ∈=∈= 
 
IN}k 7k,x|A{xA3 ∈=∈= 
 
)AAn(An(A)n 321 UU−= = )n(A)n(A)n(An(A) 321 −−− 
 )AAn(A)An(A)An(A)An(A 321323121 IIIII −+++ 
 
42000n(A) = 
 
21000
2
42000)n(A1 =



= 
 
14000
3
42000)n(A 2 =



= 
 
6000
7
42000)n(A 3 =



= 
 
7000
6
42000)An(A 21 =



=I 
 
3000
14
42000)An(A 31 =



=I 
 
2000
21
42000)An(A 32 =



=I 
1000
42
42000)AAn(A 321 =



=II 
 
1200010002000300070006000140002100042000n =−+++−−−= 
 
 
Exemplo 4.4 
 
Dado um inteiro positivo m e sendo r21 p..., ,p ,p números menores do que 
m ou iguais a ele e primos entre si, encontrar uma fórmula para o cálculo do 
número de inteiros positivos menores do que m ou iguais a ele e que não são 
divisíveis por nenhum dos números r21 p..., ,p ,p . 
 Solução 
 
Sejam 
 
m},{1,2,3,...A = ; 
}ppor divisível éx |A{xA 11 ∈= ; 
}ppor divisível éx |A{xA 22 ∈= ; 
. 
. 
. 
}ppor divisível éx |A{xA rr ∈= . 
 
O número procurado será dado por 
 
=− )A...An(An(A) r21 UUU 
 
∑∑∑
≤<<≤≤<≤=
−+−=
rkji1
kji
rji1
ji
r
1i
i )AAn(A)An(A)n(An(A) III 
∑
≤<<<≤
+
rpkji1
pkji )AAAn(A III +...+ )A...An(A1)( r21r III− , 
 
mas como 
 
mn(A) = , 






=
i
i p
m)n(A , 








=
ji
ji pp
m)An(A I , 








=
kji
kji ppp
m)AAn(A II , 
. 
. 
. 








=
rkji
rkji p...ppp
m)A...AAn(A III , 
 
 
 
temos 
 
=− )A...An(An(A) r21 UUU 
 
∑∑∑
≤<<≤≤<≤= 







−








+





−=
rkji1 kjirji1 ji
r
1i i ppp
m
pp
m
p
m
m 
 ∑
≤<<<≤ 







+
rpkji1 pkji pppp
m
+...+








−
rkji
r
p...ppp
m1)( , 
 
 
 
Exemplo 4.5 
 
Quantos são os inteiros positivos menores do que 30 ou iguais a 30 que 
não são divisíveis por 3, 5 ou 8? 
 
Solução 
 
Nesse caso, temos que 30m = , 3p1 = , 5p2 = e 8p3 = . Temos assim 
que: 
 
10
3
30
=



 6
5
30
=



 3
8
30
=



 2
53
30
=



⋅
 
1
83
30
=



⋅
 0
85
30
=



⋅
 0
853
30
=



⋅⋅
 
 
 
Logo, 
 
140012361030n =−+++−−−= .