Baixe o app para aproveitar ainda mais
Prévia do material em texto
Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital Autor: Guilherme Neves Aula 05 20 de Novembro de 2020 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 1 Sumário 1. Análise Combinatória .......................................................................................... 2 2. Fatorial de um Número Natural ........................................................................... 3 3. Princípio Fundamental da Contagem .................................................................. 6 4. Princípio Aditivo ................................................................................................. 11 5. Permutações Simples ......................................................................................... 13 6. Permutação com Elementos Repetidos ............................................................. 14 7. Permutação Circular ........................................................................................... 15 8. Combinação Simples ......................................................................................... 21 8.1. Propriedades e Casos Particulares ........................................................................ 25 9. Combinação Completa ...................................................................................... 27 10. Partições ............................................................................................................ 34 10.1. Partições ordenadas ........................................................................................... 35 10.2. Partições não-ordenadas .................................................................................... 39 11. Permutações Caóticas ....................................................................................... 43 12. Os Lemas de Kaplansky ..................................................................................... 49 12.1. Primeiro Lema de Kaplansky .............................................................................. 49 12.2. Segundo Lema de Kaplansky ............................................................................. 58 13. Permutações com Elementos Ordenados ......................................................... 64 14. Soluções Inteiras de Equações .......................................................................... 69 15. Lista de Questões de Concursos Anteriores ...................................................... 84 16. Gabaritos ......................................................................................................... 123 17. Lista de Questões de Concursos Anteriores com Comentários ...................... 127 18. Considerações Finais ....................................................................................... 225 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 2 Oi, pessoal. Aqui quem vos fala é o professor Guilherme Neves outra vez!! Vamos começar a nossa aula sobre Análise Combinatória? Não se esqueçam de me acompanhar também pelo instagram @profguilhermeneves. Estou postando dicas e questões resolvidas diariamente por lá. Coloquei alguns tópicos extras na teoria que são assuntos bem avançados. Sugiro que você os estude apenas depois de ter uma boa base de Análise Combinatória e depois de ter resolvido muitos problemas. Os tópicos avançados são os pontos 11 a 14 do índice (Permutações Caóticas, Lemas de Kaplansky, Permutações com elementos ordenados e Soluções Inteiras de Equações). 1. ANÁLISE COMBINATÓRIA Chamamos de Análise Combinatória ou simplesmente Combinatória a parte da Matemática que estuda as estruturas discretas. Falando na língua do “concursês”, a Análise Combinatória é a parte da Matemática que se preocupa em realizar contagens. Realizaremos contagens dos subconjuntos de um conjunto finito que satisfazem certas condições dadas. A grande maioria dos alunos pensa que a Análise Combinatória é apenas o estudo dos arranjos, combinações e permutações. Isto na verdade é apenas uma parte do assunto de Análise Combinatória, que, a bem da verdade, é 100% do necessário para uma prova. A Análise Combinatória trata de vários outros problemas que estão além dos nossos objetivos e não será visto neste curso. Não será visto porque nunca apareceu nem vai aparecer em prova alguma de concurso (assuntos como permutações caóticas, funções geradoras, etc.) Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 3 Diga-se de passagem, este é um dos assuntos mais importantes (se não for o mais importante) de toda a Matemática “concurseira”. É um assunto adorado por todas as bancas organizadoras. Vocês perceberão um aspecto um pouco diferente nesta aula: não apresentaremos a “fórmula” dos arranjos. Optamos em seguir esta linha, pois não achamos que seja didático utilizar fórmulas e casos particulares em demasia. Quem troca o princípio fundamental da contagem por fórmulas de arranjos terá dificuldades imensas em resolver inúmeros problemas de análise combinatória. Permitam-me copiar um trecho muito importante de um livro da Sociedade Brasileira de Matemática sobre o ensino de Análise Combinatória (A Matemática do Ensino Médio – Volume 2). “Você quer mostrar que é o bom ou quer que seus alunos aprendam? Se você prefere a segunda alternativa, resista à tentação de em cada problema buscar a solução mais elegante. O que deve ser procurado é um método que permita resolver muitos problemas e não um truque que resolva maravilhosamente um problema. A beleza de alguns truques só pode ser apreciada por quem tem domínio dos métodos. Combinatória não é difícil; impossível é aprender alguma coisa apenas com truques em vez de métodos.” Vamos aprender as ferramentas básicas de Análise Combinatória e, sem seguida, vamos aprimorar as técnicas com a resolução de questões. 2. FATORIAL DE UM NÚMERO NATURAL Com a finalidade de simplificar fórmulas e acelerar a resolução de questões, vamos definir o símbolo fatorial. Sendo 𝑛 um número natural, define-se fatorial de 𝑛 e indica-se 𝑛! à expressão: 𝑛! = 𝑛 ∙ (𝑛 − 1) ∙ (𝑛 − 2) ∙ ⋯ ∙ 2 ∙ 1, 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 1! = 1 0! = 1 Exemplos: 3! = 3 ∙ 2 ∙ 1 = 6 4! = 4 ∙ 3 ∙ 2 ∙ 1 = 24 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 4 5! = 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 120 Observação: a leitura correta da expressão 𝑛! é “fatorial de n”. Muitas pessoas, erradamente, falam “n fatorial”. Esta leitura incorreta pode gerar ambiguidades. Por exemplo, observe a maneira correta de leitura das seguintes expressões. 2 + 3! → 2 𝑚𝑎𝑖𝑠 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑑𝑒 3 (2 + 3)! → 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑑𝑒 2 𝑚𝑎𝑖𝑠 3 As pessoas que falam “n fatorial” vão falar assim (erradamente): 2 + 3! → 2 𝑚𝑎𝑖𝑠 3 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 (2 + 3)! → 2 𝑚𝑎𝑖𝑠 3 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 Exemplo: Calcular A! B! . Comentário Poderíamos simplesmente expandir os dois fatoriais e cortar os fatores comuns. 8! 6! = 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 8 ∙ 7 = 56 Entretanto, podemos simplificar os cálculos notando que: 8! = 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1EFFFFGFFFFH B! = 8 ∙ 7 ∙ 6! 8! 6! = 8 ∙ 7 ∙ 6! 6! = 8 ∙ 7 = 56 Em suma, podemos expandir o fatorial até o fator desejado e, em seguida, colocar o símbolo do fatorial no final. Vejamos mais um exemplo. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 5 Exemplo: Calcule o valor de A! I!J! . Comentário Aqui podemos expandir o fatorial de 8 e “travar” no número 5. Lembre-se de expandir o fatorial de 3. 8! 5! 3! = 8 ∙ 7 ∙6 ∙ 5! 5! ∙ 3 ∙ 2 ∙ 1 Neste ponto, podemos cancelar 5!. Observe ainda que 3 ∙ 2 ∙ 1 = 6. 8! 5! 3! = 8 ∙ 7 ∙ 6 ∙ 5! 5! ∙ 3 ∙ 2 ∙ 1 = 8 ∙ 7 ∙ 6 6 = 8 ∙ 7 = 56 Exemplo: Simplificar a expressão (KLJ)! (KLM)! . Comentário Vamos expandir o fatorial de n + 3 até n+1. (𝑛 + 3)! (𝑛 + 1)! = (𝑛 + 3)(𝑛 + 2)(𝑛 + 1)! (𝑛 + 1)! = (𝑛 + 3)(𝑛 + 2) = 𝑛N + 5𝑛 + 6 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 6 3. PRINCÍPIO FUNDAMENTAL DA CONTAGEM Vamos aprender o princípio fundamental da contagem, também chamado de princípio multiplicativo, através de exemplos. Exemplo 1: Quantos são os resultados possíveis que se obtém ao jogarmos uma moeda não viciada duas vezes consecutivas para cima? Como podemos ver no diagrama de árvore, são 4 possibilidades. No primeiro lançamento há duas possibilidades (cara ou coroa) e no segundo lançamento há duas possibilidades (cara ou coroa) gerando os seguintes resultados: (CARA,CARA), (CARA,COROA), (COROA,CARA), (COROA,COROA). Lançamento das moedas Cara Cara Cara,Cara Coroa Cara,Coroa Coroa Cara Coroa,Cara Coroa Coroa,Coroa Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 7 Exemplo 2: Em uma urna, há bolas vermelhas (V), pretas (P) e azuis (A). Uma bola é retirada, observada e é devolvida para a urna. Qual o número de resultados possíveis em 3 extrações sucessivas? ` Temos 3 possibilidades para a primeira extração (V, P ou A), 3 possibilidades para a segunda extração (V,P ou A) e 3 possibilidades para a terceira extração (V,P ou A). Há um total de 27 possibilidades. Extração das bolas V V V P A P V P A A V P A P V V P A P V P A A V P A A V V P A P V P A A V P A Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 8 Exemplo 3: Em uma sala há 3 homens e 2 mulheres. De quantos modos é possível selecionar um casal (homem-mulher)? Vamos chamar os homens de H1,H2,H3 e as mulheres de M1,M2. Para escolher o homem temos 3 possibilidades e para escolher a mulher temos 2 possibilidades. Existem 3 possibilidades para a primeira etapa (a primeira etapa é escolher o homem), 2 possibilidades para a segunda etapa (a segunda etapa é escolher a mulher). O número de diferentes casais que podem ser formados é igual a 3 ∙ 2 = 6. Com estes três exemplos, fica mais fácil compreender o Princípio Fundamental da Contagem, que pode assim ser enunciado: Se um experimento pode ocorrer em várias etapas sucessivas e independentes de tal modo que: - 𝑝M é o número de possibilidades da 1ª etapa. - 𝑝N é o número de possibilidades da 2ª etapa. . . . - 𝑝K é o número de possibilidades da n-ésima etapa. O número total de possibilidades de o acontecimento ocorrer é igual a 𝑝M ∙ 𝑝N ∙ ⋯ ∙ 𝑝K Casais H1 M1 H1-M1 M2 H1-M2 H2 M1 H2-M1 M2 H2-M2 H3 M1 H3-M1 M2 H3-M2 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 9 Vamos resolver novamente os exemplos introdutórios com o auxílio do princípio fundamental da contagem. Exemplo 1: Quantos são os resultados possíveis que se obtém ao jogarmos uma moeda não- viciada duas vezes consecutivas para cima? Comentário São duas etapas: lançar a moeda na primeira vez e lançar a moeda na segunda vez. Há 2 possibilidades no primeiro lançamento e 2 possibilidades no segundo lançamento. Portanto, são 2 ∙ 2 = 4 resultados possíveis. Exemplo 2: Em uma urna, há bolas vermelhas (V), pretas (P) e azuis (A). Uma bola é retirada, observada e é devolvida para a urna. Qual o número de resultados possíveis em 3 extrações sucessivas? Comentário São três etapas: observar a cor da primeira bola, observar a cor da segunda bola e observar a cor da terceira bola. Há 3 possibilidades para a primeira etapa, 3 possibilidades para a segunda etapa e 3 possibilidades para a terceira etapa. São, portanto, 3 ∙ 3 ∙ 3 = 27 resultados possíveis. Exemplo 3: Em uma sala há 3 homens e 2 mulheres. De quantos modos é possível selecionar um casal (homem-mulher)? Comentário São duas etapas: escolher o homem do casal e escolher a mulher do casal. Existem 3 possibilidades para a escolha do homem e 2 possibilidades para a escolha da mulher. Podemos selecionar o casal de 3 ∙ 2 = 6 modos diferentes. Os passos básicos para resolver os problemas com o Princípio Fundamental da Contagem são os seguintes: i) Identificar as etapas do problema. ii) Calcular a quantidade de possibilidades em cada etapa. iii) Multiplicar. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 10 Para fazer uma viagem Recife-Petrolina-Recife, posso escolher como transporte ônibus, carro, moto ou avião. De quantos modos posso escolher os transportes se não desejo usar na volta o mesmo meio de transporte usado na ida? Comentário Vejamos novamente os passos: i) Identificar as etapas do problema. Escolher o transporte da ida e escolher o transporte da volta. ii) Calcular a quantidade de possibilidades em cada etapa. Temos 4 possibilidades para a ida e 3 possibilidades para a volta (pois não desejo utilizar o mesmo meio de transporte). iii) Multiplicar. 𝟒 ∙ 𝟑 = 𝟏𝟐 modos. Quais seriam os 12 modos? (ônibus, carro);(ônibus, moto);(ônibus, avião); (carro, ônibus); (carro, moto); (carro, avião); (moto, ônibus); (moto, carro); (moto,avião); (avião, ônibus); (avião, carro); (avião, moto). Obviamente não precisamos descrever quais são os 12 modos, mas, para um exemplo inicial, fica interessante mostrá-los. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 11 Quantas palavras contendo 4 letras diferentes podem ser formadas com um alfabeto de 26 letras? Comentário Atente para o fato de que as letras devem ser diferentes! Há 26 possibilidades para a primeira letra, 25 possibilidades para a segunda letra, 24 possibilidades para a terceira letra e 23 possibilidades para a quarta letra. O número de palavras é igual a: 26 ∙ 25 ∙ 24 ∙ 23 = 358.800 Quantas palavras contendo 4 letras podem ser formadas com um alfabeto de 26 letras? Comentário Neste caso, podemos repetir as letras. Há 26 possibilidades para a primeira letra, 26 possibilidades para a segunda letra, 26 possibilidades para a terceira letra e 26 possibilidades para a quarta letra. O número de palavras é igual a: 26 ∙ 26 ∙ 26 ∙ 26 = 456.976 Observe que em todos os casos até agora foi utilizado o conectivo “e”. Isto indica que o processo pode ser dividido em etapas e, portanto, devemos utilizar o princípio multiplicativo. É muito comum, entretanto, o enunciado utilizar o conectivo “ou”. Isso nos motiva a estudar o princípio aditivo. 4. PRINCÍPIO ADITIVO O princípio fundamental da contagem (princípio multiplicativo) diz que se há m modos de tomar uma decisão 𝐷M e, depois de tomada a decisão 𝐷M, há n modos de tomar uma decisão 𝐷N, então o total de possibilidades para tomar sucessivamente as decisões 𝐷M e 𝐷N é igual a 𝑚 ∙ 𝑛. Imagine agora que um processo possa ser realizada de 𝑝 modos ou de 𝑞 modos. Desta maneira, o princípio aditivo, afirma que o total de modos para realizar esta processo é igual a 𝑝 + 𝑞. Desta forma, quando utilizado o conectivo “ou”, deveremos somar o total de possibilidades. Exemplo: Existem dois símbolos para representar letras no código Morse chamados de pontos e traços.Considere as palavras com no mínimo 1 e no máximo 5 letras. Quantas palavras podem ser formadas no código Morse com esta restrição? Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 12 Comentário Observe que as palavras podem ter 1 ou 2 ou 3 ou 4 ou 5 letras. Assim, vamos calcular: • a quantidade de palavras com 1 letra • a quantidade de palavras com 2 letras • a quantidade de palavras com 3 letras • a quantidade de palavras com 4 letras • a quantidade de palavras com 5 letras Em seguida, vamos somar todos os resultados. • quantidade de palavras com 1 letra Só temos uma etapa. Escolher uma letra. Há duas possibilidades, já que há apenas dois símbolos. Assim, existem 2 palavras com uma letra. • quantidade de palavras com 2 letras Temos aqui duas etapas, a saber: escolher a primeira letra e escolher a segunda letra. Há 2 possibilidades para a primeira etapa e 2 possibilidades para a segunda etapa. O total de possibilidades é igual a 2 x 2 = 4. Assim, existem 4 palavras com duas letras. • quantidade de palavras com 3 letras Temos aqui três etapas, a saber: escolher a primeira letra, escolher a segunda letra e escolher a terceira letra. Há 2 possibilidades para a primeira etapa, 2 possibilidades para a segunda etapa e 2 possibilidades para a terceira etapa. O total de possibilidades é igual a 2 x 2 x 2 = 8. Assim, existem 8 palavras com três letras. • quantidade de palavras com 4 letras Temos agora quatro etapas. Em cada etapa, há 2 possibilidades. Assim, o total de possibilidades é 2 x 2 x 2 x 2 = 16. Assim, existem 16 palavras com quatro letras. • quantidade de palavras com 5 letras Temos agora cinco etapas. Em cada etapa, há 2 possibilidades. Assim, o total de possibilidades é 2 x 2 x 2 x 2 x 2 = 32. Assim, existem 32 palavras com cinco letras. O total de palavras é 2 + 4 + 8 + 16 + 32 = 62. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 13 5. PERMUTAÇÕES SIMPLES Queremos responder perguntas do tipo “De quantas maneiras é possível ordenar 𝑛 objetos distintos?”. Imagine que temos 4 livros em uma prateleira. O problema pode ser separado em 4 etapas: escolher o primeiro objeto, escolher o segundo objeto, escolher o terceiro objeto e escolher o quarto objeto. Temos 4 objetos possíveis para o primeiro lugar, 3 objetos possíveis para o segundo lugar, 2 objetos possíveis para o terceiro lugar e 1 objeto possível para o último lugar. O total de maneiras é igual a 4 ∙ 3 ∙ 2 ∙ 1 = 4! = 24. No caso geral, temos 𝑛 modos de escolher o objeto que ocupará o primeiro lugar, 𝑛 − 1 modos de escolher o objeto que ocupará o segundo lugar,..., 1 modo de escolher o objeto que ocupará o último lugar. Portanto, o número de modos de ordenar 𝑛 objetos distintos é: 𝑛 ∙ (𝑛 − 1) ∙ ⋯ ∙ 1 = 𝑛! Cada uma destas ordenações é chamada permutação simples de 𝑛 objetos e o número de permutações simples de 𝑛 objetos distintos é representado por 𝑃K. Desta maneira, 𝑃K = 𝑛!. Exemplo: Quantos são os anagramas da palavra BOLA? Comentário Cada anagrama de BOLA é uma ordenação das letras B,O,L,A. Desta maneira, o número de anagramas de BOLA é 𝑃X = 4! = 4 ∙ 3 ∙ 2 ∙ 1 = 24. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 14 6. PERMUTAÇÃO COM ELEMENTOS REPETIDOS Quantos anagramas possui a palavra ARARAQUARA? O problema surge porque há letras repetidas na palavra ARARAQUARA. Nesta palavra a letra A aparece 5 vezes e a letra R aparece 3 vezes. Aparentemente a quantidade de anagramas seria 10! (pois há 10 letras na palavra). Devemos fazer uma “correção” por conta das letras repetidas. Devemos dividir o resultado por 5! e por 3! que são as quantidades de letras repetidas. Assim, o número de anagramas da palavra ARARAQUARA é igual a 𝑃MY I,J = 10! 5! ∙ 3! = 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6 ∙ 5! 5! ∙ 3 ∙ 2 ∙ 1 Observe que ao expandirmos o 10!, podemos “travá-lo” onde quisermos para efetuar os cancelamentos. Dessa forma, 𝑃MY I,J = 10! 5! ∙ 3! = 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6 3 ∙ 2 ∙ 1 = 5.040 𝑎𝑛𝑎𝑔𝑟𝑎𝑚𝑎𝑠 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 15 7. PERMUTAÇÃO CIRCULAR Imagine uma mesa com 4 lugares equiespaçados. De quantas maneiras 4 pessoas podem ser dispostas nesta mesa, se considerarmos equivalentes disposições que possam coincidir por rotação? A pergunta que propusemos considera as três disposições acima como equivalentes. Isso porque podemos obter a segunda e a terceira disposições por uma simples rotação da primeira disposição. Observe que o número 1 está sempre em frente ao número 3; o número 1 está sempre à direita do número 2; o número 1 está sempre à esquerda do número 4. A resposta desse problema é representada por (𝑃𝐶)K, o número de permutações circulares de 𝑛 objetos distintos. Repare que nas permutações simples importam os lugares que os objetos ocupam ao passo que nas permutações circulares o que importa é apenas a posição relativa dos objetos entre si. Por exemplo, são distintas as seguintes disposições. Tome o número 1 como referência posicional. Na primeira disposição, o número 4 está à direita do número 1 e, na segunda disposição, o número 4 está à esquerda do número 1. 1 2 3 4 3 4 1 2 2 3 4 1 1 2 3 4 1 4 3 2 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 16 Assim, para calcular o número de permutações dos 4 objetos nesta mesa circular, devemos fixar um de seus elementos e permutar todos os outros. Assim, fixando o número 1, por exemplo, podemos permutar os outros objetos de 3! = 3 × 2 × 1 = 6 maneiras diferentes. Vamos representar as 6 possibilidades para que fique mais claro. • Escolhendo o número 2 para ficar em frente ao número 1, há duas possibilidades. • Escolhendo o número 3 para ficar em frente ao número 1, há duas possibilidades. • Escolhendo o número 4 para ficar em frente ao número 1, há duas possibilidades. 1 4 2 3 1 3 2 4 1 4 3 2 1 2 3 4 1 3 4 2 1 2 4 3 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 17 São 6 possibilidades ao todo, portanto. Assim, para calcular o número de permutações circulares, devemos fixar um dos objetos e permutar os outros. Se são n objetos, devemos fixar 1 e permutar os (n – 1) restantes. Em geral, podemos afirmar que o número de permutações circulares de 𝑛 objetos distintos é dado por (𝑛 − 1)!. (𝑃𝐶)K = (𝑛 − 1)! (CS UFG 2016/Prefeitura de Goiânia-GO) Um restaurante tem em seu cardápio oito pratos de diferentes tipos de massas, e esses pratos são dispostos, para os clientes se servirem, em uma mesa circular, conforme a figura a seguir. De quantas maneiras diferentes podem ser colocados esses oito pratos na mesa, tendo como base a forma indicada na figura? a) 2520 b) 5040 c) 20160 d) 40320 Comentário Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 18 Queremos dispor 8 pratos em torno de uma mesa circular. Queremos calcular a quantidade de maneiras diferentes que podemos arrumar os pratos na mesa. Para tanto, basta calcular o total de permutações circulares de 8 objetos. 𝑃𝐶K = (𝑛 − 1)! 𝑃𝐶A = (8 − 1)! = 7! 𝑃𝐶A = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5.040Gabarito: B (IBFC 2015/SEE-MG) Um grupo de 5 pessoas do mesmo setor empresarial decidem almoçar fora do prédio comercial, ao chegar no restaurante sentam-se em volta de uma mesa circular. Assinale a alternativa que apresenta a quantidade de modos distintos que esse grupo pode se sentar à mesa. a) 15 modos b) 12 modos c) 24 modos d) 32 modos Comentário Vamos permutar 5 pessoas em torno de uma mesa circular 𝑃𝐶K = (𝑛 − 1)! 𝑃𝐶𝟓 = (𝟓 − 1)! = 𝟒! Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 19 𝑃𝐶𝟓 = 4 × 3 × 2 × 1 = 𝟐𝟒 Gabarito: C CM CURITIBA (PR) | CÂMARA MUNICIPAL DE CURITIBA (PR) | 2020 | BANCA NC-UFPR | ANALISTA LEGISLATIVO (CM CURITIBA/PR) Patrícia tem disponíveis 6 cores distintas, que pretende usar para pintar um cubo, de modo que cada face tenha uma cor diferente. Cada possibilidade de pintura deve resultar em um cubo pintado, distinto dos demais possíveis. Do mesmo modo, se ela tivesse disponíveis 7 cores para pintar o cubo, quantas possibilidades a mais ela teria? A) 180. B) 150. C) 75. D) 42. E) 30. Comentário Comecemos com o caso em que há 6 cores. Vamos numerar as cores: 1, 2, 3, 4, 5, 6. Vamos trabalhar com o cubo em cima de uma mesa. Vou pintar uma face do cubo com o número 1 e colocar essa face encostada na mesa. Vou agora separar em dois casos: i) O número 2 está oposto à face de número 1. Nesse caso, precisamos permutar as 4 cores restantes em um círculo. Logo, há um total de Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 20 𝑷𝑪𝟒 = (𝟒 − 𝟏) = 𝟑! = 𝟔 𝒄𝒂𝒔𝒐𝒔 ii) O número 2 não é oposto à face de número 1. Assim, giro o dado até que o número 2 esteja olhando para mim e deixo o dado fixo. Agora pinto as 4 faces restantes, o que pode ser feito de 4! = 24 maneiras. O total de possibilidades é 6 + 24 = 30. A dificuldade dessa questão é a mesma de quando vamos deduzir a fórmula da permutação circular: devemos escolher um elemento para servir de referência porque o que importa é a posição relativa entre os objetos. Assim, no caso da permutação circular, como estamos no plano, precisamos colocar apenas um elemento como referência. Daí permutamos os n – 1 elementos restantes e obtemos 𝑷𝑪𝒏 = (𝒏 − 𝟏)!. No caso dessa questão, estamos trabalhando com um objeto de 3 dimensões. Assim, precisamos de duas referências. Por isso coloquei a cor 1 como referência encostada na mesa e, depois, fixei a posição da cor 2. Vamos agora ao caso em que há 7 cores disponíveis. O primeiro passo é escolher 6 das 7 cores que serão usadas para pintar o cubo. Isso pode ser feito de 𝑪𝟕𝟔 = 𝟕 maneiras. Para cada escolha dessas 6 cores, há 30 maneiras de pintar o cubo. Logo, o total de possibilidades é 7 x 30 = 210. O problema pede a diferença entre essas quantidades: 210 – 30 = 180 maneiras. O gabarito é a letra A. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 21 Vamos resolver o caso de 6 cores com outro raciocínio parecido com o anterior. Coloco a face 1 encostada na mesa. Há 5 possibilidades para escolher a face oposta à face 1. Agora, dos 4 números restantes, pego um qualquer e pinto uma face lateral e coloco essa face fixa olhando para mim. Deixo fixa olhando para mim porque o que importa é a posição relativa entre as cores e não a posição absoluta. Agora, há 3! = 6 maneiras de pintar as faces restantes. Assim, o total de possibilidades é 5 x 6 = 30. Gabarito: A 8. COMBINAÇÃO SIMPLES Imagine que dispomos das seguintes frutas: maçãs, bananas, mamões e abacates. Desejamos fazer uma salada de fruta com 3 destas frutas. Picamos separadamente cada fruta e, em seguida misturamos tudo na seguinte ordem: maçã, banana, mamão no primeiro prato e banana, maçã e mamão no segundo prato. É óbvio que obteremos o mesmo resultado. Agrupamentos como este, que têm a característica de não mudar quando alteramos a ordem de seus elementos, são chamados de combinações. A pergunta aqui é a seguinte: Dispomos de um conjunto com 𝑛 elementos. Queremos formar um subconjunto deste conjunto com 𝑝 elementos. De quantos modos podemos escolher estes 𝑝 elementos? Estamos utilizando a linguagem dos conjuntos porque não existe ordem entre os elementos de um conjunto. Por exemplo, os conjuntos {𝑎, 𝑏} 𝑒 {𝑏, 𝑎} são iguais. Vamos ilustrar: temos o conjunto {1,2,3,4,5} e queremos formar um subconjunto com 2 elementos deste conjunto. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 22 Temos as seguintes possibilidades: {1,2},{1,3},{1,4},{1,5} → fixando o número 1 {2,3},{2,4},{2,5} → fixando o número 2 {3,4},{3,5} → fixando o número 3 {4,5} → fixando o número 4 Temos um total de 4+3+2+1=10 subconjuntos com 2 elementos. Repare que corremos o risco de esquecer algum subconjunto, sobretudo se houver um número grande de elementos. É para isto que serve a análise combinatória. Contar agrupamentos sem precisar descrevê-los. Pois bem, tendo um conjunto com 𝑛 elementos, o número de subconjuntos com 𝑝 elementos é igual ao número de combinações de 𝑛 elementos tomados 𝑝 a 𝑝 e é calculado da seguinte maneira: 𝑛! 𝑝! (𝑛 − 𝑝)! Existem várias notações para o número de combinações. As mais comuns são as seguintes. 𝐶K,j = 𝐶K j = k 𝑛 𝑝l = 𝑛! 𝑝! (𝑛 − 𝑝)! No nosso caso, temos 5 elementos no conjunto (𝑛 = 5) e queremos escolher 2 destes 5 elementos (𝑝 = 2). 𝐶IN = 5! 2! ∙ (5 − 2)! = 5! 2! 3! = 5 ∙ 4 ∙ 3! 2 ∙ 1 ∙ 3! = 5 ∙ 4 2 ∙ 1 = 10 Que é exatamente o número de subconjuntos que havíamos encontrado. A maneira mais fácil de utilizar esta fórmula é a seguinte: O número de combinações sempre será uma fração. 𝐶IN = Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 23 No denominador, devemos colocar o fatorial expandido do menor número. 𝐶IN = 2 ∙ 1 Quantos fatores há no denominador? Dois. Pois bem, devemos expandir o outro número, no caso o número 5, em dois fatores. 𝐶IN = 5 ∙ 4 2 ∙ 1 = 10 Exemplo: São marcados 8 pontos distintos sobre uma circunferência. Quantos triângulos são determinados por estes pontos? Comentário Vejamos o desenho acima. O triângulo ABC é congruente ao triângulo ACB, que é congruente ao triângulo BAC e assim por diante. Portanto, a ordem dos vértices não é relevante na definição do triângulo. Assim, não podemos aplicar o Princípio Fundamental da Contagem. Se assim o fizéssemos, estaríamos contando os triângulos ABC, ACB, BAC, BCA, CAB e CBA como triângulos diferentes, o que não é verdade. Como a ordem dos objetos não é relevante na formação do agrupamento, a resposta desse problema é o número de combinações de 8 objetos tomados 3 a 3, representado por 𝐶AJ. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 24 Esse cálculo é feito da seguinte maneira: teremos uma fração. Colocaremos o fatorial do menor dos números no denominador. No caso, o fatorial de 3 (no denominador. Ficamos assim por enquanto: 𝐶AJ = 3 ∙ 2 ∙ 1 E o numerador? Devemos expandir o número 8 na mesma quantidade de fatores do denominador (3 fatores). 𝐶AJ = 8 ∙ 7 ∙ 6 3 ∙ 2 ∙ 1 = 56 Assim, o total de triângulos determinados pelos 8 pontos é igual a 56. Exemplo: Um grupo é formado por 5 homens e 6 mulheres. De quantas maneiras podemos formar uma comissão formadapor: a) 2 homens e 3 mulheres. b) 2 homens ou 3 mulheres. c) 2 pessoas do mesmo sexo. Comentário a) Como estamos usando o conectivo “e”, vamos utilizar o princípio multiplicativo. Há 5 homens dos quais escolheremos 2 e há 6 mulheres das quais escolheremos 3. 𝐶IN ∙ 𝐶BJ = 5 ∙ 4 2 ∙ 1 ∙ 6 ∙ 5 ∙ 4 3 ∙ 2 ∙ 1 = 10 ∙ 20 = 200 b) Como estamos usando o conectivo “ou”, vamos utilizar o princípio aditivo. Há 5 homens dos quais escolheremos 2. Há 6 mulheres das quais escolheremos 3. 𝐶IN + 𝐶BN = 5 ∙ 4 2 ∙ 1 + 6 ∙ 5 ∙ 4 3 ∙ 2 ∙ 1 = 10 + 20 = 30 c) Escolher 2 pessoas do mesmo sexo é o mesmo que escolher 2 homens ou 2 mulheres. Assim, utilizaremos o princípio aditivo, pois estamos utilizando o conectivo “ou”. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 25 𝐶IN + 𝐶BN = 5 ∙ 4 2 ∙ 1 + 6 ∙ 5 2 ∙ 1 = 10 + 15 = 25 8.1. Propriedades e Casos Particulares i) 𝑪𝒎𝒎 = 𝟏 Isto é verdade porque 𝐶nn = 𝑚! 𝑚! 0! = 1 Assim, por exemplo, 𝐶oo = 1 ii) 𝑪𝒎𝟎 = 𝟏 Isto é verdade porque 𝐶nY = 𝑚! 0!𝑚! = 1 Assim, por exemplo, 𝐶IY = 1 iii) 𝑪𝒎𝟏 = 𝒎 Isto é verdade porque 𝐶nM = 𝑚! 1! (𝑚 − 1)! = 𝑚 ∙ (𝑚 − 1)! (𝑚 − 1)! = 𝑚 Assim, por exemplo, 𝐶BM = 6 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 26 iv) 𝑪𝒎𝒎q𝟏 = 𝒎 Isto é verdade porque 𝐶nnqM = 𝑚! (𝑚 − 1)! (𝑚 − (𝑚 − 1))! = 𝑚! (𝑚 − 1)! 1! = 𝑚 ∙ (𝑚 − 1)! (𝑚 − 1)! = 𝑚 Assim, por exemplo, 𝐶BI = 6 𝐶oB = 7 𝐶MIMX = 15 v) 𝑪𝒎 𝒑 = 𝑪𝒎 𝒎q𝒑 Esta propriedade é muito útil quando o valor de p é grande. Podemos substituí-lo por m – p. Esta propriedade é verdade porque 𝐶n j = 𝑚! 𝑝! (𝑚 − 𝑝)! 𝐶n nqj = 𝑚! (𝑚 − 𝑝)! s𝑚 − (𝑚 − 𝑝)t! = 𝑚! (𝑚 − 𝑝)! 𝑝! Portanto, 𝐶n j = 𝐶n nqj. Imagine, por exemplo, que você precisa calcular 𝐶MYA . Podemos substituir 8 por 10 – 8 = 2. 𝐶MYA = 𝐶MYN = 10 ∙ 9 2 ∙ 1 = 45 Entender esta propriedade também é muito fácil. Imagine que você tem 10 amigos e escolherá 8 para participar de um jantar. Ora, escolher os 8 que participarão do jantar é o mesmo que escolher os 2 que não participarão. Portanto, 𝐶MYA = 𝐶MYN Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 27 vi) 𝑪𝒏𝟎 + 𝑪𝒏𝟏 + 𝑪𝒏𝟐 + ⋯𝑪𝒏𝒏 = 𝟐𝒏 Exemplo: 𝐶XY + 𝐶XM + 𝐶XN + 𝐶XJ + 𝐶XX = 2X = 16 Há um raciocínio bem rápido para entender esta propriedade. Imagine um conjunto com n elementos. Assim, por exemplo, 𝐶KJ é a quantidade de subconjuntos deste conjunto com 3 elementos. Da mesma forma, 𝐶KI é a quantidade de subconjuntos com 5 elementos. Podemos então concluir que 𝐶KY + 𝐶KM + 𝐶KN + ⋯𝐶KK é o total de subconjuntos deste conjunto. Sabemos que o total de subconjuntos de um conjunto é 2K. Portanto, a propriedade acima é válida. A demonstração formal desta propriedade se dá com o desenvolvimento do binômio de Newton (1 + 1)K. 9. COMBINAÇÃO COMPLETA Para introduzir este assunto, vou resolver uma questão antiga, mas bem interessante. (Petrobras 2008-2/CESGRANRIO) Em um supermercado são vendidas 5 marcas diferentes de refrigerante. Uma pessoa que deseje comprar 3 latas de refrigerante, sem que haja preferência por uma determinada marca, pode escolhê-las de N formas. O valor de N é (A) 3 (B) 10 (C) 15 (D) 35 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 28 (E) 125 Comentário Esta é uma questão “clássica” que aparece nos livros de análise combinatória. Por outro lado, se a pessoa nunca viu uma questão parecida como esta, é muito difícil ter este raciocínio SOZINHO na hora da prova. Imagine que temos um armário para armazenar os refrigerantes. Temos 5 marcas diferentes de refrigerante. Para separar as 5 marcas diferentes de refrigerante neste armário, precisamos de 4 divisórias. O número de divisórias é sempre 1 a menos que o total de marcas. Vamos considerar algumas marcas conhecidas de refrigerante. Coca-Cola, Guaraná Antarctica, Fanta, Tuchaua, Sprite. Temos agora 3 latinhas de refrigerante para distribuir nestas divisórias. Há várias disposições possíveis. Vejamos algumas: Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 29 Nesta disposição acima, o cliente está levando uma Coca-Cola e 2 Tuchauas. Na disposição acima, o cliente está levando um Guaraná Antarctica, 1 Fanta e 1 Sprite. Na disposição acima, o cliente está levando 3 Tuchauas. Resumindo: estamos permutando 7 objetos, a saber: as 4 divisórias e as 3 latinhas. Vamos apagar agora os nomes das marcas. O número total de possibilidades que há para o cliente comprar 3 refrigerantes dentre 5 marcas disponíveis sem preferência em relação a alguma marca é igual ao número permutações de 7 objetos dos quais 4 são iguais (as divisórias) e 3 são iguais (as bolinhas). 𝑃o X,J = 7! 4! ∙ 3! 𝑃o X,J = 7 ∙ 6 ∙ 5 ∙ 4! 4! ∙ 3 ∙ 2 ∙ 1 = 7 ∙ 6 ∙ 5 3 ∙ 2 ∙ 1 = 35 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 30 Gabarito: D O problema acima é normalmente classificado como um problema de combinação completa. Os problemas de combinação completa no fundo podem ser resolvidos por permutação com repetição. Basta utilizar o raciocínio descrito acima. Observe que temos 5 qualidades para os objetos (5 marcas de refrigerante) e queremos escolher 3 objetos (3 latas). Observe ainda que o total de divisórias é igual a 5 – 1 = 4 (com 4 divisórias temos 5 lugares no armário). De uma maneira geral, digamos que há n qualidades de objetos e queremos selecionar p objetos. Adotando o raciocínio acima, teremos (n – 1) prateleiras e p objetos. Assim, permutaremos (𝑝 + 𝑛 − 1) entes dos quais há repetição de (n – 1) prateleiras e p objetos. 𝑃jLKqM KqM ,j = (𝑛 + 𝑝 − 1)! 𝑝! (𝑛 − 1)! A notação (símbolo) para a combinação completa é a que segue: 𝐶𝑅K j = (𝑛 + 𝑝 − 1)! 𝑝! (𝑛 − 1)! Para não precisar memorizar a fórmula acima, existe uma relação entre a combinação completa e a combinação simples. 𝐶𝑅K j = 𝐶KLjqM j Em outras palavras, você pode trocar a fórmula de uma combinação completa por uma combinação simples. Para tanto, basta substituir 𝑛 por 𝑛 + 𝑝 − 1. No nosso problema anterior, há 5 marcas de refrigerante. É o que temos disponível. Portanto, n = 5. Queremos escolher 3 latas de refrigerante. Portanto, p = 3. 𝐶𝑅IJ Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 31 Vamos trocar a combinação completa por uma combinação simples. Para tanto, vamos substituir 𝑛 = 5 por 5 + 3 − 1 = 7. 𝐶𝑅IJ = 𝐶oJ Agora é só calcular a combinação simples. Esse cálculo é feito da seguinte maneira: teremos uma fração. Colocaremos o fatorial do menor dos números no denominador. No caso, o fatorial de 3 (no denominador. Ficamos assim por enquanto: 𝐶𝑅IJ = 𝐶oJ = 3 ∙ 2 ∙ 1 E o numerador? Devemos expandir o número 7 na mesma quantidade de fatores do denominador (3 fatores). 𝐶𝑅IJ = 𝐶oJ = 7 ∙ 6 ∙ 5 3 ∙ 2 ∙ 1 = 35 Se você não quiser transformar em uma combinação simples, há um modo prático de calcular 𝐶𝑅 rapidamente. Comecemos novamente com uma fração. 𝐶𝑅IJ = No denominador, sempre colocaremos o fatorial de p, ou seja, o fatorial do número que está em cima. 𝐶𝑅IJ = 3 ∙ 2 ∙ 1 Na combinação simples, nós expandiríamoso número 5 em 3 fatores: 5 x 4 x 3. Aqui faremos o mesmo, só que vamos expandir “para cima”: 5 x 6 x 7. 𝐶𝑅IJ = 5 ∙ 6 ∙ 7 3 ∙ 2 ∙ 1 = 35 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 32 Exemplo: De quantos modos podemos comprar 5 refrigerantes em uma loja onde há 3 tipos de refrigerante? Comentário Este exemplo é muito parecido com o anterior. Entretanto, no problema anterior, havia 5 tipos de refrigerante e queríamos comprar 3 latas. Agora são 3 tipos de refrigerante e queremos comprar 5. Como são 3 tipos de refrigerante, precisamos de 2 divisórias para separar as marcas. Assim, iremos permutar ao todo 5 + 2 = 7 objetos com repetição de 5 e de 2. 𝑃o I,N = 7! 5! ∙ 2! = 7 ∙ 6 ∙ 5! 5! 2 ∙ 1 = 7 ∙ 6 2 ∙ 1 = 21 Vamos resolver o mesmo problema com a dica da combinação completa. São 3 tipos de refrigerante. Portanto, n = 3. Queremos selecionar 5 objetos. Portanto, p = 5. 𝐶𝑅JI A combinação completa pode ser trocada por uma combinação simples. 𝐶𝑅JI = 𝐶JLIqMI = 𝐶oI = 𝐶oN = 7 ∙ 6 2 ∙ 1 = 21 Resposta: 21 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 33 (IBADE 2019/IF-RO) Um restaurante oferece cinco pratos típicos da culinária regional. Paulo comprará almoço para três amigos nesse restaurante. De quantas maneiras ele pode realizar essa compra? a) 55 b) 50 c) 45 d) 40 e) 35 Comentário Há 5 pratos disponíveis e Paulo comprará 3 pratos. A ordem dos pratos não é relevante. Logo, utilizaremos combinações. Além disso, pode haver pratos repetidos. Portanto, usaremos combinação com repetição (combinação completa). O total de maneiras é 𝐶𝑅IJ Lembre-se que, no símbolo 𝐶𝑅K j, 𝑛 é a quantidade de classes de objetos que você tem à sua disposição e 𝑝 é a quantidade de objetos que serão selecionados. No exemplo acima, há 5 tipos de pratos disponíveis (𝑛 = 5) e queremos escolher 3 pratos (𝑝 = 3). Vamos agora utilizar a relação 𝐶𝑅K j = 𝐶KLjqM j para calcular a quantidade pedida. 𝐶𝑅IJ = 𝐶ILJqMJ = 𝐶oJ = 7 ∙ 6 ∙ 5 3 ∙ 2 ∙ 1 = 35 Gabarito: E Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 34 10. PARTIÇÕES Muita atenção neste tópico, pois é uma excelente ferramenta em Análise Combinatória que te ajudará ganhar tempo em muitas questões. Vamos trabalhar as partições ordenadas e não- ordenadas. Vamos primeiro entender o que é uma partição de um conjunto. Normalmente, nos problemas de Análise Combinatória, teremos conjuntos de pessoas. Vou explicar então com um conjunto de pessoas para ficar mais fácil. Imagine que temos um conjunto formado por 7 pessoas. Se queremos dividir esse conjunto de 7 pessoas em subconjuntos disjuntos (que não possuem elemento em comum), obteremos uma partição. Por exemplo, imagine que queremos dividir esse conjunto de 7 pessoas em 3 subconjuntos: um com 3 pessoas, outro com 2 pessoas e outro com 2 pessoas. Pronto, acabamos de obter uma partição. 𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜 = {𝐴𝑛𝑎, 𝐵𝑖𝑎, 𝐶𝑎𝑟𝑙𝑎, 𝐷𝑒𝑛𝑖𝑠𝑒, 𝐸𝑑𝑢𝑎𝑟𝑑𝑎, 𝐹𝑙á𝑣𝑖𝑎, 𝐺𝑎𝑏𝑟𝑖𝑒𝑙𝑎} Exemplo de partição: {𝐵𝑖𝑎, 𝐶𝑎𝑟𝑙𝑎, 𝐸𝑑𝑢𝑎𝑟𝑑𝑎}; {𝐴𝑛𝑎, 𝐷𝑒𝑛𝑖𝑠𝑒}; {𝐹𝑙á𝑣𝑖𝑎, 𝐺𝑎𝑏𝑟𝑖𝑒𝑙𝑎} Se a ordem entre esses conjuntos é relevante, a partição é chamada de partição ordenada. Se a ordem não é relevante, a partição é denominada partição não-ordenada. As partições ordenadas são as mais importantes em questões de concursos. Por quê? Porque normalmente as pessoas de cada subconjunto terão funções específicas na situação- problema de tal forma que a ordem dos conjuntos será relevante. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 35 Exemplo: Há 7 engenheiros envolvidos em um projeto. Queremos dividir os 7 engenheiros em 2 subconjuntos: 4 deles serão os responsáveis pelo planejamento do projeto e 3 serão responsáveis pela execução do projeto. Temos aqui uma partição ordenada, porque cada subconjunto tem um papel diferente na situação-problema. Por outro lado, há situações em que a ordem dos conjuntos não é relevante (partições não- ordenadas). Nunca vi essa situação em prova de concurso. Exemplo: Há 10 crianças que vão jogar futebol. Dividir as crianças em dois times de 5. Aqui temos uma partição não-ordenada, porque a ordem dos times não é relevante. 10.1. Partições ordenadas Observe a seguinte questão: (CESPE 2019/COGE-CE) Em determinado órgão, sete servidores foram designados para implantar novo programa de atendimento ao público. Um desses servidores será o coordenador do programa, outro será o subcoordenador, e os demais serão agentes operacionais. Nessa situação, a quantidade de maneiras distintas de distribuir esses sete servidores nessas funções é igual a a) 21. b) 42. c) 256. d) 862. e) 5.040. Comentário O problema acima ilustra perfeitamente a situação de uma partição ordenada. Há 7 pessoas e queremos dividi-las em 3 subconjuntos: um deles com 1 pessoa (o coordenador), outro com 1 pessoa (o subcoordenador) e outro com 5 pessoas (os agentes operacionais). Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 36 Normalmente, os livros resolvem esse tipo de problema assim: Há 7 pessoas disponíveis e precisamos escolher 1 coordenador. Podemos escolher de 𝐶oM = 7 𝑚𝑎𝑛𝑒𝑖𝑟𝑎𝑠. Sobraram 6 pessoas disponíveis. Devemos agora escolher 1 subcoordenador. Podemos escolher de 𝐶BM = 6 𝑚𝑎𝑛𝑒𝑖𝑟𝑎𝑠. Sobraram 5 pessoas. Devemos escolher 5 agentes operacionais. Podemos escolher de 𝐶II = 1 maneira. Como há ordem entre os subconjuntos (1 deles é o coordenador, o outro é o subcoordenador, e os restantes são agentes operacionais), a partição é ordenada. Não estou dizendo que existe ordem entre os elementos dos subconjuntos. Existe ordem entre os subconjuntos! Pelo princípio fundamental da contagem, o total de possibilidades é 7 × 6 × 1 = 42. Poderíamos também ter começado escolhendo os agentes operacionais. Há 7 pessoas disponíveis e precisamos escolher 5 agentes operacionais. Podemos escolher de 𝐶oI = 21 maneiras. Sobraram 2 pessoas. Dessas duas pessoas, precisamos escolher 1 coordenador. Podemos escolher de 𝐶NM = 2 maneiras. Sobrou 1 pessoa. Precisamos escolher o subcoordenador. Podemos escolher de 𝐶MM = 1 maneira. Pelo princípio fundamental da contagem, podemos distribuir os servidores nas funções de 21 × 2 × 1 = 42 maneiras. Vamos agora aprender o pulo do gato: a grande dica que te fará ganhar muito tempo nessas questões. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 37 Há 7 pessoas e queremos dividi-las em 3 subconjuntos com 1 pessoa (o coordenador), 1 pessoa (o subcoordenador) e 5 pessoas (os agentes operacionais). Vamos simbolizar essa quantidade de partições da seguinte forma: k 71, 1, 5l A expressão acima é conhecida como “coeficiente multinomial”. Pois bem, como calculamos? É muito fácil. A resposta será uma fração. No numerador, colocamos o fatorial de 7, que é o fatorial do conjunto original de pessoas. No denominador, colocamos os fatoriais das quantidades de elementos dos subconjuntos (fatoriais de 1, 1, e 5). k 71, 1, 5l = 7! 1! 1! 5! = 7 ∙ 6 ∙ 5! 5! = 7 ∙ 6 = 42 Muito fácil, não? O número de partições ordenadas de 𝑛 objetos em 𝑘 subconjuntos com 𝑛M, 𝑛N, … , 𝑛� elementos, respectivamente, é k 𝑛 𝑛M, 𝑛N, … , 𝑛�l= 𝑛! 𝑛M! 𝑛N!…𝑛�! Vamos resolver outros exemplos para por em prática e para que você perceba o poder desse método. (CESPE 2014/PMCE) Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 38 Considerando que um grupamento de 60 policiais militares em que haja 15 mulheres e 45 homens seja dividido em 10 equipes de 6 militares para monitorar determinada área, julgue o item subsequente. Se as 2 primeiras equipes formadas forem constituídas apenas por mulheres, então o número de maneiras distintas de escolher os membros dessas equipes será igual a MI! B!∙B!∙J! . Comentário Vamos primeiro resolver da forma “tradicional” utilizando combinações. Há 15 mulheres e devemos escolher 6 para a primeira equipe. Em seguida, sobram 9 mulheres das quais devemos escolher 6 para a segunda equipe. Observe que queremos colocar 6 mulheres na primeira equipe e 6 mulheres na segunda equipe. Como o conectivo usado é “e”, devemos multiplicar as quantidades. O total de maneiras para escolher os membros dessa equipe é 𝐶MIB ∙ 𝐶�B = 15! 6! 9! ∙ 9! 6! 3! = 15! 6! 6! 3! Vamos agora utilizar partições. Há 15 mulheres e vamos dividir em dois grupos de 6 mulheres. Observe que sobraram 3 mulheres. Essas 3 mulheres formam um terceiro subconjunto. Assim, na verdade, estamos dividindo as 15 mulheres em 3 subconjuntos: dois subconjuntos com 6 mulheres e um terceiro com 3 mulheres. Sempre que sobrarem pessoas, você deve juntar a “sobra” em um último subconjunto. k 156, 6, 3l = 15! 6! 6! 3! Gabarito: Certo. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 39 (CESPE 2013/STF) O colegiado do Supremo Tribunal Federal (STF) é composto por 11 ministros, responsáveis por decisões que repercutem em toda a sociedade brasileira. No julgamento de determinados processos, os ministros votam pela absolvição ou pela condenação dos réus de forma independente uns dos outros. A partir dessas informações e considerando que, em determinado julgamento, a probabilidade de qualquer um dos ministros decidir pela condenação ou pela absolvição do réu seja a mesma, julgue o item seguinte. Se, no julgamento de determinado réu, 8 ministros votarem pela absolvição e 3 ministros votarem pela condenação, a quantidade de maneiras distintas de se atribuir os votos aos diferentes ministros será inferior a 170. Comentário Vamos primeiro resolver sem a técnica das partições. Temos 8 absolvições (A) e 3 condenações (C): AAAAAAAACCC. A quantidade de maneiras de se atribuir os votos aos diferentes ministros é igual ao total de maneiras que podemos trocar (permutar) a ordem dessas letras. 𝑃MM A,J = 11! 8! 3! = 11 ∙ 10 ∙ 9 ∙ 8! 8! ∙ 3 ∙ 2 ∙ 1 = 11 ∙ 10 ∙ 9 3 ∙ 2 ∙ 1 = 165 Agora vamos resolver usando as partições. Há 11 pessoas e vamos dividi-las em dois subconjuntos: um com 8 pessoas (as que vão absolver) e outro com 3 pessoas (as que vão condenar). O total de maneiras de dividir essas pessoas é: k 118, 3l = 11! 8! 3! = 165 Gabarito: Certo 10.2. Partições não-ordenadas Vamos agora aprender a calcular a quantidade de partições quando a ordem entre os subconjuntos não é relevante. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 40 Exemplo: Vinte crianças estão reunidas para jogar futebol. De quantos modos podemos dividi-las em quatro times de 5 crianças cada? Nesse caso, não há ordem entre os times. Todos os subconjuntos têm o mesmo papel no problema (diferentemente dos problemas das partições ordenadas em que cada subconjunto desempenhava um papel distinto). Se as partições fossem ordenadas, a resposta seria: k 205, 5, 5, 5l = 20! 5! 5! 5! 5! = 20! (5!)X Entretanto, não há ordem entre os 4 times. Assim, precisamos desconsiderar a ordem no cálculo acima. Essa correção é feita dividindo a resposta pelo fatorial da quantidade de subconjuntos com mesma quantidade de elementos. Temos 4 subconjuntos com mesma quantidade de elementos. Logo, a resposta é 20! (5!)X ∙ 𝟒! Só para você ter ideia: o número acima é igual a 488.864.376. Vamos praticar um pouco mais. De quantos modos é possível dividir 15 pessoas: a) em dois grupos de 4 e um grupo de 7? b) em um grupo de 10 e um grupo de 5? c) em dois grupos de 2, dois grupos de 3 e um grupo de 5? Comentário Em cada caso, começamos calculando as partições ordenadas. Depois, devemos dividir a resposta pelos fatoriais das quantidades de subconjuntos que possuem a mesma quantidade de elementos. a) em dois grupos de 4 e um grupo de 7? As partições ordenadas são: Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 41 k 154, 4, 7l = 15! 4! 4! 7! Há dois conjuntos com a mesma quantidade de elementos. Logo, devemos dividir o número acima por 2!. A resposta é 15! 4! 4! 7! 𝟐! = 15! (4!)N7! 2! b) em um grupo de 10 e um grupo de 5? As partições ordenadas são: k 1510, 5l = 15! 10! 5! Como os dois subconjuntos possuem quantidades diferentes de elementos, não precisamos dividir por fatorial algum. Assim, a quantidade de partições ordenadas é igual à quantidade de partições não-ordenadas. c) em dois grupos de 2, dois grupos de 3 e um grupo de 5? As partições ordenadas são: k 152, 2, 3, 3, 5l = 15! 2! 2! 3! 3! 5! Observe que há dois grupos de 2 e dois grupos de 3. Logo, devemos dividir a resposta acima por 2! 2!. A resposta é: 15! 2! 2! 3! 3! 5! 𝟐! 𝟐! = 15! (2!)X(3!)N5! (NC-UFPR 2006/TCE-PR) De quantas maneiras diferentes 12 estudantes podem ser divididos em 3 equipes, sendo que cada uma das equipes deve ser composta de quatro estudantes? a) 8425 b) 3260 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 42 c) 12640 d) 5775 e) 34650 Comentário Vamos começar com as partições ordenadas. Há 12 pessoas e vamos dividir em 3 equipes com 4 pessoas cada. O número de partições ordenadas é: k 124, 4, 4l = 12! 4! 4! 4! Entretanto, não há ordem entre as equipes. Haveria ordem se, por exemplo, o problema designasse funções diferentes para cada equipe. Assim, devemos calcular o número de partições não-ordenadas. Para tanto, basta dividir o cálculo anterior por 3!, que é o número de equipes com mesma quantidade de elementos. 12! 4! 4! 4! 𝟑! = 12 ∙ 11 ∙ 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4! 4! ∙ 4! ∙ 4! ∙ 3! Vamos fazer algumas simplificações. Observe que 4! = 24 e 3! = 6. Podemos cortar 6 com 3!, 4! com 4!. Podemos simplificar ainda 12 com 4! e 8 com 4!. = 11 ∙ 10 ∙ 9 ∙ 7 ∙ 5 2 ∙ 3 = 5.775 Gabarito: D Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 43 11. PERMUTAÇÕES CAÓTICAS Esse assunto é um tópico avançado de Análise Combinatória e só vi duas questões de concursos que exigiam a sua cobrança. (FCC 2019/Prefeitura do Recife – Assistente de Gestão Pública) Os quatro funcionários de uma repartição trabalham cada um em uma mesa, todos na mesma sala. O chefe da repartição determinou que os funcionários trocassem de mesa entre si. Os funcionários podem ser realocados na sala de modo que nenhum funcionário passe a ocupar a mesa que ocupava antes da realocação a) de 4 maneiras diferentes. b) de 24 maneiras diferentes. c) de 9 maneiras diferentes. d) de 6 maneiras diferentes. e) de 12 maneiras diferentes. Comentário Aparentemente é uma questão bem tranquila. Puro engano! O assunto envolvido nessa questão não é tratadona esmagadora maioria de livros do Ensino Médio. A questão só é factível sem o estudo teórico deste tópico porque o número de funcionários é bem pequeno, ou seja, o candidato poderia descrever todas as possibilidades e marcar a resposta. Sejam (a, b, c, d) os funcionários em suas posições originais. Queremos realocar os funcionários de modo que nenhum ocupe a sua posição original. Dizemos que essa é uma permutação caótica (ou desarranjo). Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 44 As permutações caóticas são: (b, a, d, c); (c, a, d, b); (d, a, b, c); (c, d, a, b); (d, c, a, b); (b, d, a, c); (b, c, d, a); (c, d, b, a) e (d, c, b, a). Logo, há 9 maneiras diferentes. Veja que com 4 pessoas já é bastante complicado descrever todas as permutações caóticas. E se fossem 5 pessoas ou 8 pessoas? Apresento-lhes agora a fórmula para calcular o número de permutações caóticas (desarranjos) de n objetos: 𝐷K = 𝑛! ∙ � 1 0! − 1 1! + 1 2! − 1 3! + ⋯+ (−1)K 𝑛! � O termo (−1)K simplesmente indica que os sinais das frações vão sendo alternados. Por exemplo, para n = 4, temos: 𝐷X = 4! ∙ � 1 0! − 1 1! + 1 2! − 1 3! + 1 4!� Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 45 𝐷X = 24 ∙ �1 − 1 + 1 2 − 1 6 + 1 24� 𝐷X = 24 ∙ � 1 2 − 1 6 + 1 24� 𝐷X = 24 ∙ 1 2 − 24 ∙ 1 6 + 24 ∙ 1 24 𝐷X = 12 − 4 + 1 𝐷X = 9 Veja o resultado para n = 6. 𝐷B = 6! ∙ � 1 0! − 1 1! + 1 2! − 1 3! + 1 4! − 1 5! + 1 6!� 𝐷B = 6! ∙ �1 − 1 + 1 2 − 1 6 + 1 24 − 1 120 + 1 720� 𝐷B = 720 ∙ � 1 2 − 1 6 + 1 24 − 1 120 + 1 720� 𝐷B = 360 − 120 + 30 − 6 + 1 𝐷B = 265 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 46 É claro que seria impossível você escrever todas as possibilidades à mão. Mas, Guilherme, essa fórmula é muito complicada. Corro o risco de ficar nervoso e esquecê-la! Calma, amigo. Agora vem a salvação. Existe uma maneira bem mais fácil e rápida de calcular o número de permutações caóticas. É possível demonstrar que o número de permutações caóticas é o inteiro mais próximo de 𝑛! 𝑒 Na expressão acima, e é a constante de Euler: e = 2,718... Observe para o caso n = 6. 6! 𝑒 ≅ 720 2,718 ≅ 264,9 → 𝑜 𝑖𝑛𝑡𝑒𝑖𝑟𝑜 𝑚𝑎𝑖𝑠 𝑝𝑟ó𝑥𝑖𝑚𝑜 é 265 De fato, para n = 6, o número de permutações caóticas é 265. Vamos voltar à questão da FCC. (FCC 2019/Prefeitura do Recife – Assistente de Gestão Pública) Os quatro funcionários de uma repartição trabalham cada um em uma mesa, todos na mesma sala. O chefe da repartição determinou que os funcionários trocassem de mesa entre si. Os funcionários podem ser realocados na sala de modo que nenhum funcionário passe a ocupar a mesa que ocupava antes da realocação a) de 4 maneiras diferentes. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 47 b) de 24 maneiras diferentes. c) de 9 maneiras diferentes. d) de 6 maneiras diferentes. e) de 12 maneiras diferentes. Comentário A questão pede o número de permutações caóticas de 4 elementos. O número de permutações caóticas é o inteiro mais próximo de 4! 𝑒 ≅ 24 2,718 ≅ 8,8 O inteiro mais próximo é 9. Logo, há 9 maneiras para realocar os funcionários de modo que nenhum ocupe a sua posição original. Gabarito: C (FGV 2018/COMPESA) Há quatro urnas numeradas de 1 a 4 e quatro bolas, também numeradas de 1 a 4. O número de maneiras de se colocar uma bola em cada urna, de modo que nenhuma urna fique com a bola de mesmo número, é a) 12. b) 11. c) 10. d) 9. e) 8. Comentário Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 48 Questão idêntica à anterior, que também poderia ser resolvida com a força bruta, já que são poucas bolas. A questão pede o número de permutações caóticas de 4 elementos. O número de permutações caóticas é o inteiro mais próximo de 4! 𝑒 ≅ 24 2,718 ≅ 8,8 O inteiro mais próximo é 9. A resposta da questão é a alternativa D, mas a questão foi anulada (não sei o motivo). Gabarito: D Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 49 12. OS LEMAS DE KAPLANSKY 12.1. Primeiro Lema de Kaplansky Vamos aprender através de um exemplo. (FGV 2015/SSP-AM – Assistente Operacional) Sete pessoas formam uma fila e duas delas serão escolhidas para receber um brinde. O número de maneiras diferentes de escolher duas pessoas da fila que não sejam vizinhas é: a) 15; b) 18; c) 20; d) 24; e) 30. Comentário Vamos numerar as pessoas e formar um conjunto: {1, 2, 3, 4, 5, 6, 7}. Para esse exemplo com poucas pessoas escolhidas (apenas duas), podemos resolver de uma maneira bem simples. Há 7 pessoas e queremos escolher duas. Sem restrições, podemos fazer isso de: 𝐶oN = 7 ∙ 6 2 ∙ 1 = 21 𝑚𝑎𝑛𝑒𝑖𝑟𝑎𝑠 Entretanto, não queremos duplas formadas por números consecutivos, ou seja, devemos excluir os seguintes subconjuntos: {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}. Assim, o total de subconjuntos que satisfazem a condição é: Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 50 21 − 6 = 15 Mas essa solução só serve para casos “pequenos”. Vamos pensar em uma solução geral. Queremos formar um subconjunto de dois elementos no qual não há elementos consecutivos. Essa é exatamente a situação-problema resolvida pelos lemas de Kaplansky. Falo no plural “lemas” porque o segundo lema de Kaplansky considera 1 e 7 como sendo consecutivos (basta pensar, por exemplo, que sábado e domingo são consecutivos). Na nossa questão da FGV, 1 e 7 não são consecutivos e, portanto, será a situação-problema do Primeiro Lema de Kaplansky. O raciocínio desenvolvido em 1943 por Kaplansky (Irving Kaplanky, matemático canadense) é o seguinte: marcaremos com uma letra S (sim) os elementos do conjunto que farão parte do subconjunto e marcaremos com a letra N (não) os elementos que não farão parte do subconjunto. Por exemplo, o subconjunto {1, 3} seria representado por SNSNNNN. O subconjunto {4, 5}, que não é um subconjunto válido para o nosso problema, seria representado por NNNSSNN. Para formar um subconjunto de 2 elementos não-consecutivos, devemos colocar 2 letras S e 5 letras N em fila, sem que haja duas letras S juntas. Para tanto, vamos começar dispondo as cinco letras N com espaços vazios entre elas (os espaços vazios serão representados por chaves. � 𝑁 � 𝑁 � 𝑁 � 𝑁 � 𝑁 � Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 51 Observe que há 5 letras N e 6 espaços vazios onde podemos colocar as 2 letras S. Ora, há 6 espaços vazios e devemos escolher 2 para colocar as letras S. Como a ordem dos espaços vazios não importa, então isso pode ser feito de: 𝐶BN = 6 ∙ 5 2 ∙ 1 = 15 𝑚𝑎𝑛𝑒𝑖𝑟𝑎𝑠 A resposta da questão é 15. Gabarito: A No caso geral, o conjunto original possui n elementos. Queremos formar subconjuntos de p elementos. Logo, teremos p letras S e n – p letras N. Ao dispor os n – p letras N, teremos n – p + 1 espaços vazios para distribuiras letras S. Temos 𝑛 − 𝑝 + 1 espaços vazios porque temos um no início à esquerda e 1 no final à direita. Assim, temos n – p + 1 espaços e devemos escolher p deles para distribuir as letras S, o que pode ser feito de 𝐶KqjLM j 𝑚𝑎𝑛𝑒𝑖𝑟𝑎𝑠 𝑑𝑖𝑓𝑒𝑟𝑒𝑛𝑡𝑒𝑠 Esse raciocínio é exatamente o Primeiro Lema de Kaplansky, que pode assim ser enunciado: O número de subconjuntos de p elementos de {1, 2, 3, ..., n} nos quais não há elementos consecutivos é dado por: 𝑓(𝑛, 𝑝) = 𝐶KqjLM j Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 52 Se você entendeu o raciocínio, não precisará decorar a fórmula acima. (FGV 2019/MPE-RJ – Oficial do Ministério Público) Valdo é estagiário em um escritório de advocacia e, na semana que vem, deverá escolher para trabalhar três dias de segunda a sábado. O escritório não permite que um estagiário trabalhe dois dias consecutivos. O número de possibilidades que Valdo tem para escolher seus dias de trabalho é: a) 2 b) 3 c) 4 d) 5 e) 6 Comentário Perceba que Valdo precisa escolher 3 dentre 6 dias disponíveis na semana que vem (apenas de segunda a sábado, excluindo o domingo). Assim, precisaremos de 3 letras S e 3 letras N. Como Valdo não pode escolher 2 dias consecutivos, então não poderemos ter duas letras S juntas. Dessa forma, vamos utilizar o primeiro lema de Kaplansky. O primeiro passo é fixar as letras N e colocar espaços vazios entre elas. � 𝑁 � 𝑁 � 𝑁 � As 3 letras S deverão ficar nos espaços vazios. Assim, temos 4 espaços vazios e precisamos escolher 3 deles para colocar as letras S. Isso pode ser feito de 𝐶XJ = 4 ∙ 3 ∙ 2 3 ∙ 2 ∙ 1 = 4 𝑚𝑎𝑛𝑒𝑖𝑟𝑎𝑠 Gabarito: C Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 53 Vamos fazer mais um exemplo: Guilherme Neves dará aulas em três dias diferentes na primeira semana de outubro. De quantos modos Guilherme pode escolher os dias das aulas se ele não quer dar aulas em dias consecutivos? a) 10 b) 20 c) 35 d) 42 e) 210 Comentário Perceba que, como estamos nos referindo à primeira semana de determinado mês, o primeiro e o último dia da semana não são consecutivos. São 7 dias na primeira semana de outubro. Guilherme dará aula em 3 dias. Logo, teremos 3 letras S e 4 letras N. Vamos colocar as 4 letras N e destacar os espaços vazios em que podemos distribuir as letras S. � 𝑁 � 𝑁 � 𝑁 � 𝑁 � Temos 5 espaços vazios e devemos escolher 3 para colocar as letras S. Logo, o total de maneiras é: 𝐶IJ = 5 ∙ 4 ∙ 3 3 ∙ 2 ∙ 1 = 10 Gabarito: A Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 54 O raciocínio adotado no Primeiro Lema de Kaplansky pode ser usado para resolver outras questões de Análise Combinatória. Exemplo: Quantos são os anagramas da palavra GUILHERME que não possuem vogais juntas? Comentário A primeira observação é que o problema não quer vogais juntas (nem 2, nem 3, ...). Assim, não podemos simplesmente permutar todas as letras e subtrair as permutações em que as vogais estão juntas. Para ficar mais claro: nem o próprio nome GUILHERME é aceito pela condição dada no enunciado, pois temos as vogais UI juntas. A estratégia é parecida com a de Kaplansky. Vamos posicionar as consoantes. As vogais deverão ocupar os espaços vazios entre as consoantes. __ 𝐺 __ 𝐿__ 𝐻 __ 𝑅__ 𝑀 __ Temos 3 etapas para resolver esse problema: permutar as consoantes entre si, escolher os lugares que as vogais vão ocupar, permutar as vogais entre si. • Podemos permutar as consoantes de 𝑃I maneiras. • Há 6 lugares vazios e devemos escolher 4 lugares para serem ocupados pelas 4 vogais. Isso pode ser feito de 𝐶BX maneiras. • Depois que tivermos escolhido os lugares que as vogais vão ocupar, devemos permutá- las, o que pode ser feito de 𝑃XN maneiras (duas vogais são iguais). Assim, o total de permutações é: 𝑃I ∙ 𝐶BX ∙ 𝑃XN = Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 55 Lembre-se que 𝐶BX = 𝐶BN. Logo, = 5! ∙ 6 ∙ 5 2 ∙ 1 ∙ 4! 2! = 21.600 Gabarito: 21.600 anagramas (CESPE 2011/TRE-ES) De acordo com o primeiro lema de Kaplansky, a quantidade de subconjuntos de {𝟏, 𝟐, 𝟑, … , 𝒏} com 𝒑 elementos, em que não há números consecutivos, é dada pela fórmula abaixo. (𝒏 − 𝒑 + 𝟏)! 𝒑! (𝒏 − 𝟐𝒑 + 𝟏)! Uma das aplicações desse lema é a contagem do número de maneiras de se sentar 4 meninas e 6 meninos em uma fila de 10 cadeiras, de modo que 2 meninas não fiquem em posições adjacentes. A estratégia para se realizar essa contagem compreende quatro passos. Em primeiro lugar, deve-se contar o número de maneiras de se escolher 4 cadeiras sem que haja cadeiras consecutivas; esse procedimento deve ser feito utilizando-se o lema de Kaplansky. Em seguida, deve-se contar o número de maneiras de organizar as meninas nessas cadeiras. O próximo passo consiste em contar o número de maneiras de se distribuir os meninos nas cadeiras restantes. Por fim, deve-se usar o princípio multiplicativo. Com base nessas informações, julgue os itens subsecutivos. 01. Diante dos dados acima, é correto afirmar que o número de maneiras de se sentar 4 meninas e 6 meninos em uma fila de 10 cadeiras, de modo que não fiquem 2 meninas em posições adjacentes, é superior a 600.000. 02. Em face dos dados apresentados, é correto afirmar que o número de maneiras de se escolher as 4 cadeiras entre as 10 disponíveis sem que haja cadeiras consecutivas é superior a 40. 03. A partir dos dados acima, é correto concluir que o número de maneiras de se organizar as 4 meninas nas 4 cadeiras escolhidas é igual a 16. Comentário Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 56 Vamos colocar os 6 homens em posições fixas e destacar os espaços vazios entre eles. __ 𝐻M __ 𝐻N __ 𝐻J __ 𝐻X __ 𝐻I __ 𝐻B __ Como as meninas não podem ficar juntas, então elas devem ocupar 4 dos 7 lugares vazios destacados. Isso pode ser feito de 𝐶oX maneiras. Esse resultado também seria obtido simplesmente substituindo 𝑛 = 10 e 𝑝 = 4 na fórmula dada no enunciado. Observe: 𝐶oX = 7 ∙ 6 ∙ 5 ∙ 4 4 ∙ 3 ∙ 2 ∙ 1 = 35 (𝑛 − 𝑝 + 1)! 𝑝! (𝑛 − 2𝑝 + 1)! = (10 − 4 + 1)! 4! (10 − 2 ∙ 4 + 1)! = 7! 4! 3! = 7 ∙ 6 ∙ 5 ∙ 4! 4! ∙ 3 ∙ 2 ∙ 1 = 35 Assim, há 35 maneiras de escolher as posições ocupadas pelas meninas. Além disso, devemos permutar os 6 homens entre si e também as 4 mulheres entre si. Logo, o número de maneiras se sentar 4 meninas e 6 meninos em uma fila de 10 cadeiras, de modo que não fiquem 2 meninas em posições adjacentes, é 35 × 𝑃B × 𝑃X = 35 × 6! × 4! = 604.800 O item I está certo. O item II pergunta justamente de quantas maneiras podemos escolher as cadeiras em que as mulheres se sentarão. Vimos que esse resultado é igual a 35. Logo, o item II está errado. O item III pergunta de quantas maneiras podemos permutar as mulheres nas cadeiras escolhidas. Podemos fazer isso de 𝑃X = 4! = 24 maneiras. O item III está errado. Gabarito: Certo, errado, errado Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 57 (CESPE 2019/Prefeitura de São Cristóvão) Situação hipotética: As 5 lâmpadas tubulares de uma sala de aula foram instaladas formando uma única fileira. Por motivo de economia, 2 lâmpadas adjacentes nuncapoderão ficar acesas ao mesmo tempo. Assertiva: Nessa situação, há exatamente 13 configurações distintas, incluindo todas as lâmpadas desligadas, que atendem à exigência de economia. Comentário O primeiro caso é quanto todas as lâmpadas estão desligadas. 𝐿â𝑚𝑝𝑎𝑑𝑎𝑠 𝑑𝑒𝑠𝑙𝑖𝑔𝑎𝑑𝑎𝑠 → 𝟏 𝒎𝒂𝒏𝒆𝒊𝒓𝒂 O segundo caso é quando temos 1 lâmpada acesa e 4 desligadas. Ora, nem precisamos do lema de Kaplansky para isso. Há 5 possibilidades: acender apenas a primeira, acender apenas a segunda, acender apenas a terceira, acender apenas a quarta ou acender apenas a quinta. Ah, Guilherme, mas como ficaria o raciocínio de Kaplansky? Ora, temos 4 letras N para as lâmpadas desligadas. __ 𝑁__𝑁__ 𝑁__𝑁__ Assim, temos 5 espaços vazios. Como teremos apenas uma lâmpada acesa, precisamos escolher 1 lugar vazio dentre 5, o que pode ser feito de 𝐶IM = 5 𝑚𝑎𝑛𝑒𝑖𝑟𝑎𝑠. O terceiro caso é quando temos 2 lâmpadas acesas e 3 desligadas. Designando por N cada lâmpada desligada, temos a seguinte configuração. __ 𝑁__𝑁__ 𝑁__ Precisamos encaixar as 2 lâmpadas acesas nos espaços vazios. Há 4 espaços vazios e precisamos escolher 2 para colocar as lâmpadas acesas. Logo, podemos fazer essa escolha de 𝐶XN = 4 ∙ 3 2 ∙ 1 = 𝟔 𝒎𝒂𝒏𝒆𝒊𝒓𝒂𝒔. Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 58 O quarto caso é quando temos 3 lâmpadas acesas e 2 desligadas. Designando por N cada lâmpada desligada, temos a seguinte configuração. __ 𝑁__𝑁__ Precisamos encaixar as 3 lâmpadas acesas nos espaços vazios. Há 3 espaços vazios e precisamos escolher 3 para colocar as lâmpadas acesas. Logo, podemos fazer essa escolha de 𝐶JJ = 𝟏 𝒎𝒂𝒏𝒆𝒊𝒓𝒂, que é SNSNS. O quinto caso seria termos 4 lâmpadas acesas e 1 desligada. Entretanto, esse caso não nos interessa porque certamente teríamos lâmpadas acesas adjacentes. O total de maneiras é 1 + 5 + 6 + 1 = 13 Gabarito: Certo 12.2. Segundo Lema de Kaplansky Pois bem, até agora nunca vi uma questão envolvendo o segundo lema de Kaplansky, mas vai que... Vamos agora considerar que 1 e n são consecutivos no conjunto {1, 2, ..., n}. Isso é bem comum em questões envolvendo calendários. Por exemplo, o 31 de dezembro e 1 de janeiro são consecutivos, sábado e domingo são dias consecutivos, etc. O Segundo Lema de Kaplansky diz que o número de subconjuntos com p elementos do conjunto {1, 2, 3, ..., n}, em que 1 e n são considerados consecutivos, é igual a 𝑔(𝑛, 𝑝) = 𝑛 𝑛 − 𝑝 ∙ 𝐶Kqj j Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 59 A fórmula acima é um pouco trabalhosa de ser demonstrada (a demonstração pode ser encontrada no livro Análise Combinatória e Probabilidade da Sociedade Brasileira de Matemática). Acho melhor torcer para isso não cair. Não vale a pena memorizar essa fórmula, pois a relação custo-benefício é péssima: nunca vi cair em prova (até agora). Por isso, vou ensinar o raciocínio da demonstração para que você não precise memorizar a fórmula. Exemplo: O professor Guilherme Neves decidiu estudar piano 3 vezes por semana. De quantas maneiras Guilherme pode escolher os dias de estudo, se ele não quer estudar piano em dias consecutivos? a) 5 b) 6 c) 7 d) 8 e) 9 Comentário Situação típica do Segundo Lema de Kaplansky, pois, como a atividade será feita periodicamente, sábado e domingo (último dia e primeiro dia da semana) são consecutivos. Vamos considerar que Domingo = 1, Segunda-feira = 2, ..., Sábado = 7. Assim, temos o conjunto {1, 2, 3, 4, 5, 6, 7}. Na situação, 1 e 7 são consecutivos. Guilherme precisa escolher 3 números não consecutivos. Pelo Segundo Lema de Kaplansky, isso pode ser feito de: 𝑔(7,3) = 7 7 − 3 ∙ 𝐶oqJ J = 7 4 ∙ 𝐶X J = 7 4 ∙ 4 ∙ 3 ∙ 2 3 ∙ 2 ∙ 1 = 7 E como é o raciocínio sem decorar fórmula? Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 60 Pois bem, o segundo lema de Kaplansky é, na verdade, o primeiro lema aplicado duas vezes. Vamos separar em dois casos: o elemento 1 foi escolhido e o elemento 1 não foi escolhido. • Subconjuntos nos quais figura o elemento 1. Se o elemento 1 foi escolhido, não podemos escolher os elementos 2 e 7, porque são elementos vizinhos ao número 1. Assim, devemos escolher 2 elementos não consecutivos no conjunto {3, 4, 5, 6}. Vamos aplicar o primeiro lema de Kaplansky. Para escolher 2 elementos dentre os 4, devemos ter duas letras N e duas letras S. As letras S não podem ficar juntas porque os números não são consecutivos. Começamos fixando as letras N. __N__N__ Assim, temos 3 espaços vazios e devemos escolher 2 deles para colocar as letras S. Isso pode ser feito de 𝐶JN = 3 ∙ 2 2 ∙ 1 = 3 𝑚𝑎𝑛𝑒𝑖𝑟𝑎𝑠 • Subconjuntos nos quais não figura o elemento 1. Nesse caso, precisamos escolher 3 elementos não consecutivos no conjunto {2, 3, 4, 5, 6, 7}. Vamos aplicar novamente o primeiro lema de Kaplansky. Para escolher 3 elementos dentre os 6, devemos ter três letras N e três letras S. As letras S não podem ficar juntas porque os números não são consecutivos. Começamos fixando as letras N. __N__N__N__ Assim, temos 4 espaços vazios e devemos escolher 3 deles para colocar os sinais de “+”. Isso pode ser feito de 𝐶XJ = 4 ∙ 3 ∙ 2 3 ∙ 2 ∙ 1 = 4 𝑚𝑎𝑛𝑒𝑖𝑟𝑎𝑠 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 61 O total de maneiras é 3 + 4 = 7 maneiras. Como vocês podem ver, o Segundo Lema de Kaplansky é, na verdade, o primeiro lema aplicado duas vezes: uma vez escolhendo o número 1 e outra vez excluindo o número 1. Gabarito: C (Banca GNBPT – Guilherme Neves Botando pra Torar) Severino Kaplansky comprou um lustre circular com 6 lâmpadas. Por motivo de economia, 2 lâmpadas adjacentes nunca poderão ficar acesas simultaneamente. De quantas maneiras Kaplansky pode escolher quais lâmpadas acender, incluindo todas as lâmpadas desligadas, que atendem à exigência de economia? a) 17 b) 18 c) 19 d) 20 e) 21 Comentário Fiz uma adaptação da questão do CESPE que resolvi quando expliquei o primeiro lema de Kaplansky. A diferença é que agora as lâmpadas estão em uma disposição circular e, portanto, a sexta lâmpada é adjacente à primeira lâmpada. L1 L2 L3 L4 L5 L6 Guilherme Neves Aula 05 Raciocínio Lógico p/ PC-PA - Pós-Edital www.estrategiaconcursos.com.br 1442029 00697812227 - CINTHYA ELEN PEREIRA DE LIMA 62 Temos um conjunto de 6 lâmpadas {𝐿M, 𝐿N, 𝐿J, 𝐿X, 𝐿I, 𝐿B} em que 𝐿M e 𝐿B são consecutivos. Nesse caso, 𝑛 = 6. Queremos escolher 0, 1, 2, 3,... lâmpadas não consecutivas. Quem consegue decorar a fórmula, faria assim: • Nenhuma lâmpada acesa = 1 maneiras, que corresponde a 𝑔(6,0) = 6 6 − 0 ∙ 𝐶BqY Y = 6 6 × 𝐶B Y = 1 × 1 = 1 • Uma lâmpada acesa = 6 casos (acender a primeira, ou a segunda, ou a terceira, ...), que correspondem a: 𝑔(6,1) = 6 6 − 1 ∙ 𝐶BqM M = 6 5 × 𝐶I M = 6 5 × 5 = 6 • Duas lâmpadas acesas 𝑔(6,2) = 6 6 − 2 ∙ 𝐶BqN N = 6 4 × 𝐶X N = 6 4 × 6 = 9 • Três lâmpadas acesas 𝑔(6,3) = 6 6 − 3 ∙ 𝐶BqJ J = 6 3 × 𝐶J J = 6 3 × 1 = 2 • Quatro lâmpadas acesas Veja que é impossível termos 4 lâmpadas acesas sem haver 2 adjacentes acesas simultaneamente. Veja que absurdo aconteceria com a fórmula de Kaplansky. 𝑔(6,4) = 6 6 − 4 ∙ 𝐶BqX X = 6 4 × 𝐶N X = 𝑖𝑚𝑝𝑜𝑠𝑠í𝑣𝑒𝑙 Não temos como calcular 𝐶NX porque 2 < 4. Logo, o total de possibilidades é 1 + 6 + 9 + 2 = 18. Vamos agora resolver o problema sem o uso da fórmula. Eu, Guilherme, não sei essa fórmula decorada. Sei agora porque
Compartilhar