mat 2 - aula 7

Prévia do material em texto

Apostila de Matemática 2 - Extensivo
Aula 7 – Análise Combinatória: Permutação com Repetição, Permutação circular, Número de soluções inteiras não negativas e Número de soluções inteiras positivas de uma equação linear.
Permutação com Repetição:
Imagine que um professor peça para que a turma contabilize o número de anagramas possíveis para a palavra ARARAS. Um aluno com pouca experiência, sem perceber que nessa palavra temos letras repetidas, usaria a fórmula de permutação simples e diria que essa palavra tem um total de 6! = 720 anagramas, resultado incorreto. Mas por que essa resposta não está correta?
Vamos resolver essa questão sem a fórmula de permutação com repetição, ainda desconhecida. Nela, devemos ordenar os 6 elementos. Começaremos com os que se repetem, como por exemplo a letra A, que aparece 3 vezes. Assim, devemos escolher 3 posições entre as 6 possíveis (total de letras) para alocar as letras A. É importante ressaltar que se as letras A entram nas posições 1, 3 e 6 por exemplo temos uma situação idêntica ao cenário em que as letras A entram nas posições 6, 3 e 1, ou seja, a ordem não importa. Por isso, para alocar as letras A em 3 das 6 posições possíveis, usaremos a fórmula da combinação. No caso, teríamos C6,3 maneiras de alocar as letras A.
Seguindo para as letras R, percebemos que devemos escolher 2 posições para alocar essas letras entre as 3 possíveis que sobraram após a colocação das letras A. Da mesma forma que no caso anterior, utilizaremos a fórmula da combinação, visto que a ordem não influencia no resultado (se trocarmos as duas letras R de posição entre si, teremos o mesmo anagrama). Assim, teríamos C3,2 maneiras de alocas as letras R.
Sobra apenas um espaço para a última letra (letra S) e por isso, só há uma forma de alocar essa letra no anagrama. Como devemos alocar as letras A E alocar as letras R E alocar a letra S, usamos o princípio multiplicativo.
C6,3 . C3,2 . 1 = 1 = = 60 anagramas
Repare que após expandirmos as combinações utilizadas temos uma expressão bem interessante. Nela, o numerador apresenta um fatorial com o número total de letras da palavra dada e no denominador temos um produto entre fatoriais entre os números de elementos repetidos. Assim, temos a fórmula da permutação com repetição:
Pn(x1,x2,x3,..) = 
Onde n é o número total de elementos e x1, x2, x3 são os números de elementos repetidos. Vejamos outros exemplos:
AMAR = 12 anagramas
CADEIRA = 2520 anagramas
MAMÃE = 30 anagramas
MATEMÁTICA = 151.200 anagramas
Permutação Circular:
Imagine que você e mais 3 amigos resolvem se sentar ao redor de uma mesa circular. De quantas maneiras possíveis isso pode acontecer? Um aluno inexperiente diria que devemos alocar 4 pessoas em 4 posições e, usando a fórmula da permutação simples, teríamos 4! = 24 maneiras diferentes de posicionar o grupo. Esse raciocínio está incorreto, visto que estamos contando cada caso 4 vezes. Observe a figura abaixo:
Observe que em qualquer uma das 4 figuras, você está de frente para o amigo B, do seu lado esquerdo está sempre o amigo A e do seu lado direito está sempre o seu amigo C. Ou seja, essas 4 possibilidades são na verdade apenas uma. Assim, o número de posicionamentos é dado por:
PC(4) = = 3! = 6 ordens possíveis.
Assim, podemos expressar a fórmula da permutação circular:
PC (n) = (n-1)!, com n natural maior que 1.
Uma outra maneira de visualizar esse cenário é entender que a primeira pessoa não influencia no resultado. Em outras palavras: é a partir da segunda pessoa que começamos a visualizar uma ordem entre os integrantes do grupo. No nosso exemplo, se você fosse a primeira pessoa a se posicionar, somente a próxima pessoa começaria a influenciar o resultado. Ela poderia se posicionar de frente para você, na cadeira que está do seu lado direito ou na cadeira que está no seu lado esquerdo. Assim, posicionando o grupo, pessoa por pessoa, lembre-se que a primeira sempre tem apenas uma possibilidade posicionamento no cenário circular. Assim:
1.3.2.1 = 6 ordens possíveis.
Ex.: Cinco pessoas, entre elas Rui e Jô, vão a um bar e o garçom apresenta uma mesa circular ao grupo, com 5 cadeiras ao seu redor. Sabendo que Jô só aceita se sentar ao lado de Rui, de quantas maneiras esse grupo pode se alocar ao redor dessa mesa?
Começaremos posicionando Rui e, como ele será o primeiro a se posicionar, teremos apenas 1 possibilidade. Jô só pode se sentar ao lado de Rui e, por isso, tem apenas 2 possibilidades de entrada ao redor da mesa (do lado direito ou do lado esquerdo de Rui). Sobram 3 cadeiras para 3 pessoas e assim teremos para elas 3! maneiras de posicionamento. Usando o princípio multiplicativo, teremos:
1. 2 . 3! = 12 acomodações possíveis.
Número de soluções inteiras não-negativas de uma equação linear:
Imagine que você quer dividir 5 canetas entre 3 amigos seus. Nessa divisão, você está liberado para dividir da maneira que quiser, ou seja, você pode espalhar as canetas entre seus 3 amigos, deixar um amigo sem canetas ou até mesmo entregar todas as canetas para apenas um dos seus amigos. Na figura abaixo, temos algumas possibilidades de divisões dessas 5 canetas.
Nessas representações, cada bolinha representa uma caneta e as 2 barrinhas servem para distribuir as canetas em 3 regiões (referentes aos 3 amigos). Assim, no exemplo, temos:
Divisão 1: amigo A com 1 caneta, amigo B com 3 canetas e amigo C com 1 caneta.
Divisão 2: amigo A sem canetas, amigo B com 3 canetas e amigo C com 2 canetas.
Divisão 3: amigo A com 3 canetas, amigo B sem caneta e amigo C com 2 canetas.
Divisão 4: amigo A sem canetas, amigo B com 5 canetas e amigo C sem canetas.
Perceba que cada divisão é uma ordem diferente entre esses 7 elementos. Se queremos saber quantas divisões possíveis temos nessa situação, podemos calcular então o número de ordens possíveis para esses 7 elementos. Lembre-se também que temos elementos repetidos nos exemplos e, por isso, usaremos a fórmula da permutação com repetição. Assim, teremos:
P7(5,2) = = 21 divisões possíveis.
Número de soluções inteiras positivas de uma equação-linear:
Imagine agora que você quer dividir 5 balas entre 3 crianças e, para não provocar descontentamento, podemos até dar mais balas para uma criança do que para outra, mas não podemos deixar criança qualquer sem bala. Dessa forma usaremos 5 bolinhas novamente para representar nesse caso as 5 balas, mas lembraremos que não podemos colocar a barrinha na frente da representação (isso significaria que a primeira criança ficaria sem bala) e nem no final da representação (isso significaria a última criança sem bala). Além disso, não podemos colocar mais de uma barrinha por espaço entre as bolinhas (isso significaria alguma criança sem bala também). Visto isso, observe a figura:
As setas indicam os espaços onde podemos colocar as barrinhas. Vale ressaltar que em nenhum desses espaços podemos colocar mais do que uma barrinha, ou seja, em cada um desses espaços ou colocaremos uma barrinha ou não colocaremos barrinha. Por isso, pensaremos que dos 4 espaços possíveis para colocar barrinhas, escolheremos 2 para efetivamente colocar (2 barrinhas dividem a região em 3 sub-regiões). Também devemos pensar que colocar as duas barrinhas no espaço 1 e no espaço 3 é igual a colocar as duas barrinhas no espaço 3 e no espaço 1, isto é, a ordem não influenciará no resultado. Por isso, usaremos a fórmula da combinação simples. Assim:
C4,2 = = 6 divisões possíveis.
EXERCÍCIOS:
01) (UERJ) Uma criança ganhou seis picolés de três sabores diferentes: baunilha, morango e chocolate, representados, respectivamente, pelas letras B, M e C. De segunda a sábado, a criança consome um único picolé por dia, formando uma sequência de consumo dos sabores. Observe estas sequências, que correspondem a diferentes modos de consumo: 
(B,B,M,C,M,C) ou (B,M,M,C,B,C) ou (C,M,M,B,B,C)
O número total de modos distintos de consumir os picolés equivale a:
a) 6		b) 90		c) 180		d) 720
02) (PUC-RJ) A quantidade de anagramas da palavra CONCURSO é:
a) 2520		b) 5040		c) 10080	d) 20160	e) 4032003) (IBMEC-RJ) O número de anagramas que podem ser formados com as letras de PAPAGAIO, começando por consoante e terminando por O, é igual a:
a) 120		b) 180		c) 240		d) 300		e) 320
04) (VUNESP) A figura mostra a planta de um bairro de uma cidade. Uma pessoa quer caminhar do ponto A ao ponto B por um dos percursos mais curtos. Assim, ela caminhará sempre nos sentidos “de baixo para cima” ou “da esquerda para a direita”. O número de percursos diferentes que essa pessoa poderá fazer de A até B é: 
a) 95040	b) 40 635	c) 924 		d) 792		e) 35
05) (AFA) O número de anagramas da palavra ALAMEDA que não apresenta as 4 vogais juntas é:
a) 96 		b) 744 		c) 816 		d) 840
06) (UNITAU) O número de anagramas da palavra BIOCIÊNCIAS que terminam com as letras AS, nesta ordem é: 
a) 9! 		b) 11! 		c) 9!/(3! 2!) 	d) 11!/2! 	e) 11!/3!
07) (MACKENZIE) Uma urna contém 6 bolas pretas idênticas e 3 bolas brancas, também idênticas. Retiradas, uma de cada vez, a extração das 9 bolas pode ser feita de k formas diferentes. Então k vale: 
a) 9! 		b) 84 		c) 81 		d) 6.6! 		e) 162
08) (UFRS) No desenho a seguir, as linhas horizontais e verticais representam ruas, e os quadrados representam quarteirões. 
A quantidade de trajetos de comprimento mínimo ligando A e B que passam por C é:
a) 12 		b) 13 		c) 15 		d) 24 		e) 30
09) (UFSM) De quantas maneiras distintas podem-se alinhar cinco estacas azuis idênticas, uma vermelha e uma branca? 
a) 12 		b) 30 		c) 42 		d) 240 		e) 5040
10) (FGV-SP) Um fundo de investimento disponibiliza números inteiros de cotas aos interessados nessa aplicação financeira. No primeiro dia de negociação desse fundo, verifica-se que 5 investidores compraram cotas, e que foi vendido um total de 9 cotas. Em tais condições, o número de maneiras diferentes de alocação das 9 cotas entre os 5 investidores é igual a:
a) 56		b) 70		c) 86		d) 120		e) 126
11) (ESAF) De quantas maneiras podem sentar-se três homens e três mulheres em uma mesa redonda, isto é, sem cabeceira, de modo a se ter sempre um homem entre duas mulheres e uma mulher entre dois homens?
a) 12		b) 36		c) 216		d) 720		e) 360
12) (PUC-SP) Dois meninos e três meninas formarão uma roda dando-se as mãos. De quantos modos diferentes poderão formar a roda de modo que os dois meninos não fiquem juntos?
a) 15 	b) 24 	c) 18 	d) 16 	e) 12
13) (FGV-SP) Quantos números diferentes obtemos reagrupando os algarismos do número 718.844?
a) 90 	b) 720 	c) 15 	d) 30 	e) 180
14) (UFU-MG) O número de anagramas da palavra ERNESTO, começando e terminando por consoante, é:
a) 480 	b) 720 	c) 1440 	d) 1920 	e) 5040
15) (UFSC) Um experimento consiste em lançar uma moeda 6 vezes. Considera-se como resultado desse experimento a sequência das faces obtidas no 1º, 2º, 3º, 4º, 5º e 6º lançamento, respectivamente. Por exemplo, indicando por c a face “cara” e por k a face “coroa”, um resultado possível desse experimento é a sequência (c, c, k, c, k, c). O número de resultados possíveis desse experimento apresentando quatro caras e duas coroas é: 
a) 30 	b) 24 	c) 20 	d) 18 	e) 15
16) (ITA) O número de soluções inteiras e não-negativas da equação x + y + z + w = 5 é:
a) 36 	b) 48 	c) 52 	d) 54 	e) 56
17) (SELESSUL) O número de permutações distintas possíveis com as 8 letras da palavra PARALELA, começando todas com a letra P, será de: 
a) 120 		b) 720 		c) 420 		d) 24 		e) 360 
18) (UFSC) Quantos números pares de 5 algarismos podemos escrever apenas com os dígitos 1, 1, 2, 2 e 3, respeitadas as repetições apresentadas? 
a) 12 		b) 30 		c) 6 		d) 24 		e) 18
19) (UFRGS) Se uma partida de futebol termina com o resultado de 5 gols para o time A e 3 gols para o B, existem diversas maneiras de o placar evoluir de 0 x 0 a 5 x 3. Por exemplo, uma evolução poderia ser: 
Quantas maneiras, no total, tem o placar de evoluir de 0 x 0 a 5 x 3? 
a) 16 		b) 24 		c) 36 		d) 48 		e) 56
20) (FGV-SP) O número de permutações da palavra ECONOMIA que não começam nem terminam com a letra O é:
a) 9400 	b) 9600 	c) 9800 		d) 10200 	e) 10800
21) (UFSC) Quantos números diferentes podemos obter permutando os algarismos do número 336223? 
a) 30 		b) 40		c) 50		d) 60
22) (UEPG-PR) Com uma letra R, uma letra A e um certo número de letras M, podemos formar 20 permutações. O número de letras M é: 
a) 6 		b) 12		c) 4		d) 3		e) 8
23) (PUC-RJ) Pedro mora em um bairro com ruas no sentido leste-oeste e avenidas no sentido norte-sul. A casa de Pedro está em uma esquina três quadras ao norte e quatro quadras a oeste de sua escola (que também fica em uma esquina). Pedro vai a pé de sua casa até a escola e gosta de variar o caminho, mas sempre usando caminhos de comprimento mínimo. Quantos caminhos diferentes ele pode fazer?
a) 12		b) 21		c) 28		d) 35		e) 42
24) (FGV-SP) O número de anagramas diferentes que podem ser construídos com as letras da palavra VARGAS, e que comecem e terminem com consoantes é:
a) 360		b) 15		c) 24		d) 144		e) 288
25) (ESPCEX) Se todos os anagramas da palavra ESPCEX forem colocados em ordem alfabética, a palavra ESPCEX ocupará, nessa ordenação, a posição.
a) 144		b) 145		c) 206		d) 214		e) 215
26) (IME) É dado um tabuleiro quadrado 4x4. Deseja-se atingir o quadrado inferior direito a partir do quadrado superior esquerdo. Os movimentos permitidos são os representados pelas setas: 
De quantas maneiras isto é possível?
27) (UNICAMP) De quantas maneiras é possível distribuir 20 bolas iguais entre 3 crianças de modo que cada uma delas receba, pelo menos, 5 bolas?
28) (UERJ) Um sistema luminoso, constituído de oito módulos idênticos, foi montado para emitir mensagens em código. Cada módulo possui três lâmpadas de cores diferentes − vermelha, amarela e verde. Observe a figura:
Considere as seguintes informações:
• cada módulo pode acender apenas uma lâmpada por vez;
• qualquer mensagem é configurada pelo acendimento simultâneo de três lâmpadas vermelhas, duas verdes e uma amarela, permanecendo dois módulos com as três lâmpadas apagadas;
• duas mensagens são diferentes quando pelo menos uma das posições dessas cores acesas é diferente. 
Calcule o número de mensagens distintas que esse sistema pode emitir.
29) (UNIRIO) Uma pessoa quer comprar 6 empadas numa lanchonete. Há empadas de camarão, frango, legumes e palmito. Sabendo-se que podem ser compradas de zero a 6 empadas de cada tipo, de quantas maneiras diferentes esta compra pode ser feita?
30) (FUVEST) A figura a seguir representa parte do mapa de uma cidade onde estão assinalados as casas de João(A), de Maria(B), a escola(C) e um possível caminho que João percorre para, passando pela casa de Maria, chegar à escola. 
Qual o número total de caminhos distintos que João poderá percorrer, caminhando somente para o Norte ou Leste, para ir de sua casa à escola, passando pela casa de Maria?
31) (UEL) Usando uma vez a letra A, uma vez a letra B e (n – 2) vezes a letra C, podemos formar 20 anagramas diferentes com n letras em cada anagrama. Calcule n.
32) (UFRJ) Uma partícula desloca-se sobre uma reta, percorrendo 1 cm para esquerda ou para direita a cada movimento. Calcule de quantas maneiras diferentes a partícula pode realizar uma sequência de 10 movimentos terminando na posição de partida. 
33) (UFF) Percorrendo-se uma unidade de comprimento por vez, em movimentos paralelos aos eixos coordenados e no sentido positivo dos mesmos, deseja-se caminhar da origem até o ponto (3,3), conforme o exemplificado na figura . Determine de quantas maneiras isto pode ser feito.
34) (UNB) Considere que um decorador deva usar 7 faixas coloridas de dimensões iguais, pendurando-as verticalmente na vitrine de uma loja para produzir diversas formas. Nessa situação, se 3 faixas são verdes e indistinguíveis, 3 faixas são amarelas e indistinguíveis e 1 faixa é branca, esse decorador conseguirá produzir, no máximo, quantas formas diferentes com essas faixas?
35) (PUC-SP) Alfredo, Armando, Ricardo, Renato e Ernesto querem formar umasigla com cinco símbolos, onde cada símbolo é a primeira letra de cada nome. Qual o número total de siglas possíveis?
36) (UFRJ) Considere trajetórias estabelecidas no espaço por segmentos de reta consecutivos de modo que todos os segmentos tenham comprimento 1 e sejam paralelos a um dos seguintes vetores: (0,0,1), (0,1,0) ou (1,0,0). 
Assim, as duas sequências de pontos a seguir definem trajetórias diferentes que partem do ponto (0,0,0) e chegam ao ponto (2,1,2); a primeira tem comprimento 5, e a segunda, comprimento 7. 
Trajetória 1: (0,0,0) → (1,0,0) → (1,1,0) → (2,1,0) → (2,1,1) → (2,1,2) 
Trajetória 2: (0,0,0) → (0,1,0) → (0,1,1) → (0,1,2) → (0,1,3) → (0,1,2) → (1,1,2) → (2,1,2)
Determine quantas trajetórias assim definidas partem do ponto (0,0,0), chegam ao ponto (4,3,2) e têm o menor comprimento possível.
37) (OPM) Uma formiga está em um canto de uma armação de varetas de dimensões 2, 3 e 4. No canto oposto ao da formiga, está um torrão de açúcar. Ela é esperta e só anda para frente, para cima ou para a direita.
Quantos caminhos distintos a formiga pode percorrer para chegar ao torrão?
38) (IME) De quantas maneiras 3 rapazes e 2 moças podem ocupar 7 cadeiras em fila, de modo que as moças sentem juntas uma das outras, e os rapazes juntos uns dos outros.
39) (AFA) Numa sala de aula, estão presentes 5 alunos e 6 alunas. Para uma determinada atividade, o professor deverá escolher um grupo formado por 3 dessas alunas e 3 dos alunos. Em seguida, os escolhidos serão dispostos em círculo de tal forma que alunos do mesmo sexo não fiquem lado a lado. Isso poderá ocorrer de n maneiras distintas. Determine n.
40) (PUC-MG) Deseja-se guardar 10 bolas em quatro caixas, cada uma delas podendo conter de 0 a 10 bolas. De quantas maneiras é possível distribuir essas bolas?
GABARITO:
01) B	02) C	03) B	04) D	05) B	06) C	07) B	08) E	09) C	10) B
11) A	12) E	13) E	14) B	15) E	16) E	17) C	18) B	19) E	20) E
21) D	22) D	23) D	24) D	25) B
26) 58 maneiras
27) 21 maneiras
28) 1680 mensagens
29) 84 maneiras
30) 150 caminhos
31) n=5
32) 252 maneiras
33) 20 maneiras
34) 140 formas
35) 30 siglas
36) 1260 trajetórias
37) 1260 caminhos
38) 144 maneiras
39) n=2400
40) 286 maneiras