AD1-1-14_FAC_Gabarito

Prévia do material em texto

Curso de Tecnologia em Sistemas de Computaç ̃ao Disciplina: Fundamentos de Algoritmos para Computaç ̃ao Professoras: Susana Makler e Sulamita Klein Gabarito AD1 - Primeiro Semestre de 2014
Nome - Assinatura -
Atenç ̃ao! Embora o tópico Combinaç ̃ao com Repetiç ̃ao n ̃ao seja abor- dado na AD1, ele faz parte do conteúdo da AP1.
Quest ̃oes:
1. (1.5) Verifique se cada uma das afirmaç ̃oes abaixo é falsa ou verdadeira.
Se for verdadeira, prove, se for falsa justifique.
(i) A − (B − C) = (A − B) ∪ (B ∩ C), sendo A, B e C conjuntos
arbitrários.
Resposta: Falsa. Observe os diagramas de Venn da Figura 1.
(ii) Seja A = {∅,1} e P(A) o conjunto das partes de A. Ent ̃ao {∅} ∈
P(A).
Resposta: Verdadeiro, pois P(A) = {∅,{∅},{1},{∅,1}}. Logo,{∅} é elemento de P(A).
(iii) {
√
2,3}⊆{x ∈ Z : |3x − 7| ≤ 15}.
Resposta: Falso. Observe que
|3x − 7| ≤ 15
1
A
B
C
A B
C
(B − C) A − (B − C)
A
B
C
A B
C
(A − B)
(A − B) ∪ (B ∩ C)
Figura 1: Diagramas de Venn para A − (B − C)e(A − B) ∪ (B ∩ C). Note que o resultado das operaç ̃oes n ̃ao é o mesmo.
significa
−15 ≤ 3x − 7 ≤ 15,
isto é
−15 + 7 ≤ 3x ≤ 15 + 7,
ou seja
−8 3
≤ x ≤
22 3
.
Note um ainda que conjunto A -8
estar 3 <
√ 2 < contido deve ser elemento de B, temos 22 3
, em que mas
outro √
√
2 2 teria /∈ B, Z. todo que Uma ser elemento vez um que número de para A
2
inteiro para pertencer a {x ∈ Z : |3x−7| ≤ 15}, o que caracteriza um absurdo.
2. (1.0) Todos os convidados em um jantar bebem café ou chá; 13 con- vidados bebem café, 10 bebem chá e 4 bebem tanto café quanto chá. Quantas pessoas há nesse grupo?
Resposta: Considere os seguintes conjuntos: A =conjunto das pessoas que bebem chá B = conjunto das pessoas que bebem café Como todos os convidados bebem chá ou café, nosso objetivo é deter- minar qual o valor de n(A ∪ B). Utilizando o Princ ́ıpio da inclus ̃ao e exclus ̃ao para dois conjuntos temos:
n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
Substituindo os valores fornecidos na fórmula temos: n(A∪B)=10+ 13 − 4 = 19. Portanto, existem 19 pessoas neste grupo.
3. (2.5)
(a) Mostre pelo Princ ́ıpio da Induç ̃ao Matemática que:
3n − 2 é ́ımpar para todo inteiro n ≥ 1.
Resposta: Um número par é um múltiplo de 2. Todo número ́ımpar sucede um número par. Sendo assim, podemos representá- lo pela soma de um número par e 1. (Exemplo: 3 é ́ımpar e podemos representá-lo como 2 + 1). Portanto, considere
P(n):3n − 2=2j + 1
para algum j ∈ Z,j ≥ 0. base da induc ̧ ̃ao: n = 1. Como 31 −2 = 1 é um número ́ımpar (j = 0), temos que P(1) é verdadeira.
hip ́otese de induc ̧ ̃ao: Suponha que P(k):3k − 2=2j/ + 1 para algum j/ ∈ Z,j/ ≥ 0 seja verdadeira.
3
passo indutivo: Vamos provar que se P(k) é verdadeira, ent ̃ao P(k +1):3k+1 − 2=2j// + 1 também é verdadeira para algum j// ∈ Z,j/ ≥ 0:
3k+1 − 2 =
3 × }{{}
3k H.I.
−2 =
3(2j/ + 3) − 2 = 6j/ +7=
2 (3j/ } {{ + 3) } j
+1 =
2j// + 1
Logo, pelo Princ ́ıpio de Induç ̃ao Matemática, 3n −2 é ́ımpar para todo n ∈ N.
(b) Considere a sequência a
n
tal que: a
o
= 12, a
1
= 29 e a
k
= 5a
k-1
− 6a
k-2
para todo inteiro k ≥ 2. Mostre por Induç ̃ao Forte que: a
n
= 5.3n + 7.2n para todos inteiros n ≥ 0.
Resposta: Dada a sequência a
n
tal que: a
0
= 12, a
1
= 29 e a
k
= 5a
k-1
− 6a
k-2
para todo inteiro k ≥ 2, vamos mostrar por induç ̃ao forte que P(n) : a
n
= 5.3n + 7.2n,é verdadeira para todo n ≥ 0. base da induc ̧ ̃ao: Vamos mostrar que P(0) e P(1) s ̃ao verda- deiras.
n = 0 Como a
0
=12e5.30 + 7.20 = 12 temos que P(0) é válida. Além disso, como a
1
=29e5.31 + 7.21 = 29 também temos a validade de P(1).
hip ́otese de induc ̧ ̃ao: Suponha que P(i) : a
i
= 5.3i + 7.2i seja verdadeira para todo i ≤ k.
4
passo indutivo: Vamos mostrar que
P(k + 1) : a
k+1
= 5.3k+1 + 7.2k+1
é verdadeira.
a
k+1
= 5 }{{}
a k H.I.
−6a
}{{} k-1 = 5(5.3k + 7.2k) − 6(5.3k-1 H.I.
+ 7.2k-1) = 52.3k + 5.7.2k − [6.5.3k-1 + 6.7.2k-1] = 52.3k + 5.7.2k − 6.5.3k-1 − 6.7.2k-1] = 5.3k-1(5.3 − 6) + 7.2k-1(5.2 − 6) = 5.3k-1.32 + 7.2k-1.22 = 5.3k+1 + 7.2k+1
Logo, pelo Princ ́ıpio de Induç ̃ao Matemática Forte, temos que a sequência a
n
descrita corresponde a a
n
= 5.3n + 7.2n para todos inteiros n ≥ 0.
4. (1.2) Em quantos dos números naturais menores do que 10.000 n ̃ao ocorrem números idênticos pareados (isto é, n ̃ao aparecem os bocos 11, 22, etc)?
Resposta: Vamos analisar a quantidade de números onde n ̃ao ocorre o pareamento de algarismos idênticos de acordo com a quantidade de d ́ıgitos de cada número. caso 1: 1 d ́ıgito Neste caso, nenhum número apresenta algarismos idênticos pareados. Logo temos 9 números n ̃ao pareados. caso 2: 2 d ́ıgitos Note que para o primeiro d ́ıgito podemos escolher qualquer algarismo exceto o 0. Para o segundo, podemos escolher qualquer algarismo me- nos o escolhido para a primeira posiç ̃ao. Sendo assim, pelo PM, temos 9 × 9=92 números n ̃ao pareados. caso 3: 3 d ́ıgitos Repete-se o racioc ́ınio do caso 2 para os dois primeiros d ́ıgitos. Para o terceiro, n ̃ao podemos escolher apenas o algarismo escolhido para a
5
segunda posiç ̃ao. Logo, pelo PM, temos 9 × 9 × 9=93 números n ̃ao pareados. caso 4: 4 d ́ıgitos Repete-se o racioc ́ınio do caso 3 para os três primeiros d ́ıgitos. Para o quarto, n ̃ao podemos utilizar o algarismo que utilizamos na terceira posiç ̃ao, restando, portanto, 9 possibilidades de escolha. Assim, pelo PM, temos 93 × 9=94. Como os casos de 1 a 4 excluem-se mutuamente, pelo PA, temos 9 + 92 + 93 + 94 números menores que 10000 que n ̃ao possuem algarismos idênticos pareados.
5. (1,2) Há 12 cadeiras em fila. De quantos modos 6 casais podem se
sentar nas cadeiras, se nenhum marido senta separado de sua esposa?
Resposta: Existem 2 maneiras de um marido sentar-se ao lado de sua esposa: pela direita ou pela esquerda. Vamos considerar cada casal como um único elemento e permutá-los. Assim, pelo PM, temos:
26 × P
6
= 26 × 6!
maneiras dos casais se disporem nesta fila.
6. (1,3) De quantas maneiras 10 livros distintos podem ser colocados em
5 caixas idênticas, contendo 2 livros cada uma?
Resposta: Vamos escolher os livros que ocupar ̃ao cada caixa. Vamos considerar dois casos de interpretaç ̃ao.
• caso 1: A ordem com que os livros est ̃ao dispostos na caixa é considerada. Neste caso, para escolhermos e arrumarmos os 2 livros em cada caixa utilizamos um Arranjo simples. Logo, para a primeira caixa temos temos A2
10
. Para a segunda, A2 8
. Para a terceira, quarta e quinta
A2 6
respectivamente × A2
4
× A2 2
= 10!
8!
× 8! 6!
A2 × 6
, 6! 4!
A2
× 4
e 4! 2!
A2 × 2
. 2! 0!
Pelo = 10!
PM temos A2
10
× A2 8
×
6
• caso 2: A ordem com que os livros est ̃ao dispostos na caixa n ̃ao é considerada. Neste caso, utilizamos Combinaç ̃ao simples para escolher os li- vros que compor ̃ao cada caixa. Teremos respectivamente para as caixas 1, 2, 3, 4 e 5 as seguintes formas distintas de escolha: C2
8!2! 10!
10
,C2 × 8
6!2! 8! ,C2 × 6
,C2
4!2! 6!
4
,C2 × 2
2!2! . 4!
Pelo = PM, 10! 32
.
temos C2
10
× C2 8
× C2 6
× C2 4
× C2 2
=
Note que, em ambos os casos, como as 5 caixas s ̃ao ID
ENTICAS, ˆ
ao aplicarmos qualquer um desses racioc ́ınios estamos considerando por exemplo que termos uma caixa com livros 1 e 2 e outra com livros 3 e 4 é diferente de termos a primeira com livros 3 e 4 e a segunda com livros 1 e 2. Desta forma, para finalizarmos a quest ̃ao, precisamos remover os casos de repetiç ̃ao como estes. Portanto, devemos dividir o resultado por P
5
= 5!. Ent ̃ao para o caso nas caixas e para o 1 temos caso 2 os 10 livros nas 5 caixas.
10! temos 5!
maneiras 32.5!
10!
distintas de arrumar os livros maneiras distintas de arrumar
7. (1,3) Uma palavra tem 7 letras, sendo que uma delas aparece k vezes, e as outras letras restantes aparecem sem repetiç ̃ao. Sabendo que o número de anagramas que se obtém permutando as letras desta palavra é 210, calcule k.
Resposta: A palavra possui 7 letras das quais apenas uma se repete k vezes. Para calcularmos onúmero de anagramas dessa palavra usamos Permutaç ̃ao com repetiç ̃ao: tem 210 anagramas, temos
P
7
k,1,1,1,1,1,1
= k! 7!
. Sabendo que a palavra
k! 7!
= 210.
Donde k! = 24 e consequentemente k = 4.
7