Fundamentos De Algoritmos Para Computação

Curso de Tecnologia em Sistemas de Computação

Disciplina Fundamentos de Algoritmos para Computação

Gabarito da AP1 - Primeiro Semestre de 2010

Questões:

1. (2.0) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.

Se for verdadeira, prove, se for falsa justifique.

(a) ∅ = {∅}

Resposta: FALSO. Dois conjuntos são iguais se todo elemento de

um conjunto é elemento do outro conjunto e vice-versa.

O conjunto ∅ não tem elementos enquanto {∅} tem um elemento,

∅ ∈ {∅}. Logo, ∅ 6= {∅}.

(b) (A ∩ B) ∪ C = (A ∪ C) ∩ B

Resposta: FALSO. Contra-exemplo: Sejam os conjuntos A =

{1, 2, 3}, B = {3, 4, 5} e C = {1, 3, 5}.

Temos que (A ∩ B) = {3}, (A ∩ B) ∪ C = {1, 3, 5}, (A ∪ C) =

{1, 2, 3, 5} e (A ∪ C) ∩ B = {3, 5}.

Podemos concluir que (A ∩ B) ∪ C 6= (A ∪ C) ∩ B.

(c) n((A ∪ B) ∩ C) ≤ n(A ∩ C) + n(B ∩ C)

Resposta: VERDADEIRO. Pela propriedade distributiva, temos

que (A∪B) ∩ C = (A∩ C) ∪ (B ∩ C), e isto implica em dizer que

n((A ∪ B) ∩ C) = n((A ∩ C) ∪ (B ∩ C)).

Portanto,

n((A ∪ B) ∩ C) =

= n((A ∩ C) ∪ (B ∩ C)) =

= n(A ∩ C) + n(B ∩ C)−n((A ∩ C) ∩ (B ∩ C)) =

= n(A ∩ C) + n(B ∩ C)−n(A ∩ B ∩ C)

| {z }

´E

negativo

=

≤ n(A ∩ C) + n(B ∩ C)

2. (2.0) Mostre por indução matemática que:

23n − 1 é divisível por 7 para todo natural n ≥ 1.

Resposta: Seja P(n) : 23n − 1 divisível por 7 , para todo n ∈ N.

Base da indução:

Para n = 1, temos que 23.1−1 = 7, que é divisível por 7, portanto P(1)

é verdadeira.

Hipótese de indução: Suponhamos que a proposição se verifica para k,

isto é, P(k) é verdadeira:

P(k) : 23k − 1 é divisível por 7 ,ou seja, para algum q ∈ N temos que

23k − 1 = 7q.

Devemos provar que P(k + 1) é verdadeira, isto é:

P(k + 1) : 23(k+1) − 1 é divisível por 7

De fato, da hipótese indutiva indutiva temos que 23k = 1 + 7q.

Portanto, desenvolvendo 23(k+1)−1 e usando a igualdade acima, resulta:

23(k+1) − 1 = 23k.23 − 1 =

= (1 + 7q)23 − 1 =

= 8 + 7 × 8.q − 1 =

= 7 + 7 × 8.q =

= 7 (1 + 8q)

| {z }

r

E como r = 1 + 8q ∈ N provamos que 23(k+1) − 1 é divisível por 7.

3. (2.0) Considere os algarismos 1, 2, 3, 4, 5, 6 e 7. Quantos números naturais

superiores a 1000 e inferiores a 10000 podem ser formados se:

(a) os números são pares e têm todos os dígitos diferentes. Justifique.

Resposta: Vamos contar separadamente, já que para um número

ser par, este deve terminar em dígito par. Como os algarismos são

1, 2, 3, 4, 5, 6, 7, temos que os números pares devem terminar com

2, 4 ou 6.

Os números são de 4 dígitos. O último dígito pode ser 2, ou 4, ou

6, isto é, temos 3 possibilidades para o último dígito.

Suponhamos que o último dígito está fixado, restam 6 números

para 3 posições, ou seja, arranjos de 6 tomados 3 a 3, A(6, 3) =

6!

(6−3)! = 6!

3! .

Logo, pelo princípio multiplicativo temos 3×A(6, 3) = 360 números

que são pares, que são maiores que 1000 e menores que 10000 e

que têm todos os dígitos diferentes.

(b) os números são ímpares e os dígitos podem ser repetidos. Justifique.

Resposta: Começamos novamente pelo último dígito, que pode ser

1, 3, 5 ou 7, portanto temos 4 possibilidades. Fixada uma possibilidade,

restam 3 posições para serem preenchidas por 7 dígitos,

que podem estar repetidos, portanto temos arranjos com repetição

de 7 elementos tomados 3 a 3, AR(7, 3) = 73.

Logo, pelo princípio multiplicativo temos 4 × 73 = 1372 números

que são ímpares, que são maiores que 1000 e menores que 10000

e que podem ser repetidos.

4. (2.0) Quantos são os anagramas da palavra ARARAQUARA que

não começam pela letra A ? Justifique.

Resposta: A palavra A R A R A Q U A R A possui 10 letras: 5 A,

3 R, 1 Q, e 1 U.

Os anagramas podem começar com as letras R, Q, ou U.

O número de anagramas que