Analise-combinatoria-i PDF

Preview

Summary

topndklhldjviojn ,f vjkhllsd .smildf...

Description

ANÁLISE COMBINATÓRIA I PRINCÍPIOS DE CONTAGEM

distintas de se ir de B até C e 3 maneiras distintas de se ir de C até D então, pelo MP, o número de maneiras de se ir de A até D passando por B e C é dado por 2 × 5 × 3 = 30.

INTRODUÇÃO Frequentemente, no nosso dia a dia, precisamos enumerar “eventos” tais como, arrumação de objetos de certa maneira, particionar coisas sob uma certa condição, distribuições para certos fins etc. Para fazermos isto, antes de tudo, precisamos enunciar dois teoremas que são fundamentais em todos os problemas de contagem.

O PRINCÍPIO ADITIVO (AP) Suponha que existam n 1 maneiras para o evento E1 ocorrer, n 2 maneiras para o evento E2 ocorrer,

 n k maneiras para o evento Ek ocorrer, onde k ≥ 1. Se estas maneiras para as ocorrências dos eventos distintos forem disjuntas duas a duas então o número de maneiras nas quais pelo menos um dos eventos E1, E2, ..., ou Ek pode ocorrer é

Observação 1. Como afirmações matemáticas, tanto o AP quanto o MP são triviais e por esta razão são frequentemente negligenciados por aqueles que começam a estudar combinatória o que é uma pena pois, na realidade, eles são fundamentais na resolução de problemas de contagem. Como veremos, nos exemplos, um dado problema de contagem independente de quão complicado seja ele pode sempre ser decomposto em alguns mais simples que podem ser contados usando AP e/ou MP. 2. As palavras “e” e “ou” indicam geralmente quando um ou outro princípio é mais apropriado para a resolução de um problema. A palavra “e” sugere o princípio multiplicativo (MP) e a palavra “ou” o princípio aditivo (AP).

ARRUMAÇÕES E ESCOLHAS SIMPLES

k

n1  n2  ...  nk 

n

DEFINIÇÕES

i

i 1

Assim, por exemplo, se podemos ir de uma cidade P a uma cidade Q por vias aérea, marítima e rodoviária, e supondo que existam 2 companhias marítimas, 3 companhias aéreas e 2 companhias rodoviárias que fazem o trajeto entre P e Q, então pelo AP o número total de se fazer o trajeto de P a Q pelo mar, pelo ar ou por rodovia é 2 + 3 + 2 = 7. Uma forma equivalente do AP usando a terminologia dos conjuntos onde |X| representa o número de elementos do conjunto X é o seguinte: Sejam A1, A2, ..., Ak conjuntos finitos quaisquer onde k ≥ 1. Se os conjuntos dados são distintos dois a dois, então k

A

i

k

 A1  A2  ...  Ak 

i1

A

i

i1

O PRINCÍPIO MULTIPLICATIVO (MP) Supondo que um evento E possa ser decomposto em r eventos ordenados E1, E2, ..., Er e que existam. n 1 maneiras para o evento E1 ocorrer n 2 maneiras para o evento E2 ocorrer

 n r maneiras para o evento Er ocorrer Então o número de maneiras do evento E ocorrer é dado por r

n1  n2  ...  nr 

n

1

i1

Assim, por exemplo, se para irmos de uma cidade A até uma cidade D devemos passar pelas cidades B e C, nesta ordem, e supondo que existam duas maneiras distintas de ir de A até B, 5 maneiras

Uma permutação de n objetos distintos é qualquer agrupamento ordenado desses n objetos isto é, uma arrumação em ordenação dos n objetos. Uma k-permutação ou uma permutação de classe k dos n objetos distintos é uma arrumação utilizando k dos n objetos (uma k-permutação é o que os livros tradicionais chamam de “arranjo de k coisas dentre n”). Usaremos P (n, k) · A (n, k) ouAnk para denotar o número de k-permutações de um conjunto de n objetos. Do princípio multiplicativo obtemos: P(n,2) = n · (n – 1); P(n,3) = n · (n – 1) · (n – 2) e P(n,n) = n · (n – 1) · (n – 2) ... 3 · 2 · 1. Consideremos os n objetos x1, x2, x3, ..., xn e as n posições:

___ ___ ___ ... ___ p1

p2

p3

...

pn

Enumerando todas as permutações dos n objetos x1, x2, x3, ..., xn temos que o número de tais permutações é igual ao número de modos possíveis de se ocupar com esses n objetos as n posições p1, p2, p3, ..., pn. Para a posição p1 existem n escolhas na arrumação. Após o preenchimento de p1 existem n – 1 escolhas (os n – 1 objetos remanescentes) para a posição p2. Existem n – 2 maneiras diferentes de ser preenchida a posição p3 após terem sido preenchidas as posições p1 e p2, ..., é finalmente uma escolha para a última posição pn, após terem sido preenchidas as posições p1, p2, p3, ..., pn-1. Portanto, pelo princípio multiplicativo e utilizando a notação n! = n(n – 1)(n – 2)(n – 3) ... 3 · 2 · 1, temos que: O número de modos de ordenar n objetos distintos é n(n – 1)(n – 2)(n – 3) ... 3 · 2 · 1 = n! Assim, temos as fórmulas P(n,n) = n! ou simplesmente Pn = n! e n! Akn  n (n  1)(n  2) ... ( n  ( k  1))  ( n  k)!

PROMILITARES.COM.BR

5

ANÁLISE COMBINATÓRIA I

Por extensão, define-se P0 = 0! = 1 e P1 = 1! = 1 Uma k-combinação ou uma combinação de classe k de n objetos distintos é uma escolha não ordenada ou um subconjunto de k dos o objetos. Representaremos o número de combinações de n objetos distintos de classe k ou tomados k a k por um dos símbolos

C(n, k) ou

 n k

É padronizado ler qualquer um dos dois símbolos como “n escolhe k”. (Outra notação comumente utilizada éCnk.

TEOREMA Se 0 ≤ k ≤ n, então o número de subconjuntos de k elementos de um subconjunto com n elementos ou o número de combinações de n objetos distintos e classe k é dado por

   k!( nn! k)! n k

Prova. O conjunto de todas as permutações simples de k elementos selecionados de um conjunto com n elementos contém n! permutações. Entretanto, cada subconjunto de k elementos ( n − k)! pode ser ordenado de k! maneiras assim, o número de maneiras de primeiro escolher um subconjunto e depois ordenar os elementos deste subconjunto é pelo princípio multiplicativo igual a

  .k! n k

Entretanto, cada uma dessas ordenações é uma diferente permutação de k elementos selecionados dentre todos os n elementos e cada permutação de k elementos distintos surge da escolha de um subconjunto e a seguir, assim

  . k !  (n n!k)! n k

o que produz n k



n!  k!( n  k)!

EXERCÍCIOS DE

FIXAÇÃO 01. (CFT) A quantidade de números de quatro algarismos distintos que podem ser formados com os algarismos 3, 4, 5, 7 e 9 é a) 120 c) 160 b) 140

03. (EEAR) As atuais placas de automóveis possuem três letras do alfabeto latino (incluindo K, W, Y) e quatro algarismos. O número de placas que não repetem nem letras e nem algarismos é 26!10! c) 26! 10! a) 23! 6! 26!10! d) b) 263 · 104 4! 3! 04. (EEAR) O número de anagramas da palavra ESCOLA que começam por S e terminam por L, é a)

720

b) 120

c)

24

d) 12

05. (EEAR) Com os algarismos 1, 2, 4, 5 e 7, a quantidade de números de três algarismos distintos que se pode formar é a) 100 b) 80 c) 60 d) 30 06. (EEAR) Com os algarismos 1, 2, 3, 4 e 5, sem repeti-los, podemos escrever x números de 4 algarismos, maiores que 2400. O valor de x é a)

68

b) 72

c)

78

d) 84

07. (EEAR) Se existem k maneiras possíveis de pintar uma parede com 3 listras verticais, de mesma largura e de cores distintas, dispondo de 12 cores diferentes, então o valor de k está compreendido entre a)

1315 e 1330

c)

b) 1330 e 1345

1345 e 1360

d) 1360 e 1375

08. (CFOE) Com os dígitos 1, 2, 3, 6 e 0, podemos formar x números de 4 algarismos distintos. Então, x é igual a: a) 160 b) 96 c) 180 d) 108 09. (ESA) Com as letras da palavra SARGENTO foram escritos todos os anagramas iniciados por vogais e com as consoantes todas juntas. Quantos são esses anagramas? a) 120960 b) 40320

c) 2160 d) 720

e)

120

10. (EFOMM) O código Morse, desenvolvido por Samuel Morse, em 1835, é um sistema de representação que utiliza letras, números e sinais de pontuação através de um sinal codificado intermitentemente por pulsos elétricos, perturbações sonoras, sinais visuais ou sinais de rádio. Sabendo-se que um código semelhante ao código Morse trabalha com duas letras pré-estabelecidas, ponto e traço, e codifica com palavras de 1 a 4 letras, o número de palavras criadas é: a) 10 c) 20 e) 30 b) 15

d) 210

d) 25 EXERCÍCIOS DE

TREINAMENTO

02. (CFT) Deseja-se colorir os seis triângulos da figura com cores diferentes.

01. (EEAR) Uma classe tem 10 meninos e 9 meninas. Seu professor necessita formar comissões de 7 crianças, sendo 4 meninos e 3 meninas, que incluam obrigatoriamente o melhor aluno dentre os meninos e a melhor aluna dentre as meninas. O número possível de comissões é a)

6

igual a 2300

c)

menor que 2300

Dispondo-se de sete cores, o número de maneiras diferentes de conseguir o que se deseja é a) 3200 b) 4700

02. (EEAR) Com os algarismos 2, 3, 4, 5, 6 e 7 posso escrever ____ números pares de quatro algarismos distintos.

c) 5040 d) 6090

a) 120 b) 180

PROMILITARES.COM.BR

b) maior que 2400

d) igual a 2352

c) 240 d) 360

ANÁLISE COMBINATÓRIA I

03. (EEAR) Em um campeonato de tênis estão inscritos 10 militares. Para disputar o campeonato, esses militares podem formar _____ duplas diferentes. a)

34

b) 35

c)

44

13. (AFA) Em quantos números de 7 algarismos significativos, os algarismos 5 e 8 aparecem exatamente 2 e 3 vezes, respectivamente? a) 10270 b) 10280 c) 10290 d) 10300

d) 45

04. (EEAR) Considere os algarismos 1, 2, 3, 4, 5 e 6. A partir deles, podem ser criados _____ números pares de quatro algarismos distintos.

14. (AFA) Sobre os lados de um triângulo, marcam-se, respectivamente, 4, 5 e 6 pontos distintos dos vértices. O número total de triângulos com vértices nos pontos marcados é:

a)

a)

60

b) 120

c)

180

d) 360

05. (ESPCEX) Um tabuleiro possui 16 casas distribuídas em 4 linhas e 4 colunas. De quantas maneiras diferentes é possível colocar 4 peças iguais nesse tabuleiro de modo que, em cada linha e cada coluna, seja colocada apenas uma peça. a) 4096 c) 256 e) 16 b) 576 d) 64 06. As antigas placas para automóveis, formadas por duas letras seguidas de quatro algarismos, como por exemplo MY – 7406 foram substituídas por placas com três letras seguidas de quatro algarismos, como por exemplo DWK – 2179. Utilizando um alfabeto de 26 letras e supondo que qualquer sequência de letras e algarismos seja permitida (na realidade algumas sequências não são permitidas) quantos veículos a mais podem ser emplacados? 07. (ESPCEX) Sobre um plano α tomam-se 8 pontos distintos dos quais não existem 3 na mesma reta, e fora de α toma-se um ponto A. O número de pirâmides de base quadrangular com vértice em A que pode se obter a partir desses pontos é a) 64 c) 72 e) 96 b) 70

d) 82

d) 2400

210

b) 250

c)

371

e)

756

d) 462

10. (AFA) Um baralho é composto por 52 cartas divididas em 4 naipes distintos (copas, paus, ouros e espadas). Cada naipe é constituído por 13 cartas, das quais 9 são numeradas de 2 a 10, e as outras 4 são 1 valete (J), 1 dama (Q), 1 rei (K) e 1 ás (A). Ao serem retiradas desse baralho duas cartas, uma a uma e sem reposição, a quantidade de sequências que se pode obter em que a primeira carta seja de ouros e a segunda não seja um ás é igual a a)

612

b) 613

c)

614

d) 615

11. (AFA) Lançando-se 4 dados, sucessivamente, o número de maneiras de se obter soma 7 é a)

20

b) 24

c)

72

d) 216

12. (AFA) A quantidade de números naturais de 4 algarismos distintos, formados por 1, 2, 3, 4, 5 e 6, que contém o algarismo 3 ou o algarismo 4 é a)

196

b) 286

c)

421

m

15. (AFA) Se Am+ 2 = 360, então o valor de a)

–1

b) –3

c)

d) 432

( m − 1) ! - m ! é: ( m-1) !

–5

d) –7

16. (AFA) A quantidade de pares de retas reversas que contêm as arestas de um cubo é a)

12

b) 24

c)

36

d) 48

17. (AFA) Colocam-se em ordem crescente todos os números com 5 algarismos distintos, sem repetição, formados com 2, 4, 5, 7 e 8. A posição do número 72584 é a) 76ª b) 78ª c) 80ª d) 82ª 18. (AFA) Seja An,p o número de arranjos simples de n elementos distintos, tomados p a p. A equação An,3 = 6n tem como solução a)

uma raiz nula.

b) uma raiz positiva. c)

duas raízes positivas.

19. (AFA) A palavra que não muda o seu sentido, quer se leia da esquerda para a direita ou da direita para a esquerda, é chamada palíndromo (Ex. ovo, asa, acaiaca, serres, etc.). Considerando-se as 23 letras do nosso alfabeto, quantos anagramas de 6 letras com características de um palíndromo, pode-se formar? a)

c)

336

d) 446

236

b) 233

c)

323

d) 623

20. (ESPCEX) Considere o conjunto de números naturais {1, 2, ..., 15}. Formando grupos de três números distintos desse conjunto, o número de grupos em que a soma dos termos é ímpar é a)

09. (EFOMM) De quantas maneiras diferentes podemos escolher seis pessoas, incluindo pelo menos duas mulheres, de um grupo composto de sete homens e quatro mulheres? a)

b) 355

d) uma raiz positiva e outra negativa.

08. (ESPCEX) Entre duas cidades A e B há dois postos de pedágio, sendo o primeiro com 5 cabines e o segundo com 4 cabines. Há também 10 pontos de abastecimento. Um viajante realizará o percurso entre essas duas cidades passando pelos dois pedágios e parando três vezes para abastecimento. Entendendo por “formas diferentes de realizar o percurso” cada uma das opções de passar pelas cabines de pedágio e parar nos postos de abastecimento, o número de formas diferentes como ele poderá realizar o percurso da cidade A para a cidade B é a) 60 c) 1200 e) 14400 b) 600

301

168.

b) 196.

c)

224.

e)

231.

d) 227.

21. (ESPCEX) Duas instituições financeiras fornecem senhas para seus clientes, construídas segundo os seguintes métodos: 1ª instituição: 5 caracteres distintos formados por elementos do conjunto {1,2,3,4,5,6,7,8,9}; 2ª instituição: 6 caracteres distintos formados por duas letras, dentre as vogais, na primeira e segunda posições da senha, seguidas por 4 algarismos dentre os elementos do conjunto {3,4,5,6,7,8,9}. Para comparar a eficiência entre os métodos de construção das senhas, medindo sua maior ou menor vulnerabilidade, foi definida a grandeza “força da senha”, de forma que, quanto mais senhas puderem ser criadas pelo método, mais “forte” será a senha. Com base nessas informações, pode-se dizer que, em relação à 2ª instituição, a senha da 1ª instituição é a) 10% mais fraca. d) 20% mais fraca. b) 10% mais forte. c)

e)

20% mais forte.

De mesma força.

22. (ESPCEX) Um grupo é formado por oito homens e cinco mulheres. Deseja-se dispor essas oito pessoas em uma fila, conforme figura abaixo, de modo que as cinco mulheres ocupem sempre as posições 1, 2, 3, 4 e 5, e os homens as posições 6, 7 e 8.

PROMILITARES.COM.BR

7

ANÁLISE COMBINATÓRIA I

ímpar e apenas o 1° e o 2° dígitos são iguais entre si. Dessa maneira, se ela esquecer o segredo do cadeado da primeira mala, deverá fazer no máximo (52 x 83) tentativas para abri-lo.

Quantas formas possíveis de fila podem ser formadas obedecendo a essas restrições? a)

56

b) 456

c)

40.320

e)

2400

b) 2000

c)

o segredo do cadeado da segunda mala, o número máximo de tentativas para abri-lo será de 1.890.

f)

apenas os três dígitos consecutivos em ordem crescente do cadeado da primeira mala, ela conseguirá abri-lo com, no máximo, 8 tentativas.

8.648.640

d) 72.072

g) apenas os dois primeiros dígitos do cadeado da segunda mala, deverá tentar no máximo 10 vezes para abri-lo.

23. (EN) Qual a quantidade de números inteiros de 4 algarismos distintos, sendo dois algarismos pares e dois ímpares que podemos formar, usando algarismos de 1 a 9? a)

e)

1840

e)

1200

27. (FUVEST) Doze pontos são assinalados sobre quatro segmentos de reta de forma que três pontos sobre três segmentos distintos nunca são colineares, como na figura.

d) 1440

24. (AFA) Com base no conhecimento sobre análise combinatória, é correto afirmar que (01) existem 2160 possibilidades de 8 pessoas ocuparem um veículo com 3 lugares voltados para trás e 5 lugares voltados para frente, sendo que 2 das pessoas preferem bancos voltados para trás, 3 delas preferem bancos voltados para frente e as demais não têm preferência. (04) com os algarismos 0, 1, 2, 3, 4 e 5, pode-se formar 525 números ímpares com 4 algarismos e que não tenham zeros consecutivos. (08) podem ser formados 330 paralelogramos a partir de 7 retas paralelas entre si, interceptadas por outras 4 retas paralelas entre si. A soma das alternativas corretas é a) 05 b) 09 c)

12

d) 13

25. (AFA) No ano de 2017, 22 alunos da EPCAR foram premiados na Olimpíada Brasileira de Matemática das Escolas Públicas (OBMEP). Desses alunos, 14 ganharam medalhas, sendo 3 alunos do 3º esquadrão, 9 do 2º esquadrão e 2 do 1º esquadrão. Os demais receberam menção honrosa, sendo 2 alunos do 3º esquadrão, 4 do 2º esquadrão e 2 do 1º esquadrão. Para homenagear os alunos premiados, fez-se uma fotografia para ser publicada pela Nascentv em uma rede social. Admitindo-se que, na fotografia, os alunos que receberam menção honrosa ficaram agachados, sempre numa única ordem, sem alteração de posição entre eles, à frente de uma fila na qual se posicionaram os alunos medalhistas, de modo que, nesta fila: - As duas extremidades foram ocupadas somente por alunos do 2º esquadrão que receberam medalha; - Os alunos do 1º esquadrão, que receberam medalha, ficaram um ao lado do outro; e - Os alunos do 3º esquadrão, que receberam medalha, ficaram, também, um ao lado do outro. Marque a alternativa que contém o número de fotografias distintas possíveis que poderiam ter sido feitas. a) (72) · 9! b) (144) · 9!

c) (288) · 9! d) (864) · 9!

26. (AFA) Uma pessoa fará uma viagem e em cada uma de suas duas malas colocou um cadeado contendo um segredo formado por cinco dígitos. Cada dígito é escolhido dentre os algarismos 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9. Na primeira mala, o segredo do cadeado começa e termina com dígito par e os demais são dígitos consecutivos em ordem crescente. Na segunda mala, o segredo do cadeado termina em dígito

O número de triângulos distintos que podem ser desenhados com os vértices nos pontos assinalados é a) 200. b) 204.

PROMILITARES.COM.BR

e)

220.

28. (AFA) Uma pessoa deve escolher (não importando a ordem) sete, dentre dez cartões numerados de 1 a 10, cada um deles contendo uma pergunta diferente. Se nessa escolha houver, pelo menos três, dos cinco primeiros cartõ...