2021_1_Matemática Discreta_APX2_resolucoes

Prévia do material em texto

Matemática Discreta – APX2 – 2021/1
Resoluções
1. (2,5) Quantos quadriláteros podem ser formados com vértices tomados dentre os
dezoito pontos dados como na figura abaixo?
•
•
•
• • • •
•
•
•
•
• • • •
•
•
•
Lembre-se, um quadrilátero é formado por quatro pontos no plano, de modo que não
haja três pontos em uma mesma reta.
Resolução da Questão 1:
Objetos básicos: Dezoito pontos dispostos no plano, como na figura.
Configurações: Quadriláteros formados com vértices escolhidos dentre estes 18
pontos.
Seja X o conjunto de todas as configurações.
Considere os seguintes conjuntos:
Y : dos conjuntos de 4 dos 18 pontos,
A : dos conjuntos de 4 pontos em uma mesma reta,
B : dos conjuntos de 3 pontos em uma mesma reta e um fora dela.
Temos que X, A e B formam uma partição de Y . Assim, pelo PA, |Y | = |X| +
|A| + |B|. Como queremos |X|, ao determinamos |Y |, |A| e |B|, o problema estará
resolvido.
Calculando |Y |: Temos que |Y | = C(18, 4).
Calculando |A|: Para formarmos um elemento de A, podemos fazer duas escolhas:
e1 : escolher uma das duas retas,
e2 : escolher quatro pontos na reta escolhida.
Temos que:
#e1 = 2,
#e2 = C(4, 4) = 1.
1
Logo, pelo PM, |A| = 2× 1 = 2.
Calculando |B|: Para formarmos um elemento de B, podemos fazer três escolhas:
e1 : escolher uma das duas retas,
e2 : escolher três pontos na reta escolhida em e1,
e3 : escolher um ponto que não pertence a reta escolhida em e1.
Temos que:
#e1 = 2,
#e2 = C(4, 3),
#e3 = 18− 4 = 14.
Logo, pelo PM, |B| = 2× 4× 14.
Calculando |X|: Logo, pelo PA, |X| = C(18, 4)− 2− (2× 4× 14).
2. (2,5) Os algarismos significativos são 1, 2, 3, 4, 5, 6, 7, 8 e 9.
Quantos números de sete algarismos significativos podem ser formados, de modo
que cada número possui no máximo dois algarismos repetidos no máximo duas vezes
cada?
Resolução da Questão 2:
Objetos básicos: Os 9 algarismos significativos.
(a) Configurações: Números de sete algarismos significativos que possuem no
máximo dois algarismos repetidos no máximo duas vezes cada.
Seja X o conjunto de todas as configurações.
Considere os seguintes subconjuntos de X:
X1 : dos números em X que não possuem algarismos repetidos,
X2 : dos números em X que possuem exatamente um algarismo repetido,
X3 : dos números em X que possuem exatamente dois algarismos repeti-
dos.
Temos que X1, X2 e X3 são uma partição de X. Assim, pelo PA, |X| = |X1| +
|X2| + |X3|. Como queremos |X|, ao determinamos |X1|, |X2| e |X3|, o problema
estará resolvido.
Calculando |X1|: Para formarmos um elemento de X1, podemos fazer duas escolhas:
e1 : escolher sete algarismos para formar o número,
e2 : escolher uma permutação simples dos algarismos escolhidos em e1,
para ser o número.
Temos que:
#e1 = C(9, 7),
#e2 = 7!.
Logo, pelo PM, |X1| = C(9, 7)× 7! = C(9, 2)× 7!.
Calculando |X2|: Para formarmos um elemento de X2, podemos fazer três escolhas:
2
e1 : escolher um algarismo, digamos a, que será repetido,
e2 : escolher cinco algarismos diferentes de a para formar o número jun-
tamente com a,
e3 : escolher uma permutação completa de duas ocorrências de a e dos
algarismos escolhidos em e2, para ser o número.
Temos que:
#e1 = 9,
#e2 = C(8, 5),
#e3 =
7!
2!
,
Logo, pelo PM, |X2| = 9× C(8, 5)×
7!
2!
.
Calculando |X3|: Para formarmos um elemento de X3, podemos fazer três escolhas:
e1 : escolher dois algarismos, digamos a e b, que serão repetidos,
e2 : escolher três algarismos diferentes de a e de b para formar o número
juntamente com a e b,
e3 : escolher uma permutação completa de duas ocorrências de a, duas
ocorrência de b e dos algarismos escolhidos em e2, para ser o número.
Temos que:
#e1 = C(9, 2),
#e2 = C(7, 3),
#e3 =
7!
2!× 2!
,
Logo, pelo PM, |X3| = C(9, 2)× C(7, 3)×
7!
2!× 2!
.
Pelo PA, |X| = [C(9, 2)× 7!] +
[
9× C(8, 3)× 7!
2!
]
+
[
C(9, 2)× C(7, 3)× 7!
2!× 2!
]
.
|X| =
[
9× 8
2!
× 7!
]
+
[
9× 8× 7× 7!
2!
]
+
[
9× 4× 7× 5× 7!
2!× 2!
]
= 9× 7! (4 + 4×
7 + 7× 5).
3. (2,5) Um sargento ordenou que cinco soldados formassem uma fila, chamada fila
inicial. Quantas permutações destes cinco soldados existem, de modo que em cada
permutação cada soldado não tenha na sua frente o soldado que estava na sua frente
na fila inicial?
Resolução da Questão 3:
Objetos básicos: Cinco soldados.
Configurações: Permutações dos cinco soldados, de modo que em cada permutação
cada soldado não tenha na sua frente o soldado que estada na sua frente na fila inicial.
Seja s1s2s3s4s5 a fila inicial.
Seja X o conjunto de todas as configurações.
Considere os seguintes conjuntos:
3
Y : de todas as permutações dos cinco soldados,
Z12 : de todos os elementos de Y nos quais o soldado s2 ocorre imediata-
mente atrás do soldado s1,
Z23 : de todos os elementos de Y nos quais o soldado s3 ocorre imediata-
mente atrás do soldado s2,
Z34 : de todos os elementos de Y nos quais o soldado s4 ocorre imediata-
mente atrás do soldado s3,
Z45 : de todos os elementos de Y nos quais o soldado s5 ocorre imediata-
mente atrás do soldado s4.
Temos que X e Z12 ∪ Z23 ∪ Z34 ∪ Z45 formam uma partição de Y . Logo, pelo PA,
|Y | = |X|+ |Z12 ∪ Z23 ∪ Z34 ∪ Z45|.
Queremos determinar |X|. Para isto, vamos determinar |Y | e |Z12∪Z23∪Z34∪Z45|.
Determinando |Y |: Cada elemento de Y é uma permutação dos cinco soldados.
Logo, |Y | = 5!.
Determinando |Z12 ∪ Z23 ∪ Z34 ∪ Z45|: Pelo PIE, |Z12 ∪ Z23 ∪ Z34 ∪ Z45| = |Z12| +
|Z23| + |Z34| + |Z45| − |Z12 ∩ Z23| − |Z12 ∩ Z34| − |Z12 ∩ Z45| − |Z23 ∩ Z34| − |Z23 ∩
Z45| − |Z34 ∩Z45|+ |Z12 ∩Z23 ∩Z34|+ |Z12 ∩Z23 ∩Z45|+ |Z12 ∩Z34 ∩Z45|+ |Z23 ∩
Z34 ∩ Z45| − |Z12 ∩ Z23 ∩ Z34 ∩ Z45|.
Determinando |Z12|: Cada elemento de Z12 é uma permutação dos 4 objetos s1s2
(vistos como um único objeto), s3, s4 e s5.
Logo, |Z12| = 4!.
Determinando |Z23|, |Z34| e |Z45|: Observe que existe uma bijeção entre X12 e qual-
quer um dos conjuntos Z23, Z34 ou Z45.
Logo, |Z23| = |Z34| = |Z45| = |Z12| = 4!
Determinando |Z12 ∩ Z23|: Cada elemento de Z12 ∩ Z23 é uma permutação dos 3
objetos s1s2s3 (vistos como um único objeto), s4 e s5.
Logo, |Z12 ∩ Z23| = 3!.
Determinando |Z12 ∩ Z34|: Cada elemento de Z12 ∩ Z34 é uma permutação dos 3
objetos s1s2 (vistos como um único objeto), s3s4 (vistos como um único objeto) e
s5.
Logo, |Z12 ∩ Z34| = 3!.
Determinando |Z23∩Z34| e |Z34∩Z45|: Observe que existe uma bijeção entre Z12∩Z23
e qualquer um dos conjuntos Z23 ∩ Z34 ou Z34 ∩ Z45.
Logo, |Z23 ∩ Z34| = |Z34 ∩ Z45| = |Z12 ∩ Z23| = 3!.
Determinando |Z12∩Z45| e |Z23∩Z45|: Observe que existe uma bijeção entre Z12∩Z34
e qualquer um dos conjuntos Z12 ∩ Z45 ou Z23 ∩ Z45.
Logo, |Z12 ∩ Z45| = |Z23 ∩ Z45| = |Z12 ∩ Z34| = 3!.
Determinando |Z12∩Z23∩Z34|: Cada elemento de Z12∩Z23∩Z34 é uma permutação
dos 2 objetos s1s2s3s4 (vistos como um único objeto) e s5.
Logo, |Z12 ∩ Z23 ∩ Z34| = 2!.
Determinando |Z12∩Z23∩Z45|: Cada elemento de Z12∩Z23∩Z45 é uma permutação
dos 2 objetos s1s2s3 (vistos como um único objeto) e s4s5 (vistos como um único
objeto).
Logo, |Z12 ∩ Z23 ∩ Z45| = 2!.
4
Determinando |Z12∩Z34∩Z45|: Cada elemento de Z12∩Z34∩Z45 é uma permutação
dos 2 objetos s1s2 (vistos como um único objeto) e s3s4s5 (vistos como um único
objeto).
Logo, |Z12 ∩ Z34 ∩ Z45| = 2!.
Determinando |Z23∩Z34∩Z45|: Cada elemento de Z23∩Z34∩Z45 é uma permutação
dos 2 objetos s2s3s4s5 (vistos como um único objeto) e s1.
Logo, |Z23 ∩ Z34 ∩ Z45| = 2!.
Determinando |Z12 ∩ Z23 ∩ Z34 ∩ Z45|: O único elemento de Z12 ∩ Z23 ∩ Z34 ∩ Z45 é
a permutação 12345.
Logo, |Z12 ∩ Z23 ∩ Z34 ∩ Z45| = 1.
Determinando |Z12 ∪Z23 ∪Z34 ∪Z45|: Pelo PIE, |Z12 ∪Z23 ∪Z34 ∪Z45| = [4× 4!]−
[6× 3!] + [4× 2!]− 1.
Assim, |X| = 5!− ([4× 4!]− [6× 3!] + [4× 2!]− 1) = 4! + [6× 3!]− [4× 2!] + 1.
|X| = (4 + 6)× 3!− 4× 2!] + 1 = 60− 8 + 1 = 53.
4. (2,5) De quantas maneiras podemos pintar dez bolas iguais se dispomos de cinco
cores diferentes?
(a) Se todas as cores são usadas.
(b) Se algumas cores podem não ser usadas?
Resolução da Questão4:
Objetos básicos: As cinco cores diferentes.
Seja xi o número de bolas coloridas com a i-ésima cor.
(a) Configurações: As bolas pintadas com as cinco cores, de modo que todas as
cores são usadas.
Cada maneira de pintarmos as bolas corresponde a uma solução da equação:
x1 + x2 + x3 + x4 + x5 = 10
em número naturais não nulos.
Logo, o número total de maneiras é C(10− 1, 5− 1) = C(9, 4) = 9×8×7×64! = 126.
(b) Configurações: As bolas pintadas com as cinco cores, de modo que algumas
cores podem não ser usadas.
Cada maneira de pintarmos as bolas corresponde a uma solução da equação:
x1 + x2 + x3 + x4 + x5 = 10
em número naturais, sendo que alguns deles podem ser nulos.
Assim, cada maneira de pintarmos as bolas corresponde a uma solução da equação:
(x1 − 1) + (x2 − 1) + (x3 − 1) + (x4 − 1) + (x5 − 1) = 10
em número naturais não nulos, ou seja, a uma solução da equação:
x1 + x2 + x3 + x4 + x5 = 15.
Logo, o número total de maneiras é C(15−1, 5−1) = C(14, 4) = 14×13×12×114! = 1001.
c© 2021 Márcia Cerioli e Petrucio Viana
Coordenação da Disciplina MD/CEDERJ-UAB
5