Analise Combinatoria

Prévia do material em texto

1
Analise Combinato´ria
1.1 Princ´ıpio Aditivo
Exemplo 1.1
Paulo chegou a uma lanchonete e encontrou as seguintes opc¸o˜es de bebidas dispon´ıveis:
• 4 opc¸o˜es de refrigerante: R1, R2, R3 e R4;
• 3 opc¸o˜es de suco: S1, S2 e S3;
• 2 marcas de a´gua mineral: A1 e A2.
De quantas maneiras ele pode escolher uma bebida?
Para isso, ele tem treˆs hipo´teses: refrigerante, suco ou a´gua. Para cada uma dessas hipo´teses ele tem
um certo nu´mero de opc¸o˜es.
Hipo´teses → Refrigerante ou Suco ou A´gua
Opc¸o˜es → R1R2R3R4 S1S2S3 A1A2
4 3 2
Portanto, ele tem 9 formas (R1, R2, R3, R4, S1, S2, S3, A1, A2) diferentes de escolher uma bebida.
Esse problema ilustra o princ´ıpio aditivo de contagem e estende-se para qualquer quantidade de
hipo´teses.
1.2 Princ´ıpio Fundamental da Contagem
1
Exemplo 1.2
Ao abrir um arma´rio, Fla´via encontrou:
• 3 pares de teˆnis: T1, T2 e T3;
• 2 calc¸as jeans: J1 e J2;
• 4 camisetas: C1, C2, C3 e C4.
De quantas formas diferentes ela pode escolher um conjunto teˆnis-jeans-camiseta para ir ao shopping?
Agora, sua escolha e´ feita em treˆs etapas independentes: escolha do teˆnis, escolha do jeans e escolha da
camiseta. Para cada uma dessas etapas, ela tem um certo nu´mero de opc¸o˜es.
Etapas → Teˆnis e Jeans e Camiseta
Opc¸o˜es → T1T2T3 J1J2 C1C2C3C4
3 2 4
O caso de Fla´via envolve treˆs etapas independentes. Para cada opc¸a˜o de teˆnis que venha a escolher,
ela tem 2 opc¸o˜es para escolha do jeans. Para cada conjunto teˆnis-jeans que tenha escolhido, ela tem 4
opc¸o˜es para escolha da camiseta.
Todos os poss´ıveis resultados do problema de Fla´via podem ser visualizados no esquema a seguir, cha-
mado a´rvore das possibilidades.
T3
J2
C4 T3J2C4
C3 T3J2C3
C2 T3J2C2
C1 T3J2C1
J1
C4 T3J1C4
C3 T3J1C3
C2 T3J1C2
C1 T3J1C1
T2
J2
C4 T2J2C4
C3 T2J2C3
C2 T2J2C2
C1 T2J2C1
J1
C4 T2J1C4
C3 T2J1C3
C2 T2J1C2
C1 T2J1C1
T1
J2
C4 T1J2C4
C3 T1J2C3
C2 T1J2C2
C1 T1J2C1
J1
C4 T1J1C4
C3 T1J1C3
C2 T1J1C2
C1 T1J1C1
Observe que ha´ 24 resultados poss´ıveis. Portanto, ha´ 24 formas diferentes de Fla´via escolher um con-
junto teˆnis-jeans-camiseta. Pela ana´lise da a´rvore, podemos observar que este valor e´ obtido por meio
uma multiplicac¸a˜o: 3× 2× 4 = 24.
Esse exemplo ilustra o princ´ıpio fundamental da contagem , tambe´m conhecido como princ´ıpio
multiplicativo da contagem, e estende-se para qualquer quantidade de etapas. De forma geral, po-
demos enuncia´-lo assim:
Se um acontecimento ocorre em duas etapas sucessivas e independentes, sendo que a pri-
meira 1a situac¸a˜o ocorre de a maneiras e a 2a situac¸a˜o de b maneiras, enta˜o o nu´mero total
de possibilidades de ocorreˆncia desse acontecimento e´ dado pelo produto a.b.
2
Exerc´ıcio 1.1
Um homem vai a um restaurante disposto a comer um so´ prato de carne e uma so´ sobremesa. O carda´pio
oferece oito pratos distintos de carne e cinco pratos diferentes de sobremesa. De quantas formas pode o
homem fazer sua refeic¸a˜o?
Exerc´ıcio 1.2
Uma moc¸a possui 5 blusas e 6 saias. De quantas formas ela pode vestir uma blusa e uma saia?
Exerc´ıcio 1.3
Uma igreja tem 4 portas. Quando vai la´, Marisa sempre entra por uma porta e sai por outra. De quantas
formas diferentes ela pode fazer isso?
Exerc´ıcio 1.4
Utilizando os algarismos 1, 2, 4, 5, 7 e 9, quantos nu´meros naturais maiores que 7000 e de 4 algarismos
distintos podemos formar?
Exerc´ıcio 1.5
Uma fa´brica produz 3 modelos de automo´veis, com 5 opc¸o˜es de cores. Cada um deles esta´ dispon´ıvel
em 2 verso˜es: duas portas e quatro portas. Quantas alternativas diferentes tem um comprador para
adquirir um automo´vel, levando-se em conta essas treˆs varia´veis?
Exerc´ıcio 1.6
Normalmente, o uniforme de um clube de futebol e´ constitu´ıdo por uma camisa, um calc¸a˜o e um par de
meias. Um clube tem 3 opc¸o˜es de camisa, 2 de calc¸o˜es e 2 de meias. Quantas partidas ele pode jogar,
no ma´ximo, sem repetir o uniforme?
Exerc´ıcio 1.7
Numa lanchonete, ha´ 5 tipos de salgado, 3 tipos de sandu´ıche, 2 tipos de suco e 4 marcas de refrigerante.
De quantas formas diferentes um cliente pode escolher:
a) um comest´ıvel?
b) uma bebiba?
c) um salgado e um refrigerante?
d) um sandu´ıche e uma bebida?
e) um comest´ıvel e uma bebida?
3
Exerc´ıcio 1.8
Numa prova de matema´tica, foram dadas 8 sentenc¸as. Em cada uma delas, o aluno deveria marcar uma
das letras: V (verdadeira) ou F (falsa). De quantas maneiras diferentes as 8 marcac¸o˜es podem ser feitas?
Exerc´ıcio 1.9
Utilizando-se so´ os algarismos 1, 2, 4, 6 e 8, formam-se todos os nu´meros de 4 algarismos.
a) Qual e´ o total de nu´meros formados?
b) Quantos na˜o tem algarismo repetido?
c) Quantos teˆm pelo menos um algarismo repetido?
d) Quantos sa˜o pares?
e) Quantos sa˜o maiores que 6000 e na˜o teˆm algarismo repetido?
Exerc´ıcio 1.10
No sistema de emplacamento de ve´ıculos, usam-se letras e algarismos. Um exemplo e´ a placa PMG −
0358. As 3 letras sa˜o escolhidas entre as 26 do alfabeto; os algarismos sa˜o escolhidos entre os 10
dispon´ıveis. Suponha que haja placas com quatro zeros (0000).
a) Quantas placas diferentes podem ser feitas?
b) Quantas teˆm as 3 letras e os 4 algarismos diferentes?
c) Quantas so´ teˆm vogais e algarismos maiores que 6?
d) Quantas teˆm 3 vogais diferentes e o primeiro e o u´ltimo algarismo iguais?
Exerc´ıcio 1.11
Chama-se anagrama de uma palavra, toda palavra (com ou sem significado) obtida, trocando-se suas
letras de posic¸a˜o. Veja, por exemplo, alguns anagramas da palavra AMOR:
AMOR, OMAR, MORA, MARO
Formam-se todos os anagramas da palavra CARINHO.
a) Qual e´ o total de anagramas?
b) Quantos comec¸am por vogal?
c) Quantos terminam em CA, nesta ordem?
d) Quantos teˆm o C e o A juntos, nesta ordem?
4
Exerc´ıcio 1.12
Considere a palavra DILEMA e determine:
a) o nu´mero total de anagramas;
b) o nu´mero de anagramas que comec¸am pela letra D;
c) o nu´mero de anagramas que comec¸am pela letra D e terminam com a letra A;
d) o nu´mero de anagramas que comec¸am com vogal.
Exerc´ıcio 1.13
Da palavra LIVRO:
a) quantos anagramas podemos formar?
b) quantos sa˜o os anagramas que comec¸am por vogal?
c) quantos sa˜o os anagramas que comec¸am por consoante?
Exerc´ıcio 1.14
Da palavra ADESIVO:
a) quantos anagramas podemos formar com as letras SI juntas e nessa ordem?
b) quantos anagramas comec¸am com a letra D e terminam com a letra V?
Exerc´ıcio 1.15
Obter o nu´mero de anagramas formados com as letras da palavra REPU´BLICA, nos quais as vogais
se manteˆm nas respectivas posic¸o˜es.
OBMEP 1.1
(OBMEP 2015) Em uma Olimp´ıada de Matema´tica, foram distribu´ıdas va´rias medalhas de ouro, va´rias
de prata e va´rias de bronze. Cada participante premiado poˆde receber uma u´nica medalha. Aldo, Beto,
Carlos, Diogo e Elvis participaram dessa olimp´ıada e apenas dois deles foram premiados. De quantas
formas diferentes pode ter acontecido essa premiac¸a˜o?
a) 20 b) 30 c) 60 d) 90 e) 120
1.3 Fatorial
5
Definic¸a˜o
Na matema´tica, o fatorial de um nu´mero natural n, representado por n!, e´ o produto de todos os inteiros
positivos menores ou iguais a n. Exemplos:
• 3! = 3.2.1 = 6 • 4! = 4.3.2.1 = 24 • 5! = 5.4.3.2.1 = 120
De uma forma geral podemos escrever:
n! = n.(n− 1).(n− 2) . . . 3.2.1
Por convenc¸a˜o, adotamos 0! = 1.
Exerc´ıcio 1.16
Calcule o valor dos nu´meros fatoriais:
a) 6!
b) 7!
c) 2! + 3!
d) 1! + 4!
e) 3!− 2!
f) 0! + 1!
g) 2!3!
h) 0!5!
i) 4!2!
j) 1!7!
Exerc´ıcio 1.17
Simplifique as expresso˜es:
a)
9!
8!
b)
15!
13!
c)
6!
4!
d)
6!
4!2!
e)
8!
2!6!
f)
8.4!
4!4!
Exerc´ıcio 1.18
Simplifiqueas frac¸o˜es:
a)
n!
(n− 1)!
b)
x!
(x− 2)!
c)
(n+ 1)!
n!
d)
(2x+ 2)!
(2x)!
e)
x!(x+ 2)!
(x− 1)!(x+ 1)!
f)
(n− 1)! + (n− 2)!
n!
Exerc´ıcio 1.19
Resolva as equac¸o˜es:
a)
(n+ 1)!
(n− 1)! = 12 b)
n!
(n− 2)! = 20 c)
(n− 1)!(n+ 2)!
n!(n+ 1)!
= 2
6
Exerc´ıcio 1.20
A soluc¸a˜o da equac¸a˜o
(n+ 2)!(n− 2)!
(n+ 1)!(n− 1)! = 4 e´ um nu´mero natural:
a) par.
b) cubo perfeito.
c) maior que 10.
d) divis´ıvel por 5.
e) mu´ltiplo de 3.
Exerc´ıcio 1.21
Se (x+ 1)! = 3.x!, enta˜o x e´ igual a:
a) 1 b) 2 c) 3 d) 4 e) 5
1.4 Permutac¸a˜o Simples
Exemplo 1.3
Quantos anagramas tem a palavra LA´PIS?
5.4.3.2.1 = 5! = 120
Esse exemplo ilustra um caso de Permutac¸a˜o Simples que, de modo geral, e´ representado pela fo´rmula
Pn = n!
Exerc´ıcio 1.22
De quantos modos 6 pessoas podem se sentar em 6 cadeiras, em fila?
Exerc´ıcio 1.23
De quantos modos 5 homens e 5 mulheres podem se sentar em 5 bancos de 2 lugares, de modo que em
cada banco deve haver um homem e uma mulher?
1.5 Permutac¸a˜o com Elementos Repetidos
7
Exemplo 1.4
Quantos anagramas possui a palavra ATACA?
5.4.3.2.1
3!
=
120
6
= 20
Esse exemplo ilustra um caso de Permutac¸a˜o com elementos repetidos que, de modo geral, e´
representado pela fo´rmula
Pα,β,γ,...,θn =
n!
α!β!γ! . . . θ!
Exerc´ıcio 1.24
Quantos anagramas possui a palavra BARATA?
Exerc´ıcio 1.25
Quantos anagramas possui a palavra CATARATA?
Exerc´ıcio 1.26
Quantos anagramas da palavra BANANA comec¸am por vogal?
Exerc´ıcio 1.27
Quantos anagramas da palavra ABACAXI comec¸am por vogal?
Exerc´ıcio 1.28
De quantos modos podem-se arrumar 4 livros de Matema´tica, 3 de Geografia e 2 de Biologia, numa
estante, de modo que:
a) fiquem dispostos em qualquer ordem;
b) os livros de mesmo assunto fiquem juntos.
8
Exerc´ıcio 1.29
O mapa abaixo ilustra as quadras de um bairro.
A
B
1.6 Arranjo
Exemplo 1.5
Uma escola possui 18 professores. Entre eles, sera˜o escolhidos um diretor, um vice-diretor e um coorde-
nador pedago´gico. Quantas sa˜o as possibilidades de escolha?
18.17.16 = 4896
Esse exemplo ilustra um caso de Arranjo que, de modo geral, e´ representado pela fo´rmula
An,p =
n!
(n− p)!
Exerc´ıcio 1.30
Calcule:
a) A4,3 b) A5,2 c) A12,3 d) A6,4
Exerc´ıcio 1.31
Quantos nu´meros de 3 algarismos distintos podemos formar com os elementos do conjuntoE = {1, 2, 3, 4, 5}?
Exerc´ıcio 1.32
Uma empresa possui 16 funciona´rios administrativos, entre os quais sera˜o escolhidos 3, que disputara˜o
para os cargos de diretor, vice-diretor e tesoureiro. De quantas maneiras pode ser feita a escolha?
9
Exerc´ıcio 1.33
Ju´lio pretende pintar a palavra LIVRE em um cartaz de publicidade, usando uma cor em cada letra.
De quantos modos isso pode ser feito, se ele dispo˜e de 8 cores de tinta?
Exerc´ıcio 1.34
Duas pessoas entram num oˆnibus que tem 7 lugares vagos. De quantas maneiras diferentes as 2 pessoas
podem ocupar esses lugares?
Exerc´ıcio 1.35
Num grande preˆmio de Fo´rmula 1, participara˜o 20 pilotos e somente os 6 primeiros marcam pontos.
Quantas sa˜o as possibilidades de classificac¸a˜o nos 6 primeiros lugares?
1.7 Combinac¸a˜o
Exemplo 1.6
Uma escola possui 5 professores de matema´tica, dos quais 3 sera˜o escolhidos para participar de um
Congresso. De quantas formas esse trio pode ser escolhido?
5.4.3
3!
= 10
Esse exemplo ilustra um caso de Combinac¸a˜o que, de modo geral, e´ representado pela fo´rmula
Cn,p =
n!
(n− p)!p!
Exerc´ıcio 1.36
Calcule:
a) C5,3 b) C7,5 c) C6,2 d) C10,3
Exerc´ıcio 1.37
Devemos escolher 4 pessoas de um grupo de 9 pessoas. De quantas formas isso pode ser feito?
Exerc´ıcio 1.38
Quantos grupos diferentes de 4 laˆmpadas podem ficar acesos em um galpa˜o que tem 10 laˆmpadas?
10
Exerc´ıcio 1.39
Quantas comisso˜es de 5 membros podemos formar numa assembleia de 12 participantes?
Exerc´ıcio 1.40
Numa papelaria tem 8 cadernos de cores diferentes, e quero comprar 3 de cores diferentes. Quantas
possibilidades de escolha eu tenho?
Exerc´ıcio 1.41
Uma prova e´ composta por 15 questo˜es, das quais o aluno deve resolver 10. De quantas formas ele
podera´ escoher as 10 questo˜es?
Exerc´ıcio 1.42
Em uma reunia˜o social, cada pessoa cumprimentou todas as outras, havendo ao todo 45 apertos de ma˜o.
Quantas pessoas havia na reunia˜o?
Exerc´ıcio 1.43
Temos 10 homens e 10 mulheres. Quantas comisso˜es de 5 pessoas podemos formar se em cada uma deve
haver 3 homens e 2 mulheres?
Exerc´ıcio 1.44
Ha´ 12 inscritos em um campeonato de boxe. O nu´mero total de lutas que podem ser realizadas entre os
inscritos e´:
a) 12 b) 24 c) 33 d) 66 e) 132
Exerc´ıcio 1.45
De um total de 10 pessoas, deseja-se formar um grupo com 6 pessoas e outro com 4. De quantas formas
isso pode ser feito?
Exerc´ıcio 1.46
De um total de 12 pessoas, deseja-se formar um grupo com 5 pessoas, outro com 4 e outro com 3. De
quantas formas isso pode ser feito?
Exerc´ıcio 1.47
Numa escola ha´ 15 professores, sendo que 3 deles lecionam Matema´tica. Deseja-se formar uma comissa˜o
de 5 professores para analisar o prec¸os cobrados na cantina da escola. Nessa comissa˜o, exatamente um
membro deve lecionar Matema´tica. De quantas maneiras diferentes pode-se formar a comissa˜o?
11
1.8 Permutac¸a˜o Circular
1.9 Exerc´ıcios de Revisa˜o
Exerc´ıcio 1.48
Num banco de automo´vel o assento pode ocupar 6 posic¸o˜es diferentes e o encosto 5 posic¸o˜es, indepen-
dentes da posic¸a˜o do assento. Combinando assento e encosto, este banco assume
a) 6 posic¸o˜es b) 30 posic¸o˜es c) 90 posic¸o˜es d) 180 posic¸o˜es e) 720 posic¸o˜es
Exerc´ıcio 1.49
Um ma´gico se apresenta em pu´blico vestindo calc¸a e paleto´ de cores diferentes. Para que ele se possa
apresentar em 24 sesso˜es com conjuntos diferentes, o nu´mero mı´nimo de pec¸as (nu´mero de paleto´s mais
nu´mero de calc¸as) de que ele precisa e´
a) 24 b) 11 c) 12 d) 10 e) 8
Exerc´ıcio 1.50
Suponha que no in´ıcio de um jogo voceˆ tenha R$ 2,00 e que so´ possa jogar enquanto tiver dinheiro.
Supondo que cada jogada voceˆ perde ou ganha R$ 1,00, ao final de treˆs jogadas os poss´ıveis resultados
sa˜o
a) R$ 2,00, R$ 3,00 ou R$ 5,00
b) R$ 1,00, R$ 3,00 ou R$ 4,00
c) R$ 0,00, R$ 2,00 ou R$ 4,00
d) R$ 1,00, R$ 3,00 ou R$ 5,00
e) R$ 0,00, R$ 1,00 ou R$ 3,00
Exerc´ıcio 1.51
Uma bandeira e´ formada de 7 listras que devem ser pintadas de 3 cores diferentes. De quantas maneiras
distintas sera´ poss´ıvel pinta´-la de modo que duas listras adjacentes nunca estejam pintadas da mesma
cor?
a) 128 b) 192 c) 35 d) 2187 e) 210
Exerc´ıcio 1.52
Com os algarismos 1, 2, 3, 4, e 5 e sem repetic¸a˜o, pode-se escrever x nu´meros maiores que 2500. O valor
de x e´
a) 78 b) 120 c) 162 d) 198 e) 240
12
Exerc´ıcio 1.53
Dez clubes de futebol disputam um campeonato em dois turnos. No final, dois clubes empatam na
primeira colocac¸a˜o, havendo mais um jogo de desempate. Quantos jogos foram disputados?
a) 101 b) 91 c) 90 d) 46 e) 21
Exerc´ıcio 1.54
Deve ser formada uma comissa˜o constitu´ıda de 3 estat´ısticos e 3 economistas, escolhidos entre 7 es-
tat´ısticos e 6 economistas. De quantas maneiras diferentes podera˜o ser formadas essas comisso˜es?
a) 700 b) 25200 c) 330 d) 650 e) 720
Exerc´ıcio 1.55
Sobre uma mesa sa˜o colocadas em linha 6 moedas. O nu´mero total de modos poss´ıveis pelos quais
podemos obter 2 caras e 4 coroas voltadas para cima e´
a) 360 b) 48 c) 30 d) 120 e) 15
Exerc´ıcio 1.56
10 alunos devem ser distribu´ıdos em 2 classes, de 7 e 3 lugares respectivamente. De quantas maneiras
distintas pode ser feita a distribuic¸a˜o?
a) 720 b) 14400 c) 120 d) 86400 e) 1440
Exerc´ıcio 1.57Sobre a palavra TERERE
a) Quantos sa˜o os seus anagramas?
b) Quantos comec¸am por vogal?
c) Quantos comec¸am por consoante?
13
Exerc´ıcio 1.58
Utilizando apenas os algarismos 1, 2, 4, 5, 7, 8 e 9
a) Quantos nu´meros de 4 d´ıgitos podemos formar?
b) Quantos nu´meros de 4 d´ıgitos distintos podemos formar?
c) Quantos nu´meros pares de 4 d´ıgitos podemos formar?
d) Quantos nu´meros maiores que 5400 e menores que 10.000 podemos formar?
Exerc´ıcio 1.59
Quantos anagramas da palavra NOVELAS possuem as letras V e E juntas e nesta ordem?
Exerc´ıcio 1.60
A partir de um grupo de 12 professores, quer se formar uma comissa˜o com um presidente, um relator e
cinco outros membros. O nu´mero de formas de se compor a comissa˜o e´:
a) 12.772 b) 13.024 c) 25.940 d) 33.264 e) 27.764
Exerc´ıcio 1.61
Quantos subconjuntos de 3 elementos possui o conjunto C = {1, 2, 3, 4, 5}?
Exerc´ıcio 1.62
Quantas diagonais podemos trac¸ar em um pol´ıgono regular de oito lados? Apo´s resolver este problema,
voceˆ poderia dizer quantas diagonais tem um pol´ıgono de n lados?
Exerc´ıcio 1.63
Um grupo de 9 pessoas, dentre elas os irma˜os Joa˜o e Pedro, foi acampar. Na hora de dormir montaram
3 barracas diferentes, sendo que, na primeira, dormiram duas pessoas; na segunda, treˆs pessoas; e, na
terceira, as quatro restantes. De quantos modos diferentes eles se podem organizar, sabendo que a u´nica
restric¸a˜o e´ a de que os irma˜os Joa˜o e Pedro NA˜O podem dormir na mesma barraca?
a) 1260 b) 1225 c) 1155 d) 1050 e) 910
14
Exerc´ıcio 1.64
Numa Caˆmara de Vereadores, trabalham 6 vereadores do partido A, 5 vereadores do partido B e 4
vereadores do partido C. O nu´mero de comisso˜es de 7 vereadores que podem ser formadas, devendo cada
comissa˜o ser constitu´ıda de 3 vereadores do partido A, 2 do partido B e 2 vereadores do partido C, e´
igual a
a) 7 b) 36 c) 152 d) 1200 e) 28800
15