Aula 6-Princípios Básicos da Contagem

Prévia do material em texto

Princípios básicos da Contagem
Princípio da Casa dos pombos
Princípio da Casa dos Pombos: Seja k um número natural. Se tivermos n pombos e eles
entrarem em k casas e se n ≥ k + 1, então pelo menos uma casa tem dois ou mais pombos.
Demonstração: Vamos inicialmente identificar a hipótese e a tese da nossa conjectura.
Hipótese: n pombos entram em k casas, n, k ∈ N e n ≥ k + 1.
Tese: Pelo menos uma casa tem mais de 1 pombo.
Vamos demonstrar esse resultado por absurdo. Suponha que n pombos entram em k casas,
que n, k ∈ N e que n ≥ k + 1. Suponha que haja no máximo um pombo por casa. Então
teremos no máximo
k · 1 = k
pombos. O que é um absurdo, pois estamos supondo que existem n pombos e que n > k.
Exemplo 1. Em qualquer grupo de 13 pessoas, pelo menos duas delas fazem aniversário no
mesmo mês.
Exemplo 2. Em qualquer grupo de 27 palavras, pelo menos duas delas começam com a mesma
letra (pois o alfabeto possui 26 letras distintas).
Exemplo 3. Mostre que todo número inteiro n possui um múltiplo que possui apenas algaris-
mos 0′s e 1′s quando escrito na base decimal.
Hipótese: n ∈ Z
Tese: n possui um múltiplo que possui apenas algarismos 0′s e 1′s quando escrito na base deci-
mal.
Vams mostrar por demonstração direta.
Observe que os restos possíveis na divisão de um número por n são 0, 1, 2, 3, ..., n−1 e, portanto,
existem n restos possíveis. Se tomarmos os n+ 1 números
1, 11, 111, 1.111, 11.111, ...., 1...11︸ ︷︷ ︸)n+ 1 números 1
então, pelo princípio da casa dos pombos, pelo menos dois desses números possuem o mesmo
resto quando dividido por n. Sejam a e b dois dentre esses números que tem o mesmo resto r
quando divididos por n. Temos que a = xn+ r e b = yn+ r, onde x, y, r ∈ Z. Logo,
a− b = (xn+ r)− (yn+ r) = xn+ r − yn+ r = xn+ yn = (x+ y)︸ ︷︷ ︸
∈Z
n
Logo, a− b é um número composto apenas de 0′s e 1′s que é múltiplo de n.
Utilizamos a notação dxe para representar o menor inteiro maior ou igual a um número real
x. Ou seja, se x ∈ R, então
dxe = n ↔ (n ∈ Z, x ≤ n e @ m ∈ Z / x ≤ m < n)
Observação 1. Se x ∈ Z, então dxe = x.
1
Por exemplo,
• d1e = 1
• d−2e = −2
• d1, 5e = 2
• ⌈1
3
⌉
= 1
• ⌈4
3
⌉
= 2
• dpie = 4
• ⌈√3⌉ = 2
• d−1, 5e = −1
• ⌈√5⌉ = 3
• ⌈−√5⌉ = −2, pois (2 < √5 < 3 → −3 < √5 < −2)
Observação 2. dxe < x+ 1.
Generalização do Princípio da Casa dos Pombos: Seja k um número natural. Se tiver-
mos n pombos e eles entrarem em k casas, então existe pelo menos uma casa com
⌈
n
k
⌉
ou mais
pombos.
Demonstração: Vamos inicialmente identificar a hipótese e a tese da nossa conjectura.
Hipótese: n pombos entram em k casas, n, k ∈ N.
Tese: Pelo menos uma casa tem
⌈
n
k
⌉
ou mais pombos.
Vamos demonstrar esse resultado por absurdo. Suponha que n pombos entrem em k casas
e que n, k ∈ N. Suponha que haja no máximo ⌈n
k
⌉ − 1 pombos por casa. Então teremos no
máximo
k ·
(⌈n
k
⌉
− 1
)
pombos. Mas,
k ·
(⌈n
k
⌉
− 1
)
< k
(( n
k
+ 1
)
− 1
)
= k
(n
k
+ 1− 1
)
= k · n
k
= n
O que é um absurdo, pois estamos supondo que existem n pombos e k · (⌈n
k
⌉− 1) < n.
Exemplo 4. Em qualquer grupo de 100 pessoas, pelo menos 9 delas fazem aniversário no
mesmo mês, pois
100
12
= 8, 33333....
e, portanto,
⌈
100
12
⌉
= 9.
2
Exemplo 5. Quantas cartas de um baralho de 52 cartas devem ser selecionadas para garantir
que pelo menos 4 delas tenham o mesmo naipe.
Como temos 4 naipes distintos no jogo, temos que selecionar n cartas do baralho de tal forma
que
⌈
n
4
⌉
= 4. Para tanto, devemos ter
3 <
n
4
≤ 4
12 < n ≤ 16
O menor inteiro que satisfaz a condição é n = 13. Logo, se selecionarmos 13 cartas do baralho
garantiremos que pelo menos 4 delas tem o mesmo naipe.
Alguns conceitos importantes
Para entender o princípio do produto e o princípio da soma, é importante entender os
seguintes conceitos envolvendo a teoria de conjuntos:
Definição 1. Um conjunto é uma coleção de elementos.
A definição de conjunto é uma definição bem genérica, pois os elementos de um conjunto
podem ser de qualquer natureza. Por exemplo, podemos ter um conjunto de frutas, um conjunto
de números, um conjunto de plantas, um conjunto de pessoas etc.
Definição 2. Se A é um conjunto finito, então definimos a cardinalidade de A como sendo o
número de elementos distintos do conjunto A e o denotamos por |A|.
Exemplo 6. Se A = {1, 0,−1, 7}, então |A| = 4.
Definição 3. O produto cartesiano dos conjuntos A1 e A2 é o conjunto A1 × A2 de todos os
pares ordenados (a1, a2) em que a1 é um elemento de A1 e a2 é um elemento de A2. Ou seja,
A1 × A2 = {(a1, a2) | a1 ∈ A1 e a2 ∈ A2}
Observação 3. No caso particular em que os dois conjuntos são iguais, denotamos A×A por
A2.
Exemplo 7. Se A1 = {1, 2, 0} e A2 = {−1, 3, 0}, então
A1 × A2 = {(1,−1), (1, 3), (1, 0), (2,−1), (2, 3), (2, 0), (0,−1), (0, 3), (0, 0)}
Definição 4. O produto cartesiano dos conjuntos A1, A2, A3, ..., Ak é o conjunto
A1×A2×A3× ...×Ak de todas as k-uplas ordenadas (a1, a2, a3, ..., ak) em que a1 é um elemento
de A1, a2 é um elemento de A2, a3 é um elemento de A3, ... e ak é um elemento de Ak. Ou
seja,
A1 × A2 × A3 × ...× Ak = {(a1, a2, a3, ..., ak) | a1 ∈ A1, a2 ∈ A2, a3 ∈ A3, ..., ak ∈ Ak}
Observação 4. No caso particular em que os conjuntos são iguais, denotamos A× A× ...× A︸ ︷︷ ︸
k vezes
por Ak.
Exemplo 8. Se A1 = {1, 2}, A2 = {−1, 3} e A3 = {0, 1} , então
A1 × A2 × A3 = {(1,−1, 0), (1,−1, 1), (1, 3, 0), (1, 3, 1), (2,−1, 0), (2,−1, 1), (2, 3, 0), (2, 3, 1)}
3
Princípio do produto
Suponha que você tenha um procedimento que pode ser dividido em duas tarefas sequenciais.
Se existem n1 formas de concluir a primeira tarefa e n2 formas de concluir a segunda tarefa,
então existem n1 · n2 formas de concluir o procedimento.
Observe que esse princípio pode ser enunciado como: se A1 é um conjunto com n1 elementos
e A2 é um conjunto com n2 elementos, então o produto cartesiano A1 × A2 possui n1 · n2
elementos. Em outras palavras, existem n1 · n2 duplas ordenadas distintas (a1, a2) tais que
a1 ∈ A1 e a2 ∈ A2. Ou seja,
|A1 × A2| = |A1| · |A2|
Exemplo 9. Maria confecciona mochilas artesanais. Ela possui 5 tipos de pano e 3 tipos de
fecho. Quantas mochilas distintas Maria consegue confeccionar?
Resolução: Maria consegue confeccionar 5 · 3 = 15 mochilas distintas, pois para cada tipo
de pano, ela pode utilizar 3 fechos distintos. Observe que se A1 é o conjunto dos panos dispo-
níveis e A2 é o conjunto dos fechos disponíveis, então
A1 × A2 = {(pano, fecho) | pano ∈ A1, fecho ∈ A2}
é o conjunto de todas as possíveis mochilas distintas que Maria consegue produzir. Como
|A1 × A2| = |A1| · |A2| = 5 · 3 = 15, então Maria consegue confeccionar 15 mochilas distintas.
Exemplo 10. As cadeiras de um auditório devem ser etiquetadas com uma letra do nosso al-
fabeto e um número natural até 100. Quantas cadeiras podem ser etiquetadas de forma distinta?
Resolução: Como temos 26 letras no nosso alfabeto de 100 números disponíveis, então pode-
mos etiquetar 26 ·100 = 2600 cadeiras de forma distinta. De fato, se A1 é o conjunto das letras
do alfabeto e A2 = {n ∈ N | n ≤ 100}, então
A1 × A2 = {(letra, número) | letra ∈ A1, número ∈ A2}
é o conjunto de todas as possíveis etiquetas distintas. Como |A1×A2| = |A1| · |A2| = 26 · 100 =
2600, então existem 2600 etiquetas distintas possíveis.
Suponha que você tenha um procedimento que pode ser dividido em k tarefas sequenciais.
Se existem n1 formas de concluir a primeira tarefa, n2 formas de concluir a segunda tarefa, ...
e nk formas de concluir a k-ésima tarefa, então existem n1 · n2 · ... · nk formas de concluir o
procedimento.
Observe que esse princípio pode ser enunciado como: se A1 é um conjunto com n1 elementos,
A2 é um conjunto com n2 elementos, ..., Ak é um conjunto com nk elementos, então o produto
cartesiano A1 × A2 × ...× Ak possui n1 · n2 · ... · nk elementos. Em outras palavras, existem
n1 · n2 ... · nk k-uplas ordenadas distintas (a1, a2, ..., ak) tais que a1 ∈ A1, a2 ∈ A2, ... ak ∈ Ak.
Ou seja,
|A1 × A2 × ...× Ak| = |A1| · |A2| · ... · |Ak|
Exemplo 11. Maria confecciona mochilas artesanais. Ela possui 5 tipos de pano, 3 tipos de
fecho e 4 modelos diferentes de mochila. Quantas mochilas distintas Maria consegue confecci-
onar?
Resolução: Maria consegue confeccionar 5 · 3 · 4 = 60 mochilas distintas, pois para cada
tipo de pano, ela pode utilizar 3 fechos distintos e 4 modelos distintos. Observe que se A1 é o
4
conjunto dos panos disponíveis, A2 é o conjunto dos fechos disponíveis e A3 é o conjunto dos
modelos de mochila, então
A1 × A2 × A3 = {(pano, fecho,modelo) | pano ∈ A1, fecho ∈ A2, modelo ∈ A3}
é o conjunto de todas as possíveis mochilas distintas que Maria consegue produzir. Como
|A1×A2×A3| = |A1| · |A2| · |A3| = 5 ·3 ·4 = 60, então Maria consegue confeccionar 60 mochilas
distintas.
Exemplo 12. As placas de carro antigas são compostas por uma sequência de 3 letras e 4
números. Quantas placas de carro antigas distintas podem ser geradas?
Resolução: Podem ser geradas 26 · 26 · 26 · 10 · 10 · 10 · 10 = 175.760.000 placas distintas.
De fato, se A1 é o conjunto das letras do nosso alfabeto e A2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, então
A1×A1×A1×A2×A2×A2×A2 = A31×A42 = {(l1, l2, l3, n1, n2, n3, n4) | l1, l2, l3 ∈ A1, n1, n2, n3, n4 ∈ A2}
é o conjunto de todas as placas distintas possíveis. Como |A31×A42| = |A1|3 · |A2|4 = 263 · 104 =
175.760.000, então podem ser geradas 175.760.000 placas distintas.
Exemplo 13. Quantas senhas distintas de 6 caracteres numéricos existem?
Resolução: Podem ser geradas 10 · 10 · 10 · 10 · 10 · 10 = 106 = 1.000.000 senhas distintas. De
fato, se A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, então
A× A× A× A× A× A = A6 = {(n1, n2, n3, n4, n5, n6) | n1, n2, n3, n4, n5, n6 ∈ A}
é o conjunto de todas as senhas possíveis. Como |A6| = |A|6 = 1.000.000, então podem ser
geradas 1.000.000 de senhas distintas.
Exemplo 14. Quantos números de 6 dígitos existem?
Resolução: Se A1 = {1, 2, 3, 4, 5, 6, 7, 8, 9} e A2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, então
A1 × A2 × A2 × A2 = A1 × A32 = {(n1, n2, n3, n4) | n1 ∈ A1, n2, n3, n4 ∈ A}
é o conjunto de todos os números de seis dígitos possíveis (pois não consideramos os números
de 5 dígitos precedidos por um zero como sendo um número de seis dígitos). Como
|A1 × A32| = |A1| · |A2|3 = 9 · 103 = 9000
então existem 9.000 números de 6 dígitos.
Princípio da Soma
Suponha que você tenha um procedimento que pode ser realizado selecionando uma das n1
formas listadas no grupo 1 ou uma das n2 formas listadas do grupo 2 e que nenhuma forma
seja comum nas duas listagens. Então existem n1 + n2 formas de concluir o procedimento.
Observe que esse princípio pode ser enunciado como: se A1 é um conjunto com n1 elementos
e A2 é um conjunto com n2 elementos e se A1 ∩ A2 = ∅, então
|A1 ∪ A2| = |A1|+ |A2|
5
Exemplo 15. Suponha que você tem dinheiro para assistir um filme no cinema ou uma peça
no teatro, mas não tem dinheiro suficiente para assistir mais de uma coisa. Se tiverem 7 filmes
em cartaz no cinema e 4 peças diferentes no teatro, então quantos programas diferentes você
pode fazer?
Resolução: Se A1 é o conjunto dos filmes do cinema e A2 é o conjunto das peças no tea-
tro, então (como A1 ∩ A2 = ∅)
|A1 ∪ A2| = |A1|+ |A2| = 7 + 4 = 11
e portanto, existem 11 possibilidades de programa para você.
Suponha que você tenha um procedimento que pode ser realizado selecionando uma das n1
formas listadas no grupo 1, uma das n2 formas listadas do grupo 2, ... ou uma das nk formas
listadas no grupo k e que nenhuma forma seja comum em duas listagens distintas. Então
existem n1 + n2 + ...+ nk formas de concluir o procedimento.
Observe que esse princípio pode ser enunciado como: se A1 é um conjunto com n1 elementos,
A2 é um conjunto com n2 elementos, ..., Ak é um conjunto com nk elementos e se
A1 ∩ A2 ∩ ... ∩ Ak = ∅, então
|A1 ∪ A2 ∪ ... ∪ Ak| = |A1|+ |A2|+ ...+ |Ak|
Exemplo 16. Suponha que você quer selecionar um membro estudantil para um colegiado da
universidade e que esse membro estudantil pode ser selecionado entre graduandos, alunos de
especialização, mestrandos ou doutorandos e que nenhum aluno cursa dois níveis de escolari-
dade distintos. Se existem 400 alunos de graduação, 30 alunos de especialização, 25 alunos de
mestrado e 20 alunos de doutorado, então quantas possibilidades distintas existem para esse
membro do colegiado?
Resolução: Se A1 é o conjunto dos alunos de graduação, A2 é o conjunto dos alunos de
especialização, A3 é o conjunto dos alunos de mestrado e A4 é o conjunto dos alunos de douto-
rados, então (como A1 ∩ A2 ∩ A3 ∩ A4 = ∅)
|A1 ∪ A2 ∪ A3 ∪ A4| = |A1|+ |A2|+ |A3|+ |A4| = 400 + 30 + 25 + 20 = 475
e portanto, existem 475 possibilidades para esse membro do colegiado.
Exemplo 17. Suponha que a senha de acesso a um site deva ter entre 4 e 6 caracteres alfanu-
méricos. Quantas senhas distintas podem ser criadas?
Resolução: Sejam S4 é o conjunto de senhas de 4 caracteres, S5 é o conjunto de senhas
de 5 caracteres e S6 é o conjunto de senhas de 6 caracteres. Como existem 26 letras no nosso
alfabeto e 10 algarismos, então cada entrada da senha pode ser selecionada entre 26 + 10 = 36
caracteres distintos. Logo,
|S4| = 364 = 1.679.616
|S5| = 365 = 60.466.176
|S6| = 366 = 2.176.782.336
Como S4 ∩ S5 ∩ S6 = ∅, então existem
|S4 ∪ S5 ∪ S6| = |S4|+ |S5|+ |S6| = 1.679.616 + 60.466.176 + 2.176.782.336 = 2.299.394.304
senhas distintas entre 4 e 6 caracteres alfanuméricos e, portanto, podem ser criadas 2.299.394.304
senhas distintas para esse site.
6
Exemplo 18. Suponha que a senha de acesso a um site deva ter entre 4 e 6 caracteres alfanu-
méricos e que entre esses caracteres pelo menos 1 deve ser numérico. Quantas senhas distintas
podem ser criadas?
Resolução: Já sabemos que existem 2.299.394.304 senhas distintas entre 4 e 6 caracteres
alfanuméricos. Mas, como queremos que as senhas tenham pelo menos 1 caracter numérico,
então é necessárico remover desse conjunto de senhas as senhas de 4 a 6 dígitos compostas
apenas de letras. Sejam L4 o conjunto de senhas de 4 caracteres, L5 o conjunto de senhas de 5
caracteres e L6 o conjunto de senhas de 6 caracteres compostos apenas de letras. Como existem
26 letras no nosso alfabeto, então
|L4| = 264 = 456.976
|L5| = 265 = 11.881.376
|L6| = 266 = 308.915.776
Como L4 ∩ L5 ∩ L6 = ∅, então existem
|L4 ∪ L5 ∪ L6| = |L4|+ |L5|+ |L6| = 456.976 + 11.881.376 + 308.915.776 = 321.254.128
senhas distintas entre 4 e 6 caracteres compostas apenas de letras. Logo, podem ser criadas
|S4 ∪ S5 ∪ S6| − |L4 ∪ L5 ∪ L6| = 2.299.394.304− 321.254.128 = 1.978.140.176
senhas distintas para esse site.
Exemplo 19. Suponha que a senha de acesso a um site deva ter entre 4 e 6 caracteres alfanu-
méricos e que entre esses caracteres pelo menos 1 deve ser numérico e pelo menos 1 deve ser
uma letra. Quantas senhas distintas podem ser criadas?
Resolução: Já sabemos que podem ser criadas 1.978.140.176 senhas distintas contendo pelo
menos um caracter numérico. Como queremos que as senhas tenham pelo menos 1 letra tam-
bém, então é necessárico remover desse conjunto de senhas as senhas de 4 a 6 dígitos compostas
apenas de números. Sejam N4 o conjunto de senhas de 4 caracteres, N5 o conjunto de senhas
de 5 caracteres e N6 o conjunto de senhas de 6 caracteres compostos apenas de números. Como
existem 10 algarismos distintos, então
|N4| = 104 = 10.000
|N5| = 105 = 100.000
|N6| = 106 = 1.000.000
Como L4 ∩ L5 ∩ L6 = ∅, então existem
|L4 ∪ L5 ∪ L6| = |L4|+ |L5|+ |L6| = 10.000 + 100.000 + 1.000.000 = 1.110.000
senhas distintas entre 4 e 6 caracteres compostas apenas de números. Logo, podem ser criadas
1.978.140.176− 1.110.000 = 1.977.030.176
senhas distintaspara esse site.
7