Avaliação Presencial
Por: fmbarros • 18/3/2019 • Exam • 1.282 Palavras (6 Páginas) • 132 Visualizações
Gabarito da AD1 - Fundamentos de Algoritmos para
Computa¸c˜ao - 2008/01
1. (2.0) Seja A um conjunto com um n´umero finito de elementos sendo P(A) o conjunto
de partes de A. Sejam B e D dois conjuntos arbitr´arios. Verifique se cada uma
das afirma¸c˜oes abaixo ´e falsa ou verdadeira. Se for verdadeira, prove, se for falsa
justifique
(a) {A} ⊆ P(A)
Resposta: A afirma¸c˜ao ´e verdadeira.
Lembremos que:
– B ⊆ C significa que todo elemento de B ´e elemento de C;
– P(A) ´e o conjunto cujos elementos s˜ao subconjuntos de A, isto ´e, B ∈ P(A)
se e somente se B ⊆ A. Em particular, como A ⊆ A, tem-se que A ∈ P(A).
Logo, como o ´unico elemento de {A} ´e A, que ´e um elemento de P(A), tem-se
que {A} ⊆ P(A).
(b) ∅ ∈/ P(A)
Resposta: A afirma¸c˜ao ´e falsa, j´a que ∅ ´e um elemento de P(A), pois ∅ ⊆ A,
para todo conjunto A. Logo, ∅ ∈ P(A).
(c) D ∩ (B ∪ D) ⊆ B
Resposta: A afirma¸c˜ao ´e verdadeira, pois:
D ∩ (B ∪ D) =
(propriedade distributiva) = (D ∩ B) ∪ (D ∩ D) =
(D ∩ D) = ∅ = (D ∩ B) ∪ ∅ =
A ∪ ∅ = A = D ∩ B ⊆ B
Pois, se x ∈ (D ∩ B) ent˜ao x ∈ B.
2. (2.0) Mostre pelo princ´ıpio da indu¸c˜ao matem´atica que:
1.3.5.7....(2n − 1) = (2n)!
2nn!
para todo n natural.
Resposta: Seja P(n) = 1.3.5.....(2n − 1) = (2n)!
2nn!
, para n ∈ N.
Base da indu¸c˜ao: Para n = 1, resulta que o produto se reduz ao primeiro fator dado,
que ´e o 2.1 − 1 = 1 = (2.1)!
2
11! .
Logo, P(1) ´e verdadeira.
Hip´otese de indu¸c˜ao:
Suponha verdadeiro para k, isto ´e, P(k) ´e verdadeiro:
P(k) : 1.3.5.....(2k − 1) = (2k)!
2
k.k!
Devemos provar que P(k + 1) ´e verdadeiro, isto ´e:
P(k + 1) : 1.3.5.....(2k − 1)(2(k + 1) − 1) = (2(k+1))!
2
k+1.(k+1)!
Desenvolvendo para k + 1 e usando a hip´otese de indu¸c˜ao, temos que:
1.3.5....(2k − 1)(2(k + 1) − 1) =
= 1.3.5.....(2k − 1)
| {z }
(Por hipotese indutiva ´ )
(2(k + 1) − 1) =
=
(2k)!
2
k.k!
.[2(k + 1) − 1] =
=
(2k)!
2
k.k!
.[2k + 1] =
=
(2k)!(2k+1)(2k+2)
2
k.k!(2k+2) =
=
(2k+2)!
2
k.k!2(k+1) =
=
(2k+2)!
2
k+1.(k+1)! =
=
(2(k+1))!
2
k+1.(k+1)!
Logo, pelo princ´ıpio da indu¸c˜ao, a express˜ao ´e verdadeira, ∀n ∈ N.
3. (2.0) Considere as letras da palavra MATEMATICAMENTE.
(a) Em quantos anagramas n˜ao existem vogais consecutivas? Justifique.
Resposta: Vamos primeiramente arrumar as consoantes e, depois vamos entremear as vogais. O n´umero de modos de arrumar em fila as consoantes M (3
vezes), T (3 vezes), C (1 vez), N (1 vez) ´e P
3,3,1,1
8 =
8!
3!3!1!1! =
8.7.6.5.4
3.2 = 1120.
Para cada arruma¸c˜ao das consoantes, por exemplo, MTCMTNMT, podemos
colocar as 7 vogais nos 9 espa¸cos vazios da figura:
M T C M T N M T
Temos, ent˜ao, C
7
9 =
9!
7!2! =
9.8
2 = 36 modos de escolher os sete espa¸cos que ser˜ao
ocupados. Como a combina¸c˜ao ´e dada para posicionar onde ir´a ficar as vogais,
falta ainda permutar estas vogais, dando P
3,3,1
7 =
7!
3!3! =
7.6.5.4
3.2 = 140 maneiras
de permutar as vogais para cada posi¸c˜ao dada na combina¸c˜ao.
Logo, pelo princ´ıpio multiplicativo, a resposta ´e que temos P
...