Análise Combinatória Prof. Marlon ANÁLISE COMBINATÓRIA é uma parte da matemática que estuda os agrupamentos de elementos sem precisar de enumerá-los. A origem desse assunto está ligada ao estudo dos jogos de azar, tais como: lançamento de dados, jogos de cartas, etc. Atualmente, a estimativa de acertos em jogos populares como: loteria esportiva, loto, loteria federal, etc., além de utilizações mais específicas, como confecções de horários, de planos de produção, de números de placas de automóveis etc. FATORIAL É UMA OPERAÇÃO ! Ex.: 2! = 2 x 1 = 2 3! = 3 x 2 x 1 = 6 4! = 4 x 3 x 2 x 1 = 24 5! = 5 x 4 x 3 x 2 x 1 = 120 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720 Convenção 0! = 1 1! = 1 ANÁLISE COMBINATÓRIA FATORIAL 5! = 5.4.3.2.1 = 120 4! = 4.3.2.1 = 24 3! = 3.2.1 = 6 2! = 2.1 = 2 1! = 1 CONVENÇÃO 0! = 1 n! = n.(n 1) . (n 2) . (n 3). .... 2 . 1 Exemplo: Calcular o valor de: a) 4! + 3! 24 + 6 30 10! 10. 9.8! = 90 = c) 8! 8! b) 7! 7.6.5.4.3.2.1 5040 Observe que: 4!+3! 7! (n + 1)! = (n + 1).n.(n – 1).(n – 2).(n – 3).... (n + 1)! = (n + 1).n.(n – 1)! d) 50!49! O conjunto solução de: Determine a soma dos valores 49! 50.49!– 49! 49! (n 1)! 210 é: (n 1)! (n 1)! 210 (n 1)! de m que satisfazem a equação (m – 3)! = 1 (m – 3)! = 1! ou (m – 3)! = 0! m–3=1 m=4 m–3=0 m=3 49! (50 – 1) (n + 1).n.(n – 1)! = 210 (n – 1)! 49! Logo a soma dos valores de m 49 (n + 1).n = 210 n2 + n – 210 = 0 n’ = 14 n’’ = - 15 (n tem que ser natural) é7 Observação: n! = n (n – 1)! Ex.: 8! = 8 . 7! 10! = 10 . 9! Exemplo:Simplificar a expressão: 100! 100 99 98! 9900 98! 98! ( x 1)! 56. Resolva a equação: ( x 1)! ( x 1)! ( x 1)(x)(x 1)! 56 56 ( x 1)(x) 56 ( x 1)! ( x 1)! 1 225 x x 56 x x 56 0 x 2 x 7 1 15 x 2 x -8 2 2 Resposta: x = 7, pois não existe fatorial de um número negativo PRINCÍPIO FUNDAMENTAL DE CONTAGEM – Princípio da Multiplicação Árvore de possibilidades – princípio geral que pode ser usado para se resolver muitos problemas de contagem. EXEMPLO: Uma criança pode escolher uma entre duas balas, uma rosa e uma preta, e um entre três chicletes, um amarelo, um verde e um branco. Quantos conjuntos diferentes a criança pode ter? R A {R, A} V P B {R, V} {R, B} A {P, A} Escolha da bala V B {P, V} {P, B} Escolha do chiclete Trocando a seqüência de eventos: A R {A, R} P {A, P} V R {V, R} B P {V, P} R {B, R} Escolha do chiclete P Escolha da bala {B, P} Número de possibilidades é o mesmo: 2 x 3 = 3 x 2 = 6. Princípio da Multiplicação Se existem n1 resultados possíveis para um primeiro evento e n2 para um segundo, então existem n1 . n2 resultados possíveis para a seqüência de dois eventos. EXEMPLO: A última parte do seu número de telefone contém quatro dígitos. Quantos desses números de quatro dígitos existem? 10 . 10 . 10. 10 = 10000 números diferentes EXEMPLO: Com relação ao Ex.23, quantos números de quatro dígitos existem se um mesmo dígito não puder ser repetido? 10 . 9 . 8 . 7 = 5040 números diferentes EXEMPLO: a) De quantas maneiras podemos escolher três representantes em um grupo de 25 pessoas? 25 . 24 . 23 = 13800 b) De quantas maneiras podemos escolher três representantes, para três comissões, um para cada comissão, em um grupo de 25 pessoas, se um representante pode participar de mais 25 . 25 . 25 = de uma comissão? 15625 EXERCÍCIOS RESOLVIDOS 01. Uma moça possui 5 camisas e 4 saias, de quantas maneiras ela poderá se vestir? A escolha de uma camisa poderá ser feita de cinco maneiras diferentes. Escolhida a primeira camisa poderá escolher uma das quatro saias. Portanto, o número total de escolhas será: 4 x 5 = 20 02. Uma moeda é lançada três vezes. Qual o número de seqüências possíveis de cara e coroa? Indicaremos por C o resultado cara e K o resultado coroa. Queremos o número de triplas ordenadas(a,b,c) onde a {C,K},b {C,K} e c {C,K}, logo, o resultado procurado é 2.2.2 = 8 Pelo o Diagrama da Árvore C C C–C–C K C–C–K C C–K–C K C–K–K C K C K–C–C K K–C–K C K–K–C K K–K-K C K K 03. Quantos números de 3 algarismos podemos formar com os algarismos significativos (1 a 9)? 9 x 9 x 9 = 729 números E se fossem com algarismos distintos? 9 x 8 x 7 = 504 números 04. Quantos números de quatro algarismos distintos podemos formar no sistema de numeração decimal? Resolução: Algarismos: 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9 9 x 9 x 8 x 7 O número não começar por 0 (zero), logo: 9 . 9 . 8. 7 = 4.536 Resposta: 4.536 números 05. Em uma corrida de 6 carros, quantas são as possibilidades do 1º, 2º e 3º lugares? 1º lugar 2º lugar 6 3º lugar x 5 x 4 = 120 possib. 06. Quantos são os divisores de 72? Os divisores de 72 são do tipo 2x . 3y (pois 72 = 23.32) onde: x {0, 1, 2, 3} e y {0, 1, 2}. Logo teremos: 4 possibilidades para a escolha do expoente x e 3 possibilidades para a escolha do expoente y. Total: 4 x 3 = 12 07. Quantos resultados podemos obter na loteria esportiva? Como são 14 jogos, e para cada um dos jogos temos: coluna 1, coluna do meio e coluna 2. Pelo P.F.C., teremos: Jogo 1 Jogo 2 C1 Cm C2 3 ... C1 Cm C2 x 3 Jogo 14 C1 Cm C2 x ... x 3 = 314 EM RESUMO: 1º) Quantas escolhas devem ser feitas. 2º) Quantas opções cada escolha tem. 3º) Multiplicar tudo! Se o problema não depender da ordem (por exemplo: comissões, escolhas, jogos, equipes, urnas, jogo da sena, aperto de mão, casais, grupos, etc.) dividimos o resultado pelo fatorial das escolhas. 08. Existem 3 linhas de ônibus ligando a cidade A à cidade B, e 4 outras ligando B à cidade C. Uma pessoa deseja viajar de A a C, passando por B. De quantos modos diferentes a pessoa poderá fazer essa viagem? Resolução: de A para B = 3 possibilidades de B para C = 4 possibilidades Logo, pelo princípio fundamental de contagem, temos: 3 . 4 = 12 Resposta: 12 modos 09. A placa de um automóvel é formada por duas letras seguidas por um número de quatro algarismos. Com as letras A e R e os algarismos ímpares, quantas placas diferentes podem ser constituídas, de modo que o número não tenha algarismo repetido? Resolução: Placa: 2 . 2 . 5 . 4 . 3 . 2 Pelo princípio fundamental da contagem, temos: 2 . 2 . 5. 4. 3. 2 = 480 Resposta: 480 placas 10. Quantos números de três algarismos distintos podemos formar com os algarismos 2, 3, 4, 5, e 7? 5 x 4 x 3 5 x 4 x 3 = 60 Respostas: 60 números 11. Com os algarismos de 1 a 9, quantos números de telefone podem formar-se com 6 algarismos, de maneira que cada número tenha prefixo 51 e os restantes sejam números todos diferentes, inclusive dos números que formam o prefixo? Resolução: Algarismos: 1, 2, 3, 4, 5, 6, 7, 8 e 9 Prefixo 7 x 6 x 5 x 4 colocando-se o prefixo 51, restam 7 algarismos, logo: 7 . 6 . 5. 4 = 840 Resposta: 840 números 12. Um tabuleiro especial de xadrez possui 16 casas dispostas em 4 linhas e 4 colunas. Um jogador deseja colocar 4 peças no tabuleiro, de tal forma que, em cada linha e cada coluna, seja colocada apenas uma peça. De quantas maneiras as 4 peças poderão ser colocadas? Resolução: Para se colocar 01 peça temos 16 maneiras. Para a 3ª e 4ª peças temos, respectivamente, 4 e 1 maneiras. Logo: 16 . 9 . 4 . 1 = 576 Resposta: 576 maneiras 13. Um torneio esportivo entre duas escolas será decidido numa partida de duplas mistas de tênis. A Escola E inscreveu nesta modalidade 6 rapazes e 4 moças. A equipe de tenistas da Escola F conta com 5 rapazes e 3 moças. Calcule de quantas maneiras poderemos escolher os quatro jogadores que farão a partida decisiva, sabendo que uma das jogadoras da equipe E não admite jogar contra seu namorado, que faz parte da equipe F. Resolução: Cálculo da quantidade de maneiras de formação das equipes: Escola E 6. 4 = 24 maneiras Escola F 5 . 3 = 15 maneiras Assim, os quatro jogadores podem ser escolhidos de: 24 . 15 = 360 maneiras. Excluindo os casos nos quais os namorados jogam entre si, que são em números de: (6 . 1) . (1 . 3) = 18, temos: 360 – 18 = 342 Resposta: 342 maneiras 14. De quantos modos pode-se pintar as faces laterais de uma pirâmide pentagonal regular, utilizando-se oito cores diferentes, sendo cada face de uma única cor? Resolução: Supondo-se que todas as cinco faces laterais da pirâmide sejam pintadas com cores diferentes duas a duas, e que a pirâmide esteja fixa, o número de modos de pintar suas faces laterais, utilizando 8 cores diferentes, será dado por: 8 . 7 . 6 . 5 . 4 = 6.720 Resposta: 6.720 modos 15) (Cesgranrio-2005) A senha de certo cadeado é composta por 4 algarismos ímpares, repetidos ou não. Somando-se os dois primeiros algarismos dessa senha, o resultado é 8; somando-se os dois últimos, o resultado é 10. Uma pessoa que siga tais informações abrirá esse cadeado em no máximo n tentativas, sem repetir nenhuma. O valor de n é igual a: a) 9 b) 15 c) 20 d) 24 e) 30 Resolução: Algarismos ímpares: 1, 3, 5, 7 e 9 Soma 8 : 1 e 7; 3 e 5 ; 5 e 3 ; 7 e 1, ou seja, 04 opções; Soma 10 : 1 e 9; 3 e 7; 5 e 5; 7 e 3; 9 e 1, ou seja, 05 opções. Total de tentativas : 04 x 05 = 20 Portanto n = 20 tentativas. 16. Observe o diagrama O número de ligações distintas entre X e Z é: a) 39 b) 41 c) 35 d) 45 Resolução: Possíveis caminhos XRZ = 3.1 = 3 XRYZ = 3.3.2 = 18 XYZ = 1.2 = 2 XSYZ = 3.2.2 = 12 XSZ = 3.2 = 6 Total = 41 (Princípio da ADIÇÃO) O Princípio da Adição Suponha que queremos selecionar uma sobremesa entre três tortas e quatro bolos. De quantas maneiras isso pode ser feito? O número de escolhas possíveis é o número total de escolhas que temos, 3 + 4 = 7. Princípio da Adição Se A e B são eventos disjuntos com n1 e n2 resultados possíveis, respectivamente, então o número total de possibilidades para o evento “A e B” é n1 + n2. Exemplo: Um consumidor deseja comprar um veículo de uma concessionária. A concessionária tem 23 automóveis e 14 caminhões em estoque. Quantas escolhas possíveis o consumidor tem? Se fosse o mesmo número de veículos mais 17 veículos vermelhos, não seria 23 + 14 + 17. Conjuntos não disjuntos! 23 + 14 = 37 Usando os dois Princípios Juntos Exemplo: Uma criança pode escolher uma entre duas balas, uma rosa e uma preta, e um entre três chicletes, um amarelo, um verde e um branco. Suponha que, neste caso, queremos encontrar de quantas maneiras diferentes a criança pode escolher o doce, ao invés do número de conjuntos de doces que ela pode ter. 6 + 6 = 12 Exemplo: Quantos números de quatro dígitos começam com 4 ou 5? 1000 + 1000 = 2000 Exemplo: Considere novamente o problema do Exemplo anterior. Vamos evitar usar o princípio da adição. 2 . 10 . 10 . 10 = 2000 17. A quantidade de números de três algarismos, maiores que 500, que podem ser formados com os algarismos 3, 5, 6, 7 e 9, com repetição, é igual a: a) 10 b) 20 Resolução: c) 48 é um problema em que o português é d) 52 quem manda, a maioria das pessoas e) 100 cometeriam o erro de fazer o cálculo: 4 x 5 x 5 = 100 (errado!) Porém, quando o problema fala com repetição, os algarismos devem ser repetidos,assim: Nº com algarismos repetido mais nº com algarismos distintos é igual ao total de nº que podem ser formados Usando o P.F.C. teremos: Nº com algarismos repetidos = x Nº com algarismos distintos = 4.4.3 = 48 Total de nº formados = 4.5.5 = 100 Portanto, x + 48 = 100 Resposta : Letra D. x = 52 18. Duas das cinqüenta cadeiras de uma sala serão ocupadas por dois alunos. O número de maneiras distintas possíveis que esses alunos terão para escolher duas das cinqüenta cadeiras, para ocupálas, é: a) 1225 b) 2450 c) 250 Resolução: d) 49! 50 x 49 = 2450 19. Com relação a palavra BRASIL, quantos anagramas podemos formar: a) No total? Resolução: 6! = 720 b) Começados por BR? Resolução: 4! = 24 |BR| 4.3.2.1 c) Começando por vogal e terminando em consoante ? Resolução: 2.4.3.2.1.4 = 192 d) Com as letras BR juntas nesta ordem? Resolução: BR juntas significa que formarão uma única letra, logo o anagrama será composto de 5 letras, portanto a resposta é: 5! = 120 e) Com as letras BR juntas em qualquer ordem? Resolução: Em qualquer ordem, teremos: 5! . 2 = 240 f) Quantos anagramas podemos formar com a palavra ARARA? 5! 120 10 3!2! 6.2 g) E com a palavra ITATIAIA ? 8! 3!3!2! h) E com a palavra APROVADO ? 8! 2!2! 20. Uma urna contém 3 bolas vermelhas e 2 amarelas. Elas são extraídas uma a uma sem reposição. Quantas seqüências de cores podemos observar? Resolução: É como se fosse uma seqüência de bolas em fileira, do tipo: VVVAA, em qualquer ordem faremos como se fosse um anagrama com repetição, ou seja, 5! 10 3!.2! 21. Uma cidade é formada por 12 quarteirões segundo a figura abaixo. Uma pessoa sai do ponto P e dirigi-se para o ponto Q pelo caminho mais curto, isto é movendo–se da esquerda para direita, ou de baixo para cima. Nessas condições, quantos caminhos diferentes ele poderá fazer, se existem 2 ruas “horizontais” e 3 “verticais”? Resolução: P. Idem solução anterior, .Q é uma anagrama com repetição do tipo: DDDDCCC, ou seja: 7! 35 4!.3! 22.O número de anagramas que podem ser formados com as letras da palavra APOSTA e que não apresentam as letras A juntas é: Resolução: a) 120 TOTAL – A juntas = A separadas b) 240 c) 360 6! 5! d) 480 2! e) 600 720 120 2 360 120 240 23.O jogo da Sena consiste em acertar 6 dezenas sorteadas entre 60. O número de possíveis resultados está entre: a) 15.000.000 e 25.000.000 b) 25.000.000 e 35.000.000 c) 35.000.000 e 45.000.000 d) 45.000.000 e 55.000.000 Resolução: 60 59 58 57 56 55 50.063.860 6 5 4 3 2 1 24.Um indivíduo possui 5 discos dos Beatles, 8 discos dos Rolling Stones e 4 discos do U2. Ele foi convidado para ir a uma festa e, ao sair, levou 2 discos dos Beatles, 2 dos Rolling Stones e 3 do U2. O número de modos distintos de se escolherem os discos é: a) 12 Resolução: b) 42 c) 160 Beatles x Rol. Stones x U2 8 7 4 3 2 d) 1.120 5 4 x x e) 1.200 2 1 2 1 3 2 1 1120 25.Se existem 11 pessoas em uma sala e cada pessoa cumprimenta todas as outras uma única vez, o número de apertos de mão dados será igual a: a) 55 b) 65 Resolução: c) 110 11 10 d) 121 Precisamos de mãos : 55 2 1 26.Um fisioterapeuta recomendou a um paciente que fizesse, todos os dias, três tipos diferentes de exercícios e lhe forneceu uma lista contendo sete tipos diferentes de exercícios adequados a esse tratamento. Ao começar o tratamento, o paciente resolve que, a cada dia, sua escolha dos três exercícios será distinta das escolhas feitas anteriormente. O número máximo de dias que o paciente poderá manter esse procedimento é: a) 35 b) 38 Resolução: c) 40 d) 42 7 6 5 35 3 2 1 27. De quantas maneiras distintas podemos distribuir 10 alunos em 2 salas de aula, com 7 e 3 lugares, respectivamente? a) 120 Resolução: Basta escolhermos 3 e os b) 240 c) 14.400 outros irão para a outra sala; d) 86.400 e) 3.608.800 10 9 8 120 3 2 1 28.O número de múltiplos de 10, compreendidos entre 100 e 9999 e com todos os algarismos distintos é: a) 250 Resolução: b) 321 Para ser múltiplo de 10 o zero tem que c) 504 estar fixo na casa das unidades, portanto: d) 576 9 8 0 72 9 8 7 0 504 t ot al 576 29.Uma sala tem 6 lâmpadas com interruptores independentes. O número de modos de iluminar essa sala, acendendo pelo menos uma lâmpada é: a) 63 Resolução: b) 79 c) 127 Sabemos que a condição para iluminar a sala é que pelo menos uma lâmpada d) 182 esteja acesa.As opções de cada e) 201 lâmpada são: acesa e apagada, logo: 2 . 2 . 2 . 2 . 2 . 2 = 64 – 1 (todas apagadas) = 63 30. O código Morse usa “palavras” contendo de 1 a 4 “letras”. As “letras” são representadas pelo ponto (.) ou pelo traço (-). Deste modo, a quantidade de “palavras” possíveis através do código Morse é: a) 16 b) 64 Resolução: 2 (1 letra) c) 30 Pode-se formar d) 8 palavras de uma, duas 2.2 4 (2 letras) e) 36 , três ou quatro letras 2.2.2 8 (3 letras) e as opções por letra são duas (ponto ou traço), logo: 2.2.2.2 16 (4 letras) total 30 31. O número de maneiras de se distribuir 10 objetos diferentes em duas caixas diferentes, de modo que nenhuma caixa fique vazia, é: a) 45 b) 90 c) 1022 d) 101 Resolução: São 2.2.2.2.2.2.2.2.2.2 =1024 – 2 = 1022 (opções de apenas a caixa A ou apenas a caixa B) 32.(BB/2007) Considere que o BB tenha escolhido alguns nomes de pessoas para serem usados em uma propaganda na televisão, em expressões do tipo Banco do Bruno, Banco da Rosa etc. Suponha, também, que a quantidade total de nomes escolhidos para aparecer na propaganda seja 12 e que, em cada inserção da propaganda na TV, sempre apareçam somente dois nomes distintos. Nesse caso, a quantidade de inserções com pares diferentes de nomes distintos que pode ocorrer é inferior a 70. Resolução: É uma questão de análise combinatória onde usaremos o princípio fundamental de contagem: Devemos fazer duas escolhas dentre as 12 pessoas disponíveis, ou seja: 12 11 x 66 pares diferentes, 2 1 ou , C12, 2 12! 66 10!.2! portanto o item está correto. 33.(BB/2007)Considere que um decorador deva usar 7 faixas coloridas de dimensões iguais, pendurando-as verticalmente na vitrine de uma loja para produzir diversas formas. Nessa situação, se 3 faixas são verdes e indistinguíveis, 3 faixas são amarelas e indistinguíveis e 1 faixa é branca, esse decorador conseguirá produzir, no máximo, 140 formas diferentes com essas faixas Resolução: É um problema de permutação repetida onde as cores são como letras e o total de faixas(7) como uma palavra de 07 letras, ou seja: 7 3,3 P 7! 140 formas, 3!.3! portanto o item está correto. 34. Há exatamente 495 maneiras diferentes de se distribuírem 12 funcionários de um banco em 3 agências, de modo que cada agência receba 4 funcionários. Resolução: 1ª agência x 2ª agência x 3ª agência 12 11 10 9 8 7 6 5 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 495 701 34650 35. Se 6 candidatos são aprovados em um concurso público e há 4 setores distintos onde eles podem ser lotados, então há, no máximo, 24 maneiras de se realizarem tais lotações. Resolução: 4.4.4.4.4.4 = 46, maneiras, portanto o item está errado 36.(UFMG-2006) A partir de um grupo de oito pessoas, quer-se formar uma comissão constituída de quatro integrantes. Nesse grupo,incluem-se Gustavo e Danilo, que, sabe-se, não se relacionam um com o outro. Portanto, para evitar problemas, decidiu-se que esses dois,juntos, não deveriam participar da comissão a ser formada. Nessas condições, de quantas maneiras distintas se pode formar essa comissão? a) 70 b) 35 c) 45 d) 55 RESOLUÇÃO: Total de comissões – comissões (Gustavo e Danilo juntos) 8 7 6 5 6 5 . . . . 4 3 2 1 2 1 70 15 55 SOLUÇÕES INTEIRAS NÃO NEGATIVAS DE UMA EQUAÇÃO LINEAR Ex.: Considere a equação linear x + y = 5, quantas soluções inteiras não negativas podemos obter: (0,5);(1,4);(2,3);(3,2);(4,1);(5,0), portanto teremos 6 soluções inteiras não negativas. Considere agora a equação x+y+z=7 resolvendo por tentativa, o trabalho será muito grande , e corremos o risco de esquecer alguma solução. Temos que dividir 7 unidades em 3 partes ordenadas, de modo que fique em cada parte um número maior ou igual a zero. Indicaremos cada unidade por uma bolinha e usaremos a barra para fazer a separação, que corresponde aos sinais de adição: Logo teremos uma permutação com elementos repetidos (como em AARAARAAA), assim: P 7,2 9 9! 36 7!2! Portanto existem 36 soluções inteiras positivas para a equação.