Ad1 fac

Tecnologia em Sistemas de Computação
Disciplina: Fundamentos de Algoritmos para Computação Professoras: Susana Scheimberg de Makler e Sulamita Klein Gabarito: AD1
(1) - 2 + 5 + 8 + ... + (3n − 1) =
Por indução: para n = 1, 3 ∗ 1 − 1 = 2 =
1(1+3∗1) 2

n(1+3n) 2

∀n ∈ N

= 2 é verdadeira k(1+3k) 2

Suponha verdadeira para n = k isto é, 2 + 5 + ... + (3k − 1) =

(Vamos mostrar que se é verdadeira para k ⇒verdadeira para k + 1) Desenvolvendo para n = k + 1

2 + 5 + 8 + ... + (3k − 1) + [3(k + 1) − 1] =
(por hipótese de indução)

=

k(1+3k) 2

+ (3k + 2) =

k+3k2 +6k+4 2

=

3k2 +7k+4 2

=

1 = 1 (3k 2 + 6k + 3 + k + 1) = 2 [3(k 2 + 2k + 1) + (k + 1)] = 2 1 = 1 [3(k + 1)2 + (k + 1)] = 2 (k + 1)[3(k + 1) + 1] 2

Logo a expressão é verdadeira ∀n ∈ N

(2)
(a) Estamos considerando arranjos simples de 9 elementos tomados 6 a 6, portanto a resposta é
A(9, 6) =
9! 3!

(b) Nesta parte estamos considerando arranjos com repetição de nove elementos tomados 6 a 6, a resposta é A6 = 96 . 9 Ou
P1 P2 P3 P4 P5 P6 9 9 9 9 9 9 .

Em cada uma das 6 posições temos 9 possibilidades Pelo P.M. temos 9 × 9 × 9 × 9 × 9 × 9 = 96

(c) Temos C(9, 3) possibilidades de escolher 3 algarismos distintos entre os 9. Depois, com as
2,2,2 repetições de cada um deles temos: P6 6! 9! Logo pelo P.M. temos C(9, 3) × P 2,2,2 = ( 3!6! ) × ( 2!2!2! ) possibilidades. 6

(3) x1 + x2 + x3 + x4 + x5 = 25 , x1 , x2 ≥ 3 , x4 , x5 ≥ 7
Fazendo:

x1 = y1 + 3, y1 ≥ 0 , x4 = y4 + 7 , y4 ≥ 0 , x3 = y3 x2 = y2 + 3, y2 ≥ 0 , x5 = y5 + 7 , y5 ≥ 0 e substituindo

y1 + y2 + y3 + y4 + y5 = 25 − 3 − 3 − 7 − 7 isto é

y1 + y2 + y3 + y4 + y5 = 5,

yi ≥ 0,

i = 1, 2, 3, 4, 5
9! 5!4!

5 Solução: CR5 = C(5 + 5 − 1, 5) = C(9, 5) =

(4)
Permuta-se circularmente a posição dos n pares o que nos dá →P Cn = (n − 1)! Permuta-se cada par: 2! , n pares → 2! × 2! × ... × 2! = 2n Pelo P.M. temos (n − 1)! × 2n maneiras.

(5)
¯ Da denição de complemento de um conjunto A, A