CEDERJ Computação -

...

- = {x ∈ U| x é divisível por 2} = {x ∈ U| x = 2n,n ∈N};

- = {x ∈ U| x é divisível por 5} = {x ∈ U| x = 5m,m ∈N} C = {x ∈ U| x é divisível por 12} = x ∈ U| x = 12p,p ∈N}.

Pelo Princípio da Inclusão e Exclusão temos:

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

C) + n(A ∩ B ∩ C)

- = {2 × 1,2 × 2,2 × 3,···,2 × 500} = {2,4,6,···,1000} n(A) = 500

- = {5 × 1,5 × 2,5 × 3,···,5 × 200} = {5,10,15,···,1000} n(B) = 200

- = {12 × 1,12 × 2,12 × 3,···,12 × 83} = {12,24,36,···,996} n(C) = 83

(A ∩ B) = {x ∈ U| x é divisível por 10} = {x ∈ U| x = 10k,k ∈N} =

{10 × 1,10 × 2,10 × 3,···,10 × 100} = {10,20,30,···,1000}

n(A ∩ B) = 100

- ∩ C) = {x ∈ U| x é divisível por 12} = C n(A ∩ C) = 83

- ∩ C) = {x ∈ U| x é divisível por 60} = {x ∈ U| x = 60j,j ∈N} =

{60 × 1,60 × 2,60 × 3,···,60 × 16} = {60,120,180,···,960} n(B ∩ C) = 16

(A ∩ B ∩ C) = {x ∈ U| x é divisível por 60} = (B ∩ C) n(A ∩ B ∩ C) = 16

Daí, temos:

n(A ∪ B ∪ C) = 500 + 200 + 83 − 100 − 83 − 16 + 16 = 600

Logo, temos 600 números inteiros entre 1 e 1000 que são divisíveis por 2,5 ou 12.

3. (1.0) Mostre pelo Princípio da Indução Matemática que:

1[pic 5].

para todo n natural.

Observação: Indique claramente os passos da indução.

Resposta: Seja [pic 6]N.

base da indução: Por um lado, [pic 7].

Por outro lado, quando k = 1 temos [pic 8].

Logo, P(1) é verdadeira. hipótese de indução: Suponha que [pic 9]

[pic 10] seja verdadeira.

passo indutivo: Vamos provar que se P(n) é verdadeira então

[pic 11]

também é verdadeira.

[pic 12]

HI

[pic 13]

Por outro lado,

[pic 14]

Como (I) = (II) temos P(n + 1) verdadeira.

Logo,[pic 15] verdadeira

∀k ∈N.

4. (1.0) Seja a sequência a1,a2,a3,... definida como: a1 = 1, a2 = 3 ak = ak−2 + 2ak−1 para todos inteiros k ≥ 3

Mostre usando Indução Forte que an é ímpar para todo n natural. Observação: Indique claramente os passos da indução.

Resposta: Queremos mostrar que an é ímpar para todo n ∈N. Então, seja P(n) : an = 2m − 1, n,m ∈N, onde an é definido pela seguinte relação de recorrência:

a1 = 1, a2 = 3

ak = ak−2 + 2ak−1 para todos inteiros k ≥ 3

base da indução: a1 = 1 que é um número ímpar. Logo P(1) é verdadeira.

hipótese de indução: Suponha que P(1),P(2),···,P(n) são verdadeiras, ou seja, a1,a2,···,an são ímpares. passo indutivo: Vamos mostrar que P(n+1) : an+1 = 2m0−1, m0 ∈ N.

an+1 = [pic 16] [pic 17]ímpar pela HI par

[pic 18].

Logo, an+1 pode ser escrito na forma 2m0 − 1 e, portanto, é ímpar.

Portanto, pelo Princípio da Indução Forte an é ímpar para todo n natural

5. (2.0) Um número de inscrição de um aluno em uma universidade é composto de 7 algarismos dentre 0,1,2,3,4,5,6,7,8,9. O primeiro algarismo pode ser 0. Considere os números de inscrição com todos os algarismos diferentes.

- Quantos são os números de inscrição? Justifique.

Resposta: Como temos 10 algarismos dos quais queremos escolher 7 distintos e a ordem dos desses algarismos importa, vamos resolver esta questão utilizando o conceito de arranjo simples. Assim, temos[pic 19] números de inscrição com 7 algarismos distintos.

- Quantos deles são pares? Justifique.

Resposta: Temos 5 algarismos pares que podemos escolher para ocupar a última posição. Como não temos repetição de algarismos, temos 9 para escolher e posicionar nas 6 posições restantes.

Podemos fazer isso de[pic 20].

Pelo Princípio Multiplicativo, temos [pic 21]

52