Grátis 12 pág.
- Denunciar
Pré-visualização | Página 1 de 6
Prof. Marcelo Cóser Anglo Oficinas 1 ANÁLISE COMBINATÓRIA Considere os dois problemas abaixo: Em uma corrida envolvendo quatro corredores, quantas são as possibilidades de pódio? Para cada possível 1º lugar, existem três possíveis 2ºs lugares e, para cada um desses segundos, duas opções para 3º colocado. Como mostra o diagrama, são 24 pódios distintos. Em um grupo de quatro alunos, conseguimos formar quantos trios diferentes? Para a resolução desse problema, a estratégia anterior não funciona, pois as escolhas não possuem hierarquia entre si: ser o primeiro, o segundo ou terceiro do trio é indiferente. Observe que no problema anterior a primeira escolha é diferenciada das demais, assim como cada escolha é diferenciada das demais. Em tempo: a resposta do problema, como mostram as possibilidades listadas acima, é 4. A análise combinatória distingue dois tipos de agrupamentos: seqüências e conjuntos. Seqüências São agrupamentos que se diferenciam pelos elementos componentes ou pela ordem desses elementos. Por exemplo, (A, B) ≠ (B, A) pela ordem em que aparecem e (A, B) ≠ (A, C) pelos elementos escolhidos. Observe que ordem implica hierarquia entre escolhas: a ordem somente é importante quando cada escolha tiver uma função diferente no problema. Conjuntos São agrupamentos que se diferenciam somente pelos elementos componentes. No mesmo exemplo anterior, {A, B} = {B, A} e {A, B} ≠ {A, C}. A ordem aqui não é importante. Ou seja, não existe hierarquia e, com isso, cada escolha desempenha o mesmo papel no problema. PRÍNCIPIO FUNDAMENTAL DA CONTAGEM O raciocínio utilizado para a resolução do primeiro problema é muito importante para resolver qualquer problema de Análise Combinatória. Considere um problema onde n decisões independentes devem ser tomadas. Para cada uma dessas decisões existem 1 2 3 1, , , ..., ,n nd d d d d opções de escolha. Tendo em mente a ramificação das escolhas (ou árvore de possibilidades) apresentada anteriormente, sabe-se que a 1ª escolha possui 1d possibilidades, que se ramificam em 2d opções para a 2ª, que por sua vez se ramificam em 3d para a 3ª, e assim sucessivamente, até se ramificar em nd possibilidades para a n-ésima e última escolha. Assim, n decisões independentes com 1 2, , ..., nd d d opções de escolha cada geram um total de 1 2 3 n-1 nd d d d d seqüências. Observe que esse é o número de seqüências e não de conjuntos, pois as decisões são independentes. Ou seja, há hierarquia entre elas. EXERCÍCIOS DE AULA 01) Uma bandeira assimétrica é formada por quatro listras, que devem devem ser coloridas usando-se apenas as cores amarelo, branco e cinza, não devendo listras adjacentes ter a mesma cor. De quantos modos pode ser colorida a bandeira? Se iniciarmos colorindo a primeira lista, a única restrição diz que a listra seguinte deve ser de cor diferente. Assim, 3 2 2 2 24 modos. 02) Quantos números naturais de quatro algarismos distintos existem? Nosso sistema decimal possui 10 algarismos: 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9. O único que não pode iniciar um número é o algarismo “0”. Assim, existem 9 9 8 7 4536 números, já que os algarismos devem ser distintos. Prof. Marcelo Cóser Anglo Oficinas 2 Pequenas dificuldades adiadas costumam transformar-se em grandes dificuldades. Se alguma decisão é mais complicada que as demais, ela deve ser tomada em primeiro lugar . 03) Quantos números naturais de 4 algarismos, que sejam menores que 5000 e divisíveis por 5, podem ser formados usando-se apenas os algarismos 2, 3, 4 e 5? São duas as restrições: o primeiro algarismo não pode ser “5” e o último algarismo, por outro lado, deve ser igual a “5”. Com isso, existem 3 4 4 1 48 números que atendem essas condições. 04) Quantos são os números naturais pares que se escrevem com 3 algarismos distintos? A exigência de algarismos distintos proíbe a repetição. Ainda, para formar números pares exige-se que o último algarismo seja par: 0, 2, 4, 6 ou 8. A dificuldade desse exercício está no fato de “0” não poder ser utilizado como primeiro algarismo. Assim, se ele for escolhido como último, são 9 os possíveis algarismos para o primeiro; no entanto, se não for, existirão somente 8 possíveis primeiros algarismos. Separando em casos: 9 8 1 72 números onde “0” é o último algarismo e 8 8 4 256 números onde “0” não é o último algarismo. Assim, 72 + 256 = 328 números. Outra resolução: existem 9 9 8 648 números com três algarismos distintos. Para que sejam ímpares, o último algarismo deve ser ímpar: 1, 3, 5, 7 ou 9. Assim, 8 8 5 320 números são ímpares. Com isso, 648 - 320 = 328 são números pares. 05) Em quantos números de quatro algarismos o algarismo “5” aparece pelo menos uma vez? A mesma abordagem da segunda resolução do exercício anterior pode ser utilizada: descontando o que não interessa do total. No exercício 2, calculamos em 9.000 o total de números com quatro algarismos. Se o “5” não for utilizado, serão 8 9 9 9 5832 . Logo, serão 9000 - 5832 = 3168 números onde o algarismo “5” aparece pelo menos uma vez. 06) A respeito das letras da palavra “TESOURA”: a) Quantos anagramas apresentam as letras S, O e U juntas e nessa ordem? O enunciado exige que os anagramas formados contem com a junção “SOU”. Assim, as três letras S, O, U serão contados como somente uma opção de agrupamento: afinal, deverão estar juntas e nessa mesma sequência. Com isso, as opções para escolha são as letras T, E, R, A e o agrupamento SOU. Ou seja, 5 opções. Assim, existirão 5 4 3 2 1 120 anagramas. b) Quantos anagramas apresentam as letras S, O e U juntas? O enunciado faz quase a mesma exigência que o anterior, mas retira uma: o agrupamento “SOU” pode aparecer como “USO” ou “SUO”, por exemplo. A exigência da ordem não existe mais. No entanto, a resolução para qualquer ordem segue a mesma: existirão 120 anagramas com “USO” e 120 anagramas com “SUO”. Desse modo, é preciso calcular de quantas maneiras é possível reordenar o agrupamento original “SOU”: 3 2 1 6 maneiras, sendo que cada uma gerará 120 anagramas diferentes. Ou seja, serão 6 120 720 anagramas distintos. c) Quantos anagramas começam por vogal ou terminam por consoante? Das sete letras, três são consoantes e quatro são vogais. Assim, 4 6 5 4 3 2 1 2880 começam por vogal e 6 5 4 3 2 1 3 2160 terminam por consoante. No entanto, os anagramas que começam por vogal e terminam por consoante estão sendo contados em ambos os casos. Esses casos duplos totalizam 4 5 4 3 2 1 3 1440 anagramas. Assim, existem 2880 + 2160 - 1440 = 3600 anagramas nas condições exigidas. Prof. Marcelo Cóser Anglo Oficinas 3 Notação Fatorial n! = n·(n - 1)·(n - 2)·(n - 3)· ... ·3·2·1, com n natural. Além da definição algébrica para fatorial, deve ser compreendida também a definição combinatória: n! é o número de seqüências com n elementos distintos que formamos a partir de n elementos. Por exemplo, 1 1 1 2 2 3 4 3 2 1 4!