1ª Lista Soluções

Prévia do material em texto

Soluc¸oes da Lista adicional 01 - Combinato´ria e Conjuntos
COMBINATO´RIA
1. Para formar um subconjunto, deve-se decidir, para cada elemento do conjunto, se ele
pertencera´ ou na˜o ao subconjunto. Ha´ 2 modos de decidir o que fazer com o primeiro
elemento do conjunto, 2 modos com o segundo, etc. Logo a resposta e´ 2×2×2... = 2n.
2. Devemos decidir quantos exemplares de cada revista devem ser postos na colec¸a˜o. Ha´
6 possibilidades para a revista A (0, 1, 2, 3, 4 ou 5 exemplares), 7 para a revista B e
11 para a revista C. A nu´mero de colec¸o˜es e´ 6× 7× 11 = 462, e o nu´mero de colec¸o˜es
na˜o vazias e´ 462− 1 = 461.
3. O nu´mero de modos de acomodar os passageiros que pretendem sentar de frente e´
5 × 4 × 3 × 2 = 120; o nu´mero de modos de acomodar os passageiros que pretendem
sentar de costas e´ 5×4×3 = 60; o nu´mero de modos de acomodar os demais passageiros
e´ 3× 2× 1 = 6. A resposta e´ 120× 60× 6 = 43.200.
4. Ha´ duas palavras de uma letra (ponto ou trac¸o), 2 × 2 = 4 palavras de duas letras,
2 × 2 × 2 = 8 palavras de tres letras e 2 × 2 × 2 × 2 = 16 palavras de 4 letras. Total
de palavras e´ 2 + 4 + 8 + 16 = 30.
5. Os senadores de Sa˜o Paulo sa˜o A, B e C e Sa˜o Paulo pode ser representado de 6 modos
diferentes (A, B, C, AB, AC ou BC); analogamente o Acre pode ser representado de
6 modos, Bahia, etc. A resposta e´ 6× 6× 6... = 627.
Permutac¸a˜o simples (Pn)
6. Cada anagrama de PRA´TICA nada mais e´ do que uma ordenac¸a˜o das letras P, R, A,
T, I, C, O. Assim o nu´mero de anagramas e´ P7 = 7! = 5040. A consoante inicial pode
ser escolhida de 4 maneiras, a final de 3 maneiras e as 5 letras restantes podem ser
arrumadas entre essas duas consoantes de P5 = 5! modos. Resposta e´ 4×3×5! = 1440.
7. O primeiro homem pode escolher seu lugar de 10 modos, o segundo de 8 modos, o
terceiro de 6 modos, o quarto de 4 modos e o quinto de 2 modos. Colocando os
homens, temos que colocar as 5 mulheres nos 5 lugares restantes, o que pode ser feito
de 5! modos. A resposta e´ 10× 8× 6× 4× 2× 5! = 460.800
1
8. O nu´mero total de arrumar 7 pessoas em 7 cadeiras e´ o nu´mero de modos de arrumar
7 pessoas em fila, P7 = 7! O nu´mero de modos de arrumar 7 pessoas em fila de modo
que duas pessoas, A e B fiquem juntas e´ 2 × 6!, pois, para formar tal fila, devemos
inicialmente decidir em que ordem se colocara˜o A e B (AB ou BA), e, em seguida,
formar uma fila de 6 objetos: o bloco das pessoas A e B e as demais 5 pessoas. A
resposta e´ 7!− (2× 6!) = 3.600 modos de que duas pessoas na˜o sentem juntas.
9. Devemos inicialmente escolher a ordem das mate´rias, o que pode ser feito de 3×2×1 = 6
modos. Depois, devemos, em cada mate´ria, escolher a ordem em que se apresentara˜o
os livros, 5!× 3!× 2!. Resposta e´ 3!× 5!× 3!× 2! = 8.640
Combinac¸a˜o Simples (Cpn)
10 . A primeira fruta pode ser escolhida de 10 modos, a segunda de 9 modos a terceira de 8
modos e a quarta de 7 modos. Temos enta˜o 10×9×8×7 = 5.040. Pore´m, dessa maneira
estamos contando as escolhas ABCD, ABDC, BCDA, DCAB,... como diferentes,
quando na verdade e´ a mesma. Cada escolha contamos 4! = 24 vezes (as maneiras de
ordenar os sabores A, B, C e D). Logo a resposta e´ C410 =
10×9×8×7
4!
= 5.040
24
= 210
modos. No caso geral Cpn =
n(n−1)···(n−p+1)
p!
= n(n−1)···(n−p+1)
p!
(n−p)!
(n−p)! =
n!
p!(n−p)! , 0 ≤ p ≤ n.
11. As alternativas sa˜o:
4 homens e 2 mulheres
3 homens e 3 mulheres
2 homens e 4 mulheres
A resposta e´: C47 × C24 + C37 × C34 + C27 × C44 = 35× 6 + 35× 4 + 21× 1 = 371
Ou
poder´ıamos tambe´m contar todas as escolhas de 6 pessoas (C611) e abater as escolhas
sem mulheres (C67) e com apenas uma mulher (C
5
7 ×C14). Logo a resposta e´ C611−C67 −
C57 × C14 = 462− 7− 4× 21 = 371.
12. O primeiro grupo pode ser escolhido de C48 modos. Escolhido o 1
o grupo, sobram 4
pessoas e so´ ha´ 1 modo de formar o segundo grupo. Entretanto, contamos cada divisa˜o
2 vezes. Por exemplo, {a, b, c, d} {e, f, g, h} e´ ideˆntica a {e, f, g, h} {a, b, c, d} e foi
contada como se fossem diferentes. A resposta e´
C48×1
2
= 35.
Ou
2
A divisa˜o pode ser feita colocando 8 pessoas em fila e dividindo-as de modo que um dos
grupos seja formado pelas 4 primeiras pessoas e o outro pelas 4 u´ltimas. Existem 8!
modos de se colocar as pessoas em fila. Entretanto, consideremos a divisa˜o abcd|efgh.
Ela e´ ideˆntica a` divisa˜o efgh|abcd e na contagem de 8! foi contada como se fossem
distintas. Ale´m disso, diviso˜es como abcd|efgh e cadb|efgh, que diferem pela ordem dos
elementos em cada grupo, apesar de ideˆnticas foram contadas como se fossem distintas.
Cada divisa˜o foi contada 2 × 4! × 4! vezes (2 por causa da ordem dos grupos, 4! por
causa da ordem dos elementos no 1o grupo e 4! por causa da ordem dos elementos no
2o grupo). Portanto o nu´mero de diviso˜es poss´ıveis e´ 8!
2×4!×4! = 35.
13. Com n participantes, sa˜o jogadas C2n =
n(n−1)
2
partidas. Portanto, n(n−1)
2
= 780, ou
seja, n(n − 1) = 1560. Como n e´ inteiro e positivo, resolvendo a equac¸a˜o do segundo
grau obtemos n = 40.
Permutac¸a˜o Circular (PC)n
14. A` primeira vista parece que formar uma roda com cinco crianc¸as basta escolher uma
ordem para elas, o que poderia ser feito de P5 = 5! = 120 modos. Entretanto, as rodas
ABCDE e EABCD sa˜o iguais, pois na roda o que importa e´ a posic¸a˜o relativa das
crianc¸as entre si e a roda ABCDE pode ser “virada” na roda EABCD. Como cada
roda pode ser “virada” de cinco modos, a nossa contagem de 120 rodas contou cada
roda 5 vezes. Portanto a resposta e´ 210/5 = 24. De modo geral, (PC)n = Pn−1 =
(n− 1)!.
15. Sejam A e B as crianc¸as que na˜o podem sentar juntas. Podemos formar (PC)5 = 4!
rodas com as cinco outras crianc¸as. Ha´ agora 5 modos de colocar A na roda. Ha´ agora
4 modos de colocar B na roda sem coloca´-la junto de A. A resposta e´ 4!×5×4 = 480.
16. Podemos formar uma roda com os homens de (PC)6 = 5! modos. Depois, devemos
escolher um dos 6 espac¸os entre os homens (o que pode ser feito de 6 modos) para
a´ı colocarmos todas as mulheres. Finalmente, devemos decidir em que ordem as 5
mulheres se colocara˜o nesse espac¸o (5! modos). A resposta e´ 5!×6×5! = 120×6×120 =
86.400.
17. Ha´ (PC)5 = 4! modos de formar uma roda com as meninas. Depois disso, os 5 meninos
restantes devem ser postos nos 5 lugares entre as meninas, o que pode ser feito de 5!
modos. A resposta e´ 4!× 5! = 24× 120 = 2.880.
Permutac¸o˜es de elementos nem todos distintos (Pα,β,...,λn )
3
18. Para formar um anagrama de “CARAGUATATUBA” temos que arrumar 5A, 2T , 2U ,
1C, 1R, 1G e 1T em 13 lugares. O nu´mero de modos de escolher os lugares onde sera˜o
colocados os A e´ C513. Depois disso temos C
2
8 modos de escolher os lugares para colocar
os T . Depois C26 modos de escolher os lugares para colocar os U . Depois C
1
4 modos de
escolher o lugar para colocar o C. Depois C13 modos de escolher o lugar para colocar
o R. Depois C12 modos de escolher o lugar para colocar o G e, finalmente um u´nico
modo de escolher o lugar para o T . Logo, P 5,2,2,1,1,1,113 = C
5
13×C28 ×C26 ×4×3×2×1 =
1.287× 28× 15× 4× 3× 2× 1 = 12.972.960.
ou
Se as letras fosse diferentes obter´ıamos 13! anagramas. Como os A sa˜o iguais, contamos
cada anagrama 5! vezes. Analogamente contamos cada anagrama 2! vezes por serem
iguais os T e 2! vezes por serem iguais os U . Logo, P 5,2,2,1,1,1,113 =
13!
5!2!2!
= 12.972.960.
Combinac¸o˜es Completas (CRpn)
19. A resposta na˜o e´ C47 = 35. Isso seria o modo de escolher 4 sabores diferentes en-
tre os 7 sabores oferecidos. A resposta para esse problema e´ representada por CR47,
nu´meros de combinac¸o˜es completas de classe 4 de 7 objetos. Para efetuar a compra
devemos escolher valores para as varia´veis x1, x2, . . . , x7, onde x1 e´ a quantidade que
vamos comprar de sorvetes do 1o sabor, . . ., x7 e´ a quantidade que vamos comprar de
sorvetesdo 7o sabor. E´ claro que x1, x2, . . . , x7 devem ser inteiros, na˜o negativos e que
x1 +x2 + · · ·+x7 = 4. Portanto podemos interpretar CRnp como o nu´mero de soluc¸oes
da equac¸a˜o x1 + x2 + . . .+ xn = p em inteiros na˜o negativos.
Abaixo vemos algumas soluc¸o˜es da equac¸a˜o bem como sua representac¸a˜o no esquema
bola-trac¸o (cada bola representa uma unidade no valor da inco´gnita; cada trac¸o e´ us-
ado para separar duas inco´gnitas). No caso dos sorvetes temos 4 bolas e 7−1 = 6 trac¸os.
x1 x2 x3 x4 x5 x6 x7
1 1 1 0 0 0 1
• • • •
0 2 0 1 0 0 1
• • • •
Assim, observa-se que para cada ordenac¸a˜o poss´ıvel das bolas e trac¸os, fica determi-
nado o nu´mero de cada tipo de sorvete. Logo, o nu´mero de combinac¸o˜es possiveis de
se escolher os 4 sabores e´ igual ao nu´mero de organizac¸o˜es poss´ıveis das bolas e trac¸os.
O nu´mero de modos poss´ıveis de se organizar as bolas e trac¸o˜s e´ P 4,64+6 =
10!
4!6!
= C46 .
4
Logo, CR47 = C
4
10 = 210.
No caso geral, para calcular CRpn, isto e´, para determinar o nu´mero de soluc¸o˜es inteiras
e na˜o negativas de x1 + · · · + xn = p ter´ıamos p bolas e n − 1 trac¸os. Logo, CRpn =
P p,n−1p+n−1 =
(n+p−1)!
p!(n−1)! = C
p
n+p−1.
20. Primeiro devemos decidir quantos ane´is havera´ em cada dedo, o que equivale a resolver
em inteiro e na˜o negativos a equac¸a˜o x1 + x2 + x3 + x4 = 6. Ha´ CR
6
4 = C
6
9 = 84
soluc¸o˜es inteiras e na˜o-negativas. Determinados os 6 lugares, devemos neles colocar os
6 ane´is, o que pode ser feito de 6! = 720 modos. A resposta e´ 84× 720 = 60.480.
TEORIA DOS CONJUNTOS
Algumas relac¸o˜es importantes:
(1) Para todo conjunto A ⊂ Ω, A ∪ φ = A, A ∩ φ = φ.
(2) A ⊂ B se e somente se A ∪B = B.
(3) A ⊂ B se e somente se A ∩B = A.
(4) A ∪ (B ∪ C) = (A ∪B) ∪ C.
(5) A ∩ (B ∩ C) = (A ∩B) ∩ C.
(6) A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C).
(7) A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C).
(8) A ∪ Ac = Ω, A ∩ Ac = φ, φc = Ω, Ωc = φ.
(9) (Ac)c = A.
(10) (A ∪B)c = Ac ∩Bc.
(11) (A ∩B)c = Ac ∪Bc.
21. (a) A ∩B ∩ Cc
(b) (Ac ∩Bc ∩ Cc) = (A ∪B ∪ C)c
(c) (A ∩B ∩ C)c
(d)
[
A ∩ (B ∩ C)c]
(e) (A ∩B ∩ C) ∩ Ac = (A ∩ Ac) ∩ (B ∩ C) = φ ∩ (B ∩ C) = φ
22. (a) {5}
(b) {1, 3, 4, 5, 6, 7, 8, 9, 10}
5
(c) (Ac ∩Bc) = (Ac)c ∪Bc(c) = A ∪B = {2, 3, 4, 5}
(d)
[
A ∩ (B ∩ C)c]c = [A ∩ (Bc ∪ Cc)]c = [A]c = {1, 5, 6, 7, 8, 9, 10}
(e)
[
A ∩ (B ∪ C)] = {3, 4} ⇒ [A ∩ (B ∪ C)] = {1, 2, 5, 6, 7, 8, 9, 10}
23. (a) Se ω ∈ (A∪B)∩(A∪C)⇒ ω ∈ (A∪B) e ω ∈ (A∪C)⇒ (ω ∈ A ou ω ∈ B) e (ω ∈
A ou ω ∈ C) ⇒ ω ∈ A ou ω ∈ (B ∩ C) ⇒ ω ∈ A ∪ (B ∩ C) 6= A ∪ (A ∩ C).
FALSO
(b) Se ω ∈ B ∪ (A ∩ Bc) ⇒ ω ∈ B ou ω ∈ (A ∩ Bc) ⇒ (ω ∈ A e ω /∈ B) ou ω ∈
B ⇒ ω ∈ A ou ω ∈ B e ω /∈ B ou ω ∈ B, ou seja ω ∈ (A ∪ B) e ω ∈ Ω ⇒
(A ∪B) ∩ Ω = (A ∪B). VERDADEIRO
(c) Se ω ∈ Ac ∩ B ⇒ ω /∈ A e ω ∈ B ⇒ ω ∈ B − A. Se ω ∈ A ∪ B ⇒ ω ∈ A ou ω ∈
B ⇒ ω ∈ A+B → A+B 6= B − A. FALSO
(d) Se ω ∈ (A ∪ B)c ⇒ ω /∈ (A ∪ B) ⇒ ω /∈ A e ω /∈ B ⇒ ω ∈ Ac e ω ∈ Bc ⇒ ω ∈
(Ac ∩Bc). Logo se ω ∈ (A∪B)c ∩C quer dizer que ω ∈ Ac, ω ∈ Bc e ω ∈ C. Se
ω ∈ C ⇒ ω /∈ Cc ⇒ Ac ∩Bc ∩ Cc 6= Ac ∩Bc ∩ C. FALSO
(e) Se ω ∈ (A ∩ B) ∩ (Bc ∩ C) ⇒ ω ∈ A e ω ∈ B e ω ∈ Bc e ω ∈ C Pore´m ω na˜o
pode pertencer a B e Bc. Logo esse conjunto e´ vazio. VERDADEIRO
24. (a) A = A ∩ Ω = A ∩ (B ∪Bc) = (A ∩B) ∪ (A ∩Bc)
(b) A ⊂ B ⇒ ∀ ω ∈ A ⇒ ω ∈ B. Supondo ν ∈ Bc ⇒ ν /∈ B ⇒ ν /∈ A. Pois se
ν ∈ A⇒ ν ∈ B o que seria contra´rio a` suposic¸a˜o. Logo, ν /∈ A⇒ ν ∈ Ac, enta˜o
ν ∈ Bc ⇒ ν ∈ Ac, assim Bc ⊂ Ac.
(c)
[
(A ∩Bc ∩ C) ∪ (Ac ∩B ∩ C)] ∩ (A ∩B ∩ Cc) =
=
[
C ∩
((
A ∩Bc) ∪ (Ac ∩B))] ∩ (A ∩B ∩ Cc).
Ou seja, ω deve pertencer a C e Cc, imposs´ıvel.
Logo
[
(A ∩Bc ∩ C) ∪ (Ac ∩B ∩ C)] ∩ (A ∩B ∩ Cc) = φ.
6