Nivel2-Combinatoria-Aula-4-Lista-exercicios-resolucao

Prévia do material em texto

POTI NÍVEL 2 
Combinatória 
Contagem II 
Resolução da Lista de exercícios da aula do dia 01/06 
 
(1) De quantas maneiras diferentes um homem pode se vestir, sabendo que ele possui 
dois sapatos, duas calças e três camisas? 
Por aplicação direta do Princípio Multiplicativo: 2x2x3 = 12 
(2) Quantos subconjuntos possui o conjunto {0, 1, 2, 3, ..., 10}? 
A pergunta do enunciado equivale à esta: quantas são as possibilidades de 
formarmos um subconjunto do conjunto acima? Logo, trata-se aqui de um problema de 
contagem. 
Para respondê-la notemos que para cada elemento do conjunto original existem 
duas possibilidades para o subconjunto: ou o elemento pertence a ele ou não pertence. 
Como o conjunto original possui 11 elementos, então, usando o Princípio Multiplicativo, 
as possibilidades de subconjuntos são: 2x2x ... x2 = 211. 
Note que não faz diferença para a resolução do problema quais elementos 
pertencem ao conjunto original, mas unicamente quantos elementos pertencem a ele. 
Assim, por exemplo, se ao invés do conjunto {0, 1, 2, 3, ...., 10} tomarmos o conjunto 
{10, 11, 12, 13, ..., 20} (que possui a mesma quantidade de elementos) a resposta para 
a questão será exatamente a mesma. 
(3) Quantos subconjuntos possui um conjunto com n elementos? 
Generalizando o raciocínio usado na questão anterior, teremos: 2n. 
(4) Quantos são os números naturais pares que se escrevem com três algarismos 
distintos? 
 Como procuramos por números pares, é mais conveniente que comecemos a 
análise da quantidade de possibilidades pelo último algarismo. 
Devemos separar o problema em dois casos: 
 (1°) O último algarismo é zero. Aqui, as possibilidades são 9 para o primeiro 
algarismo (o zero não entra na contagem), 8 para o segundo (o número escolhido como 
primeiro algarismo não entra na contagem e nem o zero) e 1 para o último (o próprio 
zero fixado). Portanto, as possibilidades são: 9x8 = 72; 
 (2°) O último algarismo é 2, 4, 6 ou 8. Aqui, as possibilidades são 4 para o último 
algarismo, 8 para o primeiro algarismo (não podemos usar nem o zero e nem o algarismo 
escolhido anteriormente) e 8 para o segundo (agora podemos voltar a usar o zero). 
Portanto, as possibilidades são: 8x8x4 = 256 
 Quando separamos um problema de contagem em casos, a quantidade total de 
possibilidades é dada pela soma da quantidade de cada caso, ou seja, a operação 
aritmética que corresponde à divisão por casos é a soma. 
 Assim, para esta questão a quantidade de números é a soma da quantidade 
fornecida em (1°) com a quantidade fornecida em (2°). Ou seja, 72 + 256 = 328. 
(5) O alfabeto da Zumbilândia possui apenas 3 letras: C, S e M. As criaturas que lá vivem 
conseguem formar palavras com no máximo 4 caracteres. Quantas palavras existem 
na Zumbilândia? 
 Aqui temos 4 casos: 
 (1°) Palavras com 1 caractere: as possibilidades são 3; 
 (2°) Palavras com 2 caracteres: as possibilidades são 3x3 = 9; 
 (3°) Palavras com 3 caracteres: as possiblidades são 3x3x3 = 27; 
 (4°) Palavras com 4 caracteres: as possiblidades são 3x3x3x3 = 81. 
 Portanto, a quantidade total de possibilidades é: 3 + 9 + 27 + 81 = 120. 
(6) De um grupo de 7 pessoas, devemos escolher 3 delas para formar um pódio 
(primeiro, segundo e terceiro lugares). De quantas formas podemos fazer isso? 
 Escolhamos o 1° lugar do pódio: há 7 possibilidades de escolha. Depois o 2° lugar: 
restaram 6 possibilidades. Por fim, o 3° lugar: restaram 5 possibilidades. Logo, pelo 
Princípio Multiplicativo, as possibilidades são: 7x6x5 = 210. 
(7) De um grupo de 7 pessoas, devemos escolher 3 delas para formar um comitê (sem 
hierarquias). De quantas formas podemos fazer isso? 
 Note que para cada comitê de três pessoas existem 3x2x1 = 6 possibilidades de 
pódio. Assim, temos: [quantidade de pódios] = 6x[quantidade de comitês], ou seja, 
[quantidade de comitês] = [quantidade de pódios]/6. 
 Logo, usando a resposta ao item anterior, a quantidade de comitês é: 210/6 = 
35. 
(8) Quantos anagramas possui a palavra matematica (desconsiderando o acento)? 
 Se tivéssemos uma palavra com todas as letras distintas, bastaria usar o Princípio 
Multiplicativo: por exemplo, a quantidade de anagramas da palavra ZUMBI é 5! = 120. 
 O que dificulta um pouco a questão é o fato de haverem letras repetidas: assim, 
se numa permutação trocarmos o primeiro ‘a’ de ‘matematica’ pelo segundo ‘a’, a 
palavra será exatamente a mesma. 
 Para abordar o problema, vamos colocar um índice numerando as letras 
repetidas de ‘matematica’: 
m1a1t1em2a2t2ica3 
 Se tomássemos todas essas letras como distintas, o numero de anagramas seria 
10!. Porém, qualquer permutação dentro do conjunto {a1, a2, a3}, dentro do conjunto 
{m1, m2} e dentro do conjunto {t1, t2} produzem o mesmo anagrama. Note que há 3!x2x2 
possibilidades de tais permutações. Dessa forma, cada anagrama foi contado 3!x2x2 
vezes. Assim, para compensar essas repetições do mesmo anagrama devemos dividir a 
quantia de 10! pela quantidade de repetições. Ou seja, a quantidade de anagramas 
distintos é dada por: 
10!/(3!x2x2) 
 
(9) Seja um alfabeto que contenha os símbolos: a1, a2, a3, ..., an. Uma palavra qualquer 
desse alfabeto é uma combinação finita de tais símbolos. Suponha que nela o símbolo 
a1 se repete j1 vezes, o símbolo a2 se repete j2 vezes, assim por diante, até o símbolo 
an, que se repete jn vezes (com j1, j2, ..., jn ≥ 0). Descubra uma fórmula para encontrar 
a quantidade de anagramas da palavra. 
Resposta: (j1 + j2 +... + jn)!/j1!xj2!x... xjn! 
 A questão é mais fácil do que parece, pois o raciocínio é basicamente o mesmo 
que o que foi usado na resposta à questão anterior: no numerador da fração aparece o 
fatorial da quantidade total de letras que a palavra possui e no denominador aparece a 
multiplicação entre os fatoriais da quantidade de vezes em que cada letra se repete. 
(10) De quantas formas podemos por 8 pessoas em uma fila se Alice e Bob devem estar 
juntos, e Carol deve estar em algum lugar atrás de Daniel? 
Como Alice e Bob devem estar sempre juntos, podemos imaginar que eles sejam 
uma pessoa só. Assim, teríamos agora 7 pessoas para ordenar: existem 7! possibilidades 
de fazer isso. Mas, embora Alice e Bob estejam sempre juntos, há duas possibilidades 
de isso ocorrer: Alice estar na frente de Bob ou Bob na frente de Alice. Logo, devemos 
multiplicar 7! por 2. 
Vejamos como fica a segunda condição imposta pelo enunciado. Note que a cada 
configuração em que Carol está atrás de Daniel corresponde uma (e apenas uma) 
configuração na qual eles trocam de posição (Carol passa a estar na frente de Daniel) e 
a posição dos restantes mantém-se a mesma. Assim, em exatamente metade das 
possibilidades de fila Carol está na frente e na outra metade ela está atrás de Daniel. 
Assim, essa segunda condição nos diz que devemos dividir por 2 o resultado obtido a 
partir da primeira condição do enunciado. 
Portanto, a resposta é: 7!x2/2 = 7! 
(11) Escrevem-se todos os inteiros de 1 a 9999. Quantos números têm pelo menos um 
zero? 
 O melhor aqui é seguir o seguinte caminho: ao invés de calcular diretamente 
quantos números têm pelo menos um zero, vamos calcular quantos números não têm 
nenhum zero e depois subtrair essa quantia de 9999 (que é o total de números, com ou 
sem zero). 
 Para isso consideremos 4 casos: 
 (1°) Algarismos sem o zero e com um dígito: 9 
 (2°) Algarismos sem o zero e com dois dígitos: 9x9 = 81 
 (3°) Algarismos sem o zero e com 3 dígitos: 9x9x9 = 729 
 (4°) Algarismos sem o zero e com 4 dígitos: 9x9x9x9 = 6561 
 Logo, a quantia total de números que não têm nenhum zero entre seus 
algarismos é dada pela soma das quantias fornecidas pelos 4 casos acima: 9 + 81 + 729 
+ 6561 = 7380. 
 Portanto, a quantidade de algarismos que possuem pelo menos um zero é: 
9999 – 7380 = 2619 
(12) Quantos são os números de quatro algarismos que possuem pelo menos um dígito 
repetido? 
 Repetindo o caminho seguido noexercício acima, não vamos calcular 
diretamente a quantidade de números de quatro algarismos que possuem pelo menos 
um dígito repetido: ao invés disso, calcularemos a quantidade de algarismos que não 
possuem nenhum dígito repetido e depois subtrair tal quantia do total de algarismos 
com quatro dígitos. 
 Existem 9x9x8x7 = 4536 números de quatro algarismo sem nenhum dígito 
repetido. 
 Existem 9999 – 999 = 9000 números de quatro dígitos. 
 Portanto, a quantidade de números de quatro algarismos com pelo menos um 
dígito repetido é: 
9000 – 4536 = 4464 
(13) Em uma festa havia 6 homens e 4 mulheres. De quantos modos podemos formar 
3 pares com essas pessoas? 
 Aqui estamos diante da seguinte situação. Há dois grupos, um com os 6 homens 
e o outro com as 4 mulheres. Para formar um par devemos escolher uma pessoa do 
grupo dos homens e uma do grupo das mulheres. 
 Formemos o primeiro par. Para isso temos 6 possibilidades de escolher um 
homem e 4 de escolher uma mulher. Logo, temos 6x4 possibilidades de escolher o 
primeiro par. 
 Formemos agora o segundo par. Restaram 5 possibilidades de escolher um 
homem e 3 de uma mulher. Logo, temos 5x3 possibilidades de escolher o segundo par. 
 Por fim, o terceiro par. Restaram 4 possibilidades de escolher um homem e 2 de 
uma mulher: logo 4x2 possibilidades de escolher o terceiro para. 
 Portanto, podemos formar os 3 pares de (6x4)x(5x3)x(4x2) modos distintos. 
Porém a formação desses pares se deu de maneira ordenada (foi escolhido um primeiro 
par, depois um segundo e depois um terceiro), mas para o nosso problema não importa 
a ordem em que os pares foram formados, apenas quais foram os pares. 
 Aqui temos uma situação parecida com a do exercício (7), só que agora as coisas 
ordenadas das quais queremos “tirar” a ordenação são os próprios casais (os pares). 
Como para cada conjunto de 3 casais existem 3! ordenações possíveis, então 
(analogamente ao exercício (7)) devemos dividir o resultado obtido com a ordenação 
pela quantidade de ordenações. Ou seja, a resposta será: 
(6x4)x(5x3)x(4x2)/3! = 480 modos de formar três pares. 
(14) Em uma sala de aula existem a meninas e b meninos. De quantas formas eles 
podem ficar em uma fila, se as meninas devem ficar em ordem crescente de peso, e 
os meninos em ordem decrescente de peso? (Suponha que duas pessoas quaisquer 
não tenham o mesmo peso). 
Para entregar. 
(15) Quantos números de três dígitos possuem todos os seus algarismos com a mesma 
paridade? 
Resposta: 225 
(16) Quantos são os números de quatro dígitos distintos que não possuem dois 
algarismos consecutivos com a mesma paridade? 
Resposta: 720 
(17) De quantos modos podemos pintar (usando uma de quatro cores) as casas da 
figura abaixo de modo que as casas vizinhas tenham cores diferentes? 
 
 
Resposta: 84. 
 
(18) Na cidade Gótica as placas das motos consistem de três letras. A primeira letra 
deve estar no conjunto {C, H, L, P, R}, a segunda letra no conjunto {A, I, O} e a terceira 
letra no conjunto {D, M, N, T}. Certo dia, decidiu-se aumentar o número de placas 
usando duas novas letras: J e K. O intendente dos transportes ordenou que as novas 
letras fossem postas em conjuntos diferentes. Determine com qual opção podemos 
obter o maior número de placas. 
Resposta: o número máximo é 100 e ocorre quando as novas opções são adicionadas ao 
segundo e ao terceiro conjunto. 
(19) De quantas maneiras podemos por três torres de mesma cor em um tabuleiro 8 x 
8 de modo que nenhuma delas ataque a outra? 
Resposta: 64x49x36/3! 
(20) De quantas maneiras podemos colocar um rei preto e um rei branco em um 
tabuleiro de xadrez (8 x 8) sem que nenhum deles ataque o outro? 
Para entregar. 
(21) Considere um torneio de xadrez com 10 participantes. Na primeira rodada cada 
participante joga somente uma vez, de modo que há cinco jogos realizados 
simultaneamente. De quantas maneiras esta primeira rodada pode ser realizada? 
Para entregar. 
(22) Cada um dos seis segmentos da figura abaixo deve ser pintado de uma de quatro 
cores de modo que segmentos vizinhos não tenham a mesma cor. De quantas 
maneiras podemos fazer isso? 
 
 
 Para entregar. 
(23) (Desafio!) Doze cavaleiros estão sentados em torno de uma mesa redonda. Cada 
um dos 12 cavaleiros considera seus dois vizinhos como rivais. Deseja-se formar um 
grupo de 5 cavaleiros para salvar uma princesa. Nesse grupo não poderá haver 
cavaleiros rivais. Determine de quantas maneiras é possível escolher esse grupo. 
Para entregar. 
(24) (Desafio!) Duas casas de um tabuleiro 7 x 7 são pintadas de amarelo e as outras 
são pintadas de verde. Duas pinturas são ditas equivalentes se uma é obtida da outra 
a partir de uma rotação aplicada no plano do tabuleiro. Quantas pinturas 
inequivalentes existem? (Dica: considere a simetria em relação à casa central do 
tabuleiro). 
Para entregar.