Principio Inclusão Exclusão

Prévia do material em texto

Princ´ıpio da Inclusa˜o e Exclusa˜o (P.I.E.)
Vamos considerar o seguinte problema:
Num grupo de 100 pessoas, 50 falam Ingleˆs, 40 franceˆs e 20
falam ambas as l´ınguas. Quantas delas na˜o falam nenhuma
dessas l´ınguas?
Resposta: 100-50-40+ 20=30
1 / 23
Situac¸a˜o no diagrama
I A = 100 pessoas
I B = 50 pessoas que falam ingleˆs
I C = 40 pessoas que falam franceˆs
I B ∩ C = 20 pessoas que falam ingleˆs e franceˆs
Para contar o nu´mero de uma certa classe de objetos, no´s
exclu´ımos aqueles que na˜o deveriam ser inclu´ıdos na contagem
e em troca, compensamos a contagem, incluindo aqueles que
foram exclu´ıdos incorretamente (a mais).
2 / 23
Notac¸a˜o
Considere um conjunto R com N objetos.
Sejam a1, · · · , ar um conjunto de propriedades que os objetos de
R podem ter ou na˜o.
I N = nu´mero de objetos de R;
I N(ai ) = nu´mero de elementos de R que tem a propriedade ai
I N(ai ) = nu´mero de elementos de R que na˜o tem a
propriedade ai ;
I N(aiaj) = nu´mero de elementos de R que tem a propriedade
ai e a propriedade aj ;
I N(aiaj) = nu´mero de elementos de R que tem a propriedade
aj e na˜o tem a propriedade ai ;
I N(aiaj) = nu´mero de elementos de R que na˜o tem a
propriedade ai e na˜o tem a propriedade aj ;
I · · ·
3 / 23
E´ imediato que:
I N(ai ) = N − N(ai ), porque cada um dos N objetos ou tem a
propriedade ai (neste caso esta´ contado em N(ai ) ), ou na˜o
tem a propriedade ai (neste caso esta´ contado em N(ai )).
I N(aiaj) = N(aj)− N(aiaj), porque cada um dos N(aj)
objetos que tem a propriedade aj , ou tem a propriedade ai
(neste caso esta´ contado em N(aiaj)), ou na˜o tem a
propriedade ai (neste caso esta´ contado em N(aiaj)).
Usando argumento similar, temos:
I N(aiaj) = N − N(aiaj)− N(aiaj)− N(aiaj)
Reescrevendo:
N(aiaj) = N − [N(ai )−N(aiaj)]− [N(aj)−N(aiaj)]−N(aiaj)
= N − N(ai )− N(aj) + N(aiaj)
4 / 23
Voltando ao primeiro exemplo:
Aplicando a notac¸a˜o anterior, temos:
I R = grupo de pessoas: N = 100
I a1 = propriedade de falar ingleˆs: N(a1) = 50
I a2 = propriedade de falar franceˆs: N(a2) = 40
I a1a2 = propriedade de falar ingleˆs e franceˆs: N(a1a2) = 20
N(a1a2) = N−N(a1)−N(a2)+N(a1a2) = 100−50−40+20 = 30
5 / 23
Teorema: Princ´ıpio da Inclusa˜o e Exclusa˜o
Sejam R um conjunto com N elementos e a1, · · · , ar as
propriedades que os elementos de R podem ter, ou na˜o. Enta˜o
N(a1 · · · ar ) = N − N(a1)− · · · − N(ar )+
+N(a1a2) + N(a1a3) + · · ·+ N(ar−1ar )−
−N(a1a2a3)− · · · − N(ar−2ar−1ar ) + · · ·+
(−1)rN(a1 · · · ar ) =
= N −
∑
i
N(ai ) +
∑
i≤j
N(aiaj)−
∑
i≤j≤k
N(aiajak)+
+ · · ·+ (−1)rN(a1 · · · ar )
6 / 23
Exemplo
1. Temos 12 bolas onde, 2 sa˜o pintadas de vermelho, 1 de azul,
1 de branco, 2 sa˜o pintadas de vermenlho e azul, 1 de
vermelho e branco, 3 de vermelho, azul e branco. Quantas
bolas na˜o sa˜o pintadas (isto e´, na˜o recebem nenhuma cor)?
Soluc¸a˜o: Seja R o conjunto de bolas, |R| = N = 12.
Sejam a1, a2, a3 tais que
a1 propriedade de que a bola recebe a cor vermelha;
a2 propriedade de que a bola recebe a cor azul e
a3 propriedade de que a bola recebe a cor branca.
7 / 23
continuac¸a˜o...
N = 12, N(a1) = 8, N(a2) = 6, N(a3) = 5, N(a1a2) = 5,
N(a1a3) = 4, N(a2a3) = 3 e N(a1a2a3) = 3.
N(a1a2a3) = N − N(a1)− N(a2)− N(a3)+
+N(a1a2) + N(a1a3) + N(a2a3)− N(a1a2a3) =
= 12− 8− 6− 5 + 5 + 4 + 3− 3 = 2
8 / 23
Demonstrac¸a˜o do Teorema
Por induc¸a˜o no nu´mero de propriedades que os objetos podem ter
ou na˜o (induc¸a˜o em r)
I Base da induc¸a˜o: r = 1 (uma u´nica propriedade: a1)
N(a1) = N − N(a1), verdadeira
I Hipo´tese de induc¸a˜o: assuma que a identidade e´ verdadeira
para um conjunto de N objetos podendo ter ate´ r − 1
propriedades:
(1) N(a1 · · · ar−1) = N − N(a1)− · · · − N(ar−1)+
+N(a1a2) + · · ·+ N(ar−2ar−1) + · · ·+ (−1)r−1N(a1 · · · ar−1)
9 / 23
Continuac¸a˜o
Seja R um conjunto com N elementos e a1, · · · , ar as propriedades
que os elementos de R podem ter, ou na˜o. Considere o
subconjunto R′ de R cujos elementos tem a propriedade ar . Esse
conjunto (pela nossa notac¸a˜o) tem N(ar ) elementos. Como os
elementos de R′ podem ter qualquer uma das r − 1 propriedades
a1, · · · , ar−1, temos pela hipo´tese de induc¸a˜o:
(2) N(a1 · · · ar−1ar ) = N(ar )−N(a1ar )−N(a2ar )−· · ·−N(ar−1ar )+
+N(a1a2ar ) + · · ·+ N(ar−2ar−1ar ) + · · ·+
(−1)r−1N(a1 · · · ar )
10 / 23
Subtraindo (2) de (1)
Fazendo (1)− (2), temos:
N(a1 · · · ar−1)− N(a1 · · · ar−1ar ) =
= N − N(a1)− · · · − N(ar−1)− N(ar )+
+N(a1a2)+· · ·+N(ar−2ar−1)+N(ar−1ar )−· · ·+(−1)r−1N(a1 · · · ar )
Como
N(a1 · · · ar−1)− N(a1 · · · ar−1ar ) = N(a1a2 · · · ar )
segue o resultado.
11 / 23
Exemplo 3
Achar o nu´mero de inteiros entre 1 e 250 (inclusive) que na˜o sa˜o
divis´ıveis por nenhum dos inteiros 2, 3, 5 e 7.
a1 propriedade de que um nu´mero e´ divis´ıvel por 2;
a2 propriedade de que um nu´mero e´ divis´ıvel por 3;
a3 propriedade de que um nu´mero e´ divis´ıvel por 5 e
a4 propriedade de que um nu´mero e´ divis´ıvel por 7.
Notac¸a˜o:
bxc = maior inteiro positivo menor ou igual a x
Seja R o conjunto dos inteiros de 1 a 250, |R| = N = 250
Entre os inteiros 1 ate´ 250 temos 125 = 2502 inteiros divis´ıveis por
2.
N(a1) = b2502 c = 125
N(a2) = b2503 c = 83
N(a3) = b2505 c = 50
N(a4) = b2507 c = 35
12 / 23
continuac¸a˜o...
N(a1a2) = b 2502×3c = 41
N(a1a3) = b 2502×5c = 25
N(a1a4) = b 2502×7c = 17
N(a2a3) = b 2503×5c = 16
N(a2a4) = b 2503×7c = 11
N(a3a4) = b 2505×7c = 7
N(a1a2a3) = b 2502×3×5c = 8
N(a1a2a4) = b 2502×3×7c = 5
N(a1a3a4) = b 2502×5×5c = 3
N(a2a3a4) = b 2503×5×7c = 5
N(a1a2a3)a4 = b 2502×3×5×7c = 1
13 / 23
continuac¸a˜o...
Enta˜o, o nu´mero de inteiros que na˜o sa˜o divis´ıveis por 2, nem por
3, nem por 5 e nem por 7 e´:
N(a1a2a3a4) = 250− (125 + 83 + 50 + 35)+
+(41 + 25 + 17 + 16 + 11 + 7)− (8 + 5 + 3 + 2) + 1 = 57
E o nu´mero de inteiros que na˜o sa˜o divis´ıveis por 2 e nem por 7,
mas sa˜o divis´ıveis por 5?
N(a1a3a4) = N(a3)− N(a1a3)− N(a3a4) + N(a1a3a4) =
= 50− 25− 7 + 3 = 21
14 / 23
Definic¸o˜es
I Uma sequeˆncia e´ dita bina´ria quando e´ formada pelos d´ıgitos
0 e 1.
Por exemplo: 0010100011...
I Sequeˆncias terna´rias: formada pelos d´ıgitos 0, 1 e 2.
Por exemplo: 0022100112...
I Sequeˆncias quaterna´rias: formada pelos d´ıgitos 0, 1, 2 e 3.
Por exemplo: 03022133001312...
15 / 23
Exemplo 4
Determine o nu´mero de sequeˆncias quaterna´rias de r d´ıgitos
(r ≥ 3) onde cada um dos d´ıgitos 1, 2 e 3 aparece pelo menos uma
vez.
I Seja R o conjunto das sequeˆncia quaterna´rias com r d´ıgitos
(r ≥ 3):
I a1 = propriedade de que o d´ıgito 1 na˜o aparece na sequeˆncia;
I a2 = propriedade de que o d´ıgito 2 na˜o aparece na sequeˆncia e
I a3 = propriedade de que o d´ıgito 3 na˜o aparece na sequeˆncia.
N(a1a2a3) = N − N(a1)− N(a2)− N(a3)+
+N(a1a2) + N(a1a3) + N(a2a3)− N(a1a2a3)
16 / 23
continuac¸a˜o...
I N = 4r , em cada posic¸a˜o posso colocar 4 d´ıgitos: 0, 1, 2 e 3
I N(a1) = 3r = N(a2) = N(a3), porque excluindo um elemento,
posso colocar os outros 3.
I N(a1a2) = 2r = N(a1a3) = N(a2a3), porque excluindo 2
elementos, posso colocar os outros 2.
I N(a1a2a3) = 1, porque so´ posso colocar o zero.
Logo,
N(a1a2a3) = 4
r − 3× 3r + 3× 2r − 1
17 / 23
Segunda forma do P.I.E
Seja R um conjunto com N elementos e N(ai ∪ aj) =nu´mero de
elementos de R que tem a propriedade ai ou a propriedade aj .
Corola´rio O nu´mero de objetos de R que teˆm pelo menos uma
das propriedades a1, · · · ar e´ dado por
N(a1 ∪ a2 ∪ · · · ∪ ar ) =
=
∑
N(ai )−
∑
N(aiaj) + · · ·+ (−1)r+1N(a1 · · · ar ) =
N − N(a1 · · · ar )
I Prova Seja Ai o subconjunto de elementos de R que teˆm a
propriedade ai . Temos que |Ai | = N(ai ) e |Ai | = N(ai ).
O conjunto A1 ∪ A2 ∪ · · · ∪ Ar consiste de todosos elementos
que tem ao menos uma das propriedades ai .
18 / 23
continuac¸a˜o...
Obs.: N(a1 ∪ · · · ∪ ar ) = |A1 ∪ · · · ∪ Ar | e
N(a1 · · · ar ) = |A1 ∩ · · · ∩ Ar |
|A1 ∪ · · · ∪ Ar | = |R| − |A1 ∪ · · · ∪ Ar |
Mas, pela propriedade de conjuntos, A1 ∪ · · · ∪ Ar = A1 ∩ · · · ∩ Ar .
Logo,
|A1 ∪ · · · ∪ Ar | = |R| − |A1 ∩ · · · ∩ Ar |
Enta˜o,
N(a1 ∪ a2 ∪ · · · ∪ ar ) = N − N(a1 · · · ar )
19 / 23
Exemplo 5
Quantos sa˜o os anagramas da palavra BRASIL em que o B ocupa
o primeiro lugar, ou o R ocupa o segundo lugar ou o L o sexto
lugar?
I a1 = propriedade de ter o B em primeiro lugar;
I a2 = propriedade de ter o R em segundo lugar e
I a3 = propriedade de ter o L em sexto lugar.
Queremos calcular
N(a1 ∪ a2 ∪ a3) = N(a1) + N(a2) + N(a3)− N(a1a2)−
−N(a1a3)− N(a2a3) + N(a1a2a3)
20 / 23
continuac¸a˜o...
I N(a1) = N(a2) = N(a3) = 5!
I N(a1a2) = N(a1a3) = N(a2a3) = 4!, porque fixamos 2 letras e
permutamos as outras e
I N(a1a2a3) = 3! porque fixamos 3 letras e permutamos as
outras.
Logo, N(a1 ∪ a2 ∪ a3) = 3 · 5!− 3 · 4! + 3! = 294
21 / 23
Exemplo 6
Quantas soluc¸o˜es inteiras e estritamente positivas existem para
x1 + x2 + x3 + x4 = 20 tal que 1 ≤ x1 ≤ 6, 1 ≤ x2 ≤ 7, 1 ≤ x3 ≤ 8
e 1 ≤ x4 ≤ 9.
I R = conjunto das soluc¸o˜es inteiras e estritamente positivas da
equac¸a˜o x1 + x2 + x3 + x4 = 20, onde x1, x2, x3 e x4 > 0
I N = |R| = C 1619 , pois resolver a equac¸a˜o nas condic¸o˜es acima,
e´ equivalente a resolver a equac¸a˜o na seguinte mudanc¸a de
variavel: x1 = a+ 1, x2 = b + 1, x3 = c + 1 e x4 = d + 1,
a, b, c , d ≥ 0. Logo, a+ b + c + d = 20− 4 = 16.
22 / 23
continuac¸a˜o...
Considere as propriedades:
I a1 = propriedade de x1 > 6
I a2 = propriedade de x2 > 7
I a3 = propriedade de x3 > 8
I a4 = propriedade de x4 > 9
N(a1a2a3a4)) = N − N(a1)− N(a2)− N(a3)− N(a4)+
+N(a1a2) + N(a1a3) + N(a1a3) + · · ·+ (−1)4N(a1a2a3a4)
23 / 23