Tecnologia

Curso de Tecnologia em Sistemas de Computa¸˜o ca Disciplina: Fundamentos de Algoritmos para Computa¸˜o ca Professoras: Susana Makler e Sulamita Klein AD1 - Segundo Semestre de 2012 Quest˜es: o 1. (1.5) Verifique se cada uma das afirma¸˜es abaixo ´ falsa ou verdadeira. co e 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´ meros de 1 a 1000, inclusive, quantos s˜o divis´ u a ıveis por 2 ou 5 ou 12? Justifique. Sugest˜o: Use o Princ´ a ıpio da Inclus˜o e Exclus˜o. a a 3. (1.0) Mostre pelo Princ´ ıpio da Indu¸˜o Matem´tica que: ca a 1 1 k 1 + +···+ = 1.3 3.5 (2k − 1)(2k + 1) 2k + 1 para todo n natural. Observa¸˜o: Indique claramente os passos da indu¸˜o. ca ca 4. (1.0) Seja a sequˆncia a1 , a2 , a3 , . . . definida como: e a1 = 1, a2 = 3 ak = ak−2 + 2ak−1 para todos inteiros k ≥ 3 Mostre usando Indu¸˜o Forte que an ´ ´ ca e ımpar para todo n natural. Observa¸˜o: Indique claramente os passos da indu¸˜o. ca ca 1

5. (2.0) Um n´ mero de inscri¸˜o de um aluno em uma universidade ´ u ca 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´ meros de inscri¸˜o com todos os u ca algarismos diferentes. (a) Quantos s˜o os n´ meros de inscri¸˜o? Justifique. a u ca (b) Quantos deles s˜o pares? Justifique. a (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? Justifique.

2