AP2-MD-2013-2-gabarito

Prévia do material em texto

Matemática Discreta – AP2 – 2013/2
Resoluções
1. Considere um grupo de 15 pessoas, dentre elas dois alunos, a1 e a2, do CEDERJ.
De quantas maneiras podemos escolher 10 pessoas neste grupo, de modo que:
(a) (1,0) os alunos do CEDERJ não fazem parte do grupo?
(b) (2,0) exatamente um aluno do CEDERJ faz parte do grupo?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 1:
(a) Para formar um grupo nestas condições, podemos fazer 1 escolha:
e1 : escolher 10 pessoas diferentes de a1 e a2 para formar o grupo
Como no total temos 15 pessoas, mas os 2 alunos do CEDERJ não podem ser
escolhidos, temos que:
#e1 = C(13, 10)
Assim, o número procurado é C(13, 10) = C(13, 3) =
13× 12× 11
3× 2× 1
= 13× 2× 11 =
286.
(b) Considere o conjunto X de todos os grupos que podem ser formados.
Para formar um elemento de X, podemos fazer 2 escolhas:
e1 : escolher a1 ou a2 (ou exclusivo) para fazer parte do grupo
e2 : escolher 9 pessoas diferentes da pessoa já escolhida, para
completar o grupo
Temos que:
#e1 = 2
#e2 = C(13, 9)
Assim, pelo PM, |X| = 2 × C(13, 9) = 2 × C(13, 4) = 2 × 13× 12× 11× 10
4× 3× 2× 1
=
13× 11× 10 = 1.430.
1
2. Quantas palavras podem ser formadas com as letras
U,U, U, U, V, V, V,W,W,X,X
(a) (1,0) no total?
(b) (2,0) se as palavras não têm ocorrências de W e as letras X ocorrem separadas?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 2:
(a) Cada palavra corresponde a uma permutação de 11 letras, sendo 4 letras U , 3
letras V , 2 letras W e 2 letras X. Assim, pelo cálculo do número de permutações
completas, temos que o número procurado é:
P (11, 4, 3, 2, 2) =
11!
4!× 3!× 2!× 2!
=
11× 10× 9× 8× 7× 6× 5
3!× 2× 2
= 11× 10× 9× 2× 7× 5
= 69.300
(b) Como as palavras não possuem ocorrências de W , cada palavra corresponde a
uma permutação de 4 letras U , 3 letras V e 2 letras X, sendo que as 2 letras X
ocorrem separadas.
Considere os seguintes conjuntos:
T : das palavras de 4 letras U , 3 letras V , e 2 letras X
J : das palavras em T nas quais as letras X ocorrem juntas
S : das palavras em T nas quais as letras X ocorrem separadas
Queremos determinar |S|. Como J e S são uma partição de T , pelo PA, |T | =
|J |+ |S|. Assim, se determinamos |T | e |J |, o problema está resolvido.
Determinando |T |: Cada palavra em T corresponde a uma permutação de 9 letras,
sendo 4 letras U , 3 letras V e 2 letras X.
Assim, pelo cálculo do número de permutações completas, temos que:
|T | = P (9, 4, 3, 2) = 9!
4!× 3!× 2!
=
9× 8× 7× 6× 5
3!× 2
= 9× 4× 7× 5
Determinando |J |: Considerando as duas ocorrências juntas de X como uma única
letra, cada palavra em J corresponde a uma permutação de 8 letras, sendo 4 letras
U , 3 letras V e uma letra XX (aqui usamos o PB).
Assim, pelo cálculo do número de permutações completas, temos que:
|J | = P (8, 4, 3, 1) = 8!
4!× 3!× 1!
=
8× 7× 6× 5
3!
= 8× 7× 5
Determinando |S|: Pelo PA, temos que |S| = |T | − |J | = 9× 4× 7× 5− 8× 7× 5 =
7× 5(9× 4− 8) = 35× 28 = 980.
2
(b) Resolução alternativa. Cada palavra corresponde a um anagrama da palavra
UUUUV V V XX, onde os X’s ocorrem separados.
Para formar um tal anagrama, podemos executar as seguintes tarefas:
t1 : formar um anagrama das letras UUUUV V V
t2 : escolher dentre as 8 posições determinadas pelas 7 letras
do anagrama já escolhido, duas para colocar 2 os X’s
Observe que um anagrama de 7 letras, digamos a1a2a3a4a5a6a7, determina 8 posi-
ções:
−a1 − a2 − a3 − a4 − a5 − a6 − a7−
Temos que:
#t1 = P (7, 4, 3) =
7!
4!× 3!
=
7× 6× 5
3!
= 7× 5 = 35
#t2 = C(8, 2) =
8× 7
2× 1
= 4× 7 = 28
Assim, pelo PM, existem 35× 28 = 980 tais palavras.
3
3. Em parque há uma roda gigante (circular) que tem 10 bancos, cada um com dois
lugares, sendo que os lugares de cada banco são pintados com as cores azul e ver-
melho, respectivamente. 10 casais foram ao parque conhecer a roda gigante, sendo
que cada casal levou um filho consigo. De quantas maneiras:
(a) (1,0) os filhos podem se sentar na roda gigante (os pais não estão na roda gigante)
ocupando os lugares azuis?
(b) (1,0) os filhos podem se sentar na roda gigante (os pais não estão na roda
gigante), exatamente um em cada banco, ocupando qualquer lugar?
(c) (1,0) os casais podem se sentar na roda gigante (os filhos não estão na roda
gigante), sem que necessariamente cada marido sente ao lado da sua esposa, de
modo que as mulheres estejam sentadas nos lugares pintados de azul.
(d) (1,0) os casais podem se sentar na roda gigante (os filhos não estão na roda
gigante), cada esposa e seu marido no mesmo banco, ocupando qualquer lugar?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 3:
(a) Cada tal maneira de sentar os filhos na roda gigante corresponde a uma per-
mutação circular dos 10 filhos. Assim, pelo cálculo do número de permutações
circulares, temos que o número procurado é:
PC(10) = 9! = 36.2880.
(b) Para sentar os filhos na roda gigante desta maneira, podemos tomar as seguintes
decisões:
d1 : escolher uma permutação circular dos 10 filhos
para ocupar os 10 bancos da roda gigante
di : escolher o lugar (azul ou vermelho) que o filho i− 1 vai
ocupar na roda gigante
onde 2 ≤ i ≤ 11.
Temos que:
#d1 = 9!
#di = 2
onde 2 ≤ i ≤ 11.
Assim, pelo PM, existem 9! × 2× 2× · · · × 2︸ ︷︷ ︸
10 fatores
= 362.880 × 1.024 = 371.589.120 tais
maneiras.
(c) Para sentar os casais na roda gigante desta maneira, podemos tomar as seguintes
decisões:
d1 : escolher uma permutação circular das 10 mulheres
e sentá-las nos lugares azuis
d2 : escolher uma permutação circular dos 10 homens
e sentá-los nos lugares vermelhos
4
Temos que:
#d1 = 9!
#d2 = 9!
Assim, pelo PM, existem 9!×9! = 362.880×362.880 = 131.681.894.400 tais maneiras.
(d) Para sentar os casais na roda gigante desta maneira, podemos tomar as seguintes
decisões:
d1 : escolher uma permutação circular das 10 mulheres
para ocupar os 10 bancos da roda gigante
di : escolher o lugar (azul ou vermelho) que a mulher i− 1 vai
ocupar na roda gigante
d12 : colocar cada marido do lado da sua esposa, no assento
desocupado
onde 2 ≤ i ≤ 11.
Temos que:
#d1 = 9!
#di = 2
#d12 = 1
onde 2 ≤ i ≤ 11.
Assim, pelo PM, existem 9! × 2× 2× · · · × 2︸ ︷︷ ︸
10 fatores
×1 = 362.880 × 1.024 = 371.589.120
tais maneiras.
c© 2013 Márcia Cerioli e Petrucio Viana
Coordenação da Disciplina MD/CEDERJ-UAB
5