Tecnologia em sistema de computação

Curso de Tecnologia em Sistemas de Computa¸c˜ao
Disciplina: Fundamentos de Algoritmos para Computa¸c˜ao
Professoras: Susana Makler e Sulamita Klein
AD1 - Segundo Semestre de 2012
Quest˜oes:
1. (1.5) Verifique se cada uma das afirma¸c˜oes abaixo ´e falsa ou verdadeira.
Se for verdadeira, prove, se for falsa justifique.
(a) A − (B − C) = (A − B) − C;
(b) (A \ B) − C = (A \ B)
(A \ C).
Lembre que: X
Y = (X − Y ) [ (Y − X).
2. (1.5) Dentre os n´umeros de 1 a 1000, inclusive, quantos s˜ao divis´ıveis por 2 ou 5 ou 12? Justifique.
Sugest˜ao: Use o Princ´ıpio da Inclus˜ao e Exclus˜ao.
3. (1.0) Mostre pelo Princ´ıpio da Indu¸c˜ao Matem´atica que:
1
1.3
+
1
3.5
+ · · · +
1
(2k − 1)(2k + 1)
=
k
2k + 1 para todo n natural.
Observa¸c˜ao: Indique claramente os passos da indu¸c˜ao.
4. (1.0) Seja a sequˆencia a1, a2, a3, . . . definida como: a1 = 1, a2 = 3 ak = ak−2 + 2ak−1 para todos inteiros k  3
Mostre usando Indu¸c˜ao Forte que an ´e ´ımpar para todo n natural.
Observa¸c˜ao: Indique claramente os passos da indu¸c˜ao.
1
5. (2.0) Um n´umero de inscri¸c˜ao de um aluno em uma universidade ´e composto de 7 algarismos dente 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. O primeiro algarismo pode ser 0. Considere os n´umeros de inscri¸c˜ao com todos os algarismos diferentes.
(a) Quantos s˜ao os n´umeros de inscri¸c˜ao? Justifique.
(b) Quantos deles s˜ao pares? Justifique.
(c) Quantos deles tem todos os algarismos pares? Justifique.
(d) Quantos deles tem os algarismos 2 e 5 juntos? Justifique.
6. (1,5) De quantas maneiras 18 objetos distintos podem ser divididos entre 5 pessoas, de modo que 4 pessoas fiquem com 4 objetos (cada uma delas) e uma fique com 2 objetos. Justifique.
7. (1.5) De quantas maneiras as letras da palavra INDIVIDUALIZAR podem ser permutadas de modo que duas letras I nunca fiquem juntas?