CEDERJ AD1 2 15

Curso de Tecnologia em Sistemas de Computa¸ca˜o
Disciplina: Fundamentos de Algoritmos para Computa¸ca˜o
Professoras: Susana Makler e Sulamita Klein
AD1 - Segundo Semestre de 2015
Nome Assinatura -

Quest˜ oes: 1. (1.5) Sejam A, B e C conjuntos arbitr´arios e P (A) o conjunto de partes do conjunto A. Verifique se cada uma das afirma¸co˜es abaixo ´e falsa ou verdadeira. Se for verdadeira, prove, se for falsa justifique.
(a) {A} ∈ P (A)
(b) {∅} ⊆ P (A)
(c) A ∆ (B ∩ C) = (A ∆ B) ∪ (A ∆ C)
(Lembre-se que A ∆ B ´e a diferen¸ca sim´etrica entre os conjuntos
A e B, isto ´e, A ∆ B = (A − B) ∪ (B − A).)
2. (1.5) Mostre pelo Princ´ıpio da Indu¸c˜ao Matem´atica que:
1 + 32 + 52 + · · · + (2n − 1)2 =

n(2n − 1)(2n + 1)
3

para todo n ∈ N, n ≥ 1.
3. (1,5) Um estacionamento disp˜oe de 20 vagas numeradas de 1 a 20.
Deseja-se colocar 20 carros em suas vagas, sendo 7 carros vermelhos, 5 carros brancos e 8 carros pretos.
1

(a) De quantas maneiras os carros podem ser colocados nas 20 vagas se considerarmos que todos os carros s˜ao diferentes e desejamos que aqueles da mesma cor fiquem em vagas consecutivas. Justifique.
(b) De quantas maneiras os carros podem ser colocados nas 20 vagas se considerarmos que carros da mesma cor s˜ao indistingu´ıveis?
Justifique.
4. (1,5) Listando os n´ umeros inteiros de 1 a 10.000, quantas vezes o d´ıgito
5 aparece se
(a) os d´ıgitos dos n´ umeros s˜ao todos diferentes? Justifique;
(b) os d´ıgitos dos n´ umeros podem ser repetidos? Justifique.
5. (1,0) Um coro possui 10 membros. De quantas maneiras se pode selecionar 3 grupos distintos de 6 membros cada, por ocasi˜ao de 3 eventos distintos? Justifique.
6. (1,5) Quantos s˜ao os anagramas da palavra C A R A C O L que n˜ao cont´em duas letras iguais juntas? Justifique.
(Sugest˜ao: considere o conjunto que tem as duas letras A juntas e o conjunto que tem as duas letras C juntas.)
7. (1,5) Um pedido para uma loja de ferragens cont´em 6 itens, onde cada item ´e um gal˜ao de tinta, um martelo ou uma