Aula 28 a 33

Prévia do material em texto

MATEMÁTICA
F B O N L I N E . C O M . B R
//////////////////
Professor(a): Isaac Luís
assunto: arranjos, combInações e os Lemas de KapLansKy
frente: matemátIca IV
013.033 - 138677/19
AULAS 28 A 33
EAD – ITA/IME
Resumo Teórico
Arranjos Simples
Definição: Seja A um conjunto com n ≥ 1 elementos. 
Um arranjo simples com 1 ≤ p ≤ n elementos de A é qualquer lista 
ordenada com esses P elementos.
Se A = {1, 2, 3, 4, 5}, as listas (1,2,5); (2,1,5) e (3,2,1), por 
exemplo, são arranjos simples com 3 elementos de A.
Proposição: O número de arranjos simples de n ≥ 1 elementos, 
tomados p a p, denotado por A
n,p
, é dado por
n
n p
!
!
.
−( )
Prova: Para montarmos uma lista ordenada com 1 ≤ p ≤ n 
elementos oriundos de um conjunto A, podemos, inicialmente, 
escolher o elemento que ocupará a primeira posição da lista, o que 
pode ser feito de n modos distintos. Procedendo dessa forma, é fácil 
ver que, para a i-ésima posição da lista, teremos n – (i – 1) possíveis 
escolhas. Daí, pelo princípio multiplicativo,
A n i
n i n p
n p
n
n
n p
i
p
i
p
,
!
!
!
= − −( )  =
− −( ) { } −( )
−( ) =
−=
=∏
∏
1
1
1
1
pp( )!.
Exemplo 1: Para mostrar aos seus clientes alguns dos produtos que 
vende, um comerciante reservou um espaço em uma vitrine para 
colocar exatamente 3 latas de refrigerante, lado a lado. Se ele vende 
6 tipos diferentes de refrigerante, de quantas maneiras distintas pode 
expô-los na vitrine?
A) 144
B) 132
C) 120
D) 72
E) 20
Solução. Seja R = {r
1
, r
2
, r
3
, r
4
, r
5
, r
6
 } o conjunto formado pelos 6 
refrigerantes dos quais o comerciante dispõe. Claramente, a resposta 
para o problema corresponde ao número de arranjos simples com 3 
elementos de R, isto é, 
 ( )= = =
−6, 3
6! 6!
A 120.
6 3 ! 3!
Alternativa: C
Exemplo 2: Ao utilizar o caixa eletrônico de um banco, o usuário 
digita sua senha numérica em uma tela, como mostra a figura. Os dez 
algarismos {0,1,2,3,4,5,6,7,8,9} são associados aleatoriamente a cinco 
botões, de modo que a cada botão corresponda a dois algarismos, 
indicados em ordem crescente. O número de maneiras diferentes de 
apresentar os dez algarismos na tela é:
1 ou 4
corrigir sair
5 ou 70 ou 3
senha:
2 ou 9 6 ou 8
A) 5
10!
2
B) 
10!
5
 
C) 25 × 5!
D) 25 × 10!
E) 
10!
2
Solução: Inicialmente, o sistema operacional do caixa eletrônico 
escolhe os dois algarismos que serão associados ao primeiro botão, 
o que pode ser feito de 10, 2A
2
 modos distintos. De fato, A
10,2
 contabiliza 
todas as listas ordenadas com dois elementos oriundos do conjunto 
{0,1,2,3,4,5,6,7,8,9}. Porém, como os dois algarismos escolhidos serão 
exibidos na tela em ordem crescente, A
10,2
 corresponde ao dobro do 
número correto de possíveis escolhas para o primeiro botão. Feita a 
primeira escolha, a máquina terá à sua disposição 8 algarismos, dos 
quais 2 serão escolhidos para o segundo botão, e, aqui, um raciocínio 
similar nos leva a concluir que o total de possíveis escolhas é 
8, 2A
.
2 
Procedendo dessa maneira, e aplicando o princípio multiplicativo, 
inferimos que a resposta procurada é
 × × × × =10, 2 8, 2 6, 2 4, 2 2, 2A A A A A
2 2 2 2 2
 = × × × × × =
5 5
1 10! 8! 6! 4! 2! 10!
.
2 8! 6! 4! 2! 0! 2
Alternativa: A
2F B O N L I N E . C O M . B R
//////////////////
Módulo de estudo
013.033 - 138677/19
Exemplo 3: (Professor Isaac Luís) 12 enxadristas participam de um 
torneio em que todos jogam contra todos. Cada participante do 
torneio inicia sua sequência de jogos com 11 pontos. Se um enxadrista 
ganha uma partida, somam-se 3 pontos àqueles que ele já possuía; 
se perde, subtrai-se um ponto; se empata um jogo, nem perde e nem 
ganha pontos. Foram registrados 14 empates nesse torneio. Qual é 
a soma de todos os pontos com os quais cada enxadrista ficou ao 
término do torneio?
Solução. Perceba que o número de partidas disputadas nesse torneio foi
 = × = × × =12, 2A 1 12! 1
12 11 66.
2 2 10! 2
Desse modo, houve 66 – 14 = 52 vitórias (e 52 derrotas, 
evidentemente). Em cada uma das partidas nas quais um jogador saiu 
vitorioso, foram agregados 3 – 1 = 2 pontos na pontuação geral do 
torneio (isto é, na soma dos pontos de todos os enxadristas). Assim, 
a resposta procurada é
12 × 11 + 52 × 2 = 132 + 104 = 236
Exemplo 4: Em uma primeira fase de um campeonato de xadrez, 
cada jogador joga uma vez contra todos os demais. Nessa fase, foram 
realizados 78 jogos. Quantos eram os jogadores?
A) 10
B) 11
C) 12
D) 13
E) 14
Solução. Seja n ≥ 2 o número de jogadores do torneio. É claro que 
n, 2A
2
 corresponde ao número de partidas disputadas nesse torneio, 
de modo que
 ( ) ( )= ⇒ = ⇒ − = ⇒
−
n, 2A n!
78 156 n n 1 156
2 n 2 !
 ⇒ − − =2n n 156 0.
Resolvendo a equação quadrática anterior, obtemos n = 13, 
posto que n ≥ 2.
Alternativa: D
Combinações Simples
Definição: Seja A um conjunto com n elementos. Uma combinação 
simples de classe P com os elementos de A é qualquer subconjunto 
de A com 0 ≤ p ≤ n elementos.
Se A = {1,2,3}, por exemplo, as combinações simples de classe 2 com 
os elementos de A são os subconjuntos de A com dois elementos:
{1,2}; {1,3}; {2,3}.
Proposição: O número de combinações simples de n elementos, 
tomados P a P, denotado por C
n,p
, é dado por
 ( )−
n!
.
p! n p !
Prova: Seja A um conjunto com n elementos. Se P = 0, o único 
subconjunto de A com nenhum elemento é o vazio, e, nesse caso, a 
fórmula acima funciona, posto que 
 = =n, 0
n!
C 1.
0!n!
Suponha p ≠ 0. Consideremos todos os arranjos simples 
com p elementos de A. Note que C
n,p
 corresponde ao número de 
grupos desses arranjos constituídos pelos mesmos p elementos. 
Com efeito, cada grupo de arranjos formados pelos mesmos p 
elementos está associado a um único subconjunto de A com p 
elementos, e, reciprocamente, cada subconjunto de A com p elementos 
está associado a um único grupo de arranjos formados pelos mesmos 
p elementos. Agora, note que A
n,p
 corresponde à soma dos números 
de permutações dos p elementos de cada um dos grupos de arranjos 
mencionados anteriormente, isto é,
 ( )× = = ⇒
−n, p n, p
n!
p! C A
n p !
 ( )⇒ =
−n, p
n!
C ,
p! n p !
o que encerra a prova.
Exemplo 5: Considere o conjunto
C = {2, 8, 18, 20, 53, 124, 157, 224, 286, 345, 419, 527}.
O número de subconjuntos de três elementos de C que possuem a 
propriedade “soma dos três elementos é um número ímpar” é:
A) 94
B) 108
C) 115
D) 132
E) 146
Solução. Repare que, para montarmos um subconjunto de C com três 
elementos satisfazendo a exigência anterior, ao menos um dos números 
escolhidos deve ser ímpar. Em verdade, devemos escolher um ímpar e 
dois pares ou três ímpares. Como há 5 ímpares e 7 números pares em 
C, o total de subconjuntos de C formados por um ímpar e dois pares é
 ×
× = × = × =7, 2
7! 7 6
5 C 5 5 105.
2!5! 2
Por outro lado, o número de subconjuntos de C formados por 
três ímpares é
 
×
= = =5, 3
5! 5 4
C 10.
3!2! 2
Para o que falta, fazemos 10 + 105 = 115. 
Alternativa: C
Exemplo 6: Em um escritório, onde trabalham 6 mulheres e 8 homens, 
pretende-se formar uma equipe de trabalho com 4 pessoas, com a 
presença de pelo menos uma mulher. O número de formas distintas 
de se compor essa equipe é:
A) 721
B) 1111
C) 841
D) 931
E) 1001
Solução. Consideremos o conjunto E formado por todas as pessoas 
que trabalham no escritório. É claro que n(E) = 6 + 8 =1 4. O número 
total de equipes com 4 integrantes que podemos formar com os 
elementos de E é dado por C
14,4
. Essa contagem, evidentemente, 
inclui as equipes formadas apenas por homens, que são em número 
de C
8,4
 (aqui, estamos contando os subconjuntos com 4 elementos 
do conjunto de homens que trabalham no escritório). Daí, a resposta 
procurada é
3 F B O N L I N E . C O M . B R
//////////////////
013.033 - 138677/19
Módulo de estudo
 
− = − =14, 4 8, 4
14! 8!
C C
4!10! 4!4!
 
× × × × × ×
= − = × × − × × =
× × × ×
14 13 12 11 8 7 6 5
7 13 11 7 2 5
4 3 2 4 3 2
 
( )= × × − × = × =7 13 11 2 5 7 133 931.
Alternativa: D
Exemplo 7: Marcam-se,em um plano, 10 pontos, dos quais 4 estão sobre 
a mesma reta e três outros pontos quaisquer nunca estão alinhados. 
O número total de triângulos que podem ser formados, unindo-se três 
quaisquer desses pontos, é:
A) 24
B) 112
C) 116
D) 120
E) 124
Solução. Seja P o conjunto formado pelos 10 pontos em questão. 
O número de triângulos com vértices em pontos de P corresponde 
ao número de subconjuntos de P da forma {A, B, C}, com A, B e C 
não colineares. O total de subconjuntos de P com três elementos é 
dado por C
10,2
. Porém, devemos excluir desse número a quantidade 
de subconjuntos de P cujos elementos são três dos quatro pontos 
que se encontram sobre a mesma reta. Logo, a resposta procurada é
 − = − =10, 3 4, 3
10!
C C 4
3!7!
 
× ×
= − = × × − = − =
×
10 9 8
4 10 3 4 4 120 4 116.
3 2
Alternativa: C
Proposição: Os números C
n,p
 e C
n,q
 são iguais se, e somente se, 
p = q ou p + q = n.
Prova: (⇐) É claro que, se p = q, C
n,p
 = C
n,p
. Além disso, se p + q = 
n, temos q = n – p. Daí, segue-se que
 ( ) ( )−= = =
 − − − 
n, q n, n p
n!
C C
n p ! n n p !
 ( )= =
− n, p
n!
C .
n p !n!
⇒ Suponha C
n,p
 = C
n,q
. Se p = q, nada há a fazer. Suponha, sem perda 
de generalidade, p > q. Temos
 ( ) ( ) ( ) ( ) ( )= ⇒ − = −
− −
n! n!
p! n p ! q! n q ! * .
p! n p ! q! n q !
Seja ( )
−
=
= − +∏
p q
i 1
M n p i . Multiplicando ambos os membros de 
(*) por M, obtemos 
p![(n – p)!M] = q!(n – q)!M ⇒ p! = q!M,
uma vez que (n – p)!M = (n – q)!. Agora, note que a igualdade obtida 
anteriormente nos permite concluir que
 
( )
−
=
+ =∏
p q
i 1
q i M,
posto que p > q. Suponha que n – p + 1 > q + 1. Nesse caso, teríamos 
n – p + j > q + j, para todo j, 1 ≤ j ≤ p – q, e, portanto,
 ( )
−
=
> +∏
p q
i 1
M q i ,
o que não é possível. Se n – p + 1nesses 
casos. Suponha n ≥ 2. É claro que p∑
m
p 2, p
p 0
C .
B) Quantas são as soluções inteiras e não negativas da inequação 
x + y + z ≤ 10?
13. Com os elementos 1,2,…,10 são formados todas as sequências 
(a
1
, a
2
,…,a
7
). Escolhendo aleatoriamente uma dessas sequências, 
a probabilidade de a sequência escolhida não conter elementos 
repetidos é:
A) 
×7
7!
10 3!
 B) 
×7
10!
10 3!
C) 
×7
3!
10 7!
 D) 
×3
10!
10 7!
E) 
7
10!
10
14. (Professor Isaac Luís) O conjunto A é tal que n(A) ≥ 2. Seleciona-se 
um subconjunto X de A com k elementos. Em seguida, calcula-se 
o número t de subconjuntos Y de A tais que X ⊄ Y. Sabe-se que 
t é uma potência de 2. Determine o valor de k.
A) 1
B) 2
C) 3
D) 4
E) As informações fornecidas são insuficientes para a determinação 
do valor de k.
15. (Professor Isaac Luís) Seja n um número natural maior do que ou 
igual a 3. Considere todos os subconjuntos S com k elementos 
do conjunto {1,2,3,…,n}, 2 ≤ k ≤ n – 1. Encontre, em função de 
n, uma fórmula para a soma das somas dos elementos de cada 
um dos subconjuntos S anteriormente descritos.
Gabarito
01 02 03 04 05
D * A C B
06 07 08 09 10
* A C * *
11 12 13 14 15
* * B A *
* 02: 64.
 06: 14480.
 09: 10.
 10: 36
 11: 70560.
 12: A) C
m+3,m
. B) 286.
 15: n(n + 1) (2n–2 –1).
SUPERVISOR/DIRETOR: MARCELO PENA – AUTOR: ISAAC LUÍS
André – REV.: KELLY MOURA