INDIQUE TODOS OS RESULTADOS INTERMEDIÁRIOS E ARGUMENTOS USADOS!!!!
(exercícios contendo apenas a RESPOSTA não serão considerados)
Matemática Discreta – IF63E / Prova 1
Adolfo Neto (08/10/2009)
LEIA: Das 10 questões abaixo, ESCOLHA 5 para serem avaliadas.
(2,0) 1. Quantas soluções inteiras não-negativas existem para: x1 + x 2 + x3 + x 4 = 12 ?
Sugestão: pense neste problema como a distribuição de 12 moedas de 1 centavo entre 4
crianças.
(2,0) 2. Prove que qualquer conjunto de sete inteiros distintos inclui dois inteiros x e y, tais
que (x+y) ou (x-y) seja divisível por 10.
Dica: pense em agrupar os possíveis restos da divisão de um inteiro por 10 de forma que
(x+y) ou (x-y) sejam divisíveis por 10.
(2,0) 3. De quantas maneiras diferentes você pode sentar 10 homens e 6 mulheres em uma
fila se 2 homens nunca sentam juntos?
(2,0) 4. Prove que qualquer quantia em selos maior ou igual a 12 centavos pode ser obtida
usando-se apenas selos de 4 e 5 centavos.
(2,0) 5. Prove por indução que:
para todo inteiro n ≥ 1.
(2,0) 6. A diferença simétrica é uma operação binária definida em conjuntos por
A ⊕ B = ( A − B) ∪ ( B − A) . Prove que A ⊕ B = ( A ∪ B ) − ( A ∩ B ) .
(2,0) 7. Sejam ρ e σ relações binárias em um conjunto S. Se ρ e σ são transitivas, ρ ∪ σ é
transitiva? E ρ ∩ σ ? Justifique.
(2,0) 8. Prove que P(n,1) + P(n,2)=n2 para n ≥ 2. Onde P(n,i) é número de permutações de i
objetos distintos escolhidos dentre n objetos distintos.
(2,0) 9. Sejam as funções f : S → T e g : T → U . Prove que, se g  f é injetora, então f é
injetora.
(2,0) 10.