UNIVERSIDADE FEDERAL DE UBERLÂNDIA
Faculdade de Computação
Disciplina : Matemática para Ciência da Computação – 2º Semestre 2009
Professora : Sandra Aparecida de Amo
Lista de Exercícios nº 5
1. Para cada caso a seguir, determine se a função é injetora, sobrejetora, ou ambos. Prove
suas afirmações.
a) ƒ : Z→Z definida por ƒ(x) = 2x
b) ƒ : Z→Z definida por ƒ(x) = 10 + x
c) ƒ : N→N definida por ƒ(x) = 10 + x
d) ƒ : Z→Z definida por
x se x é par
2
ƒ(x) =
x-1 se x é impar
2
e) ƒ : Q→Q definida por ƒ(x) = x ²
2. Seja A um conjunto de n elementos e seja k є N, k ≤ n. Quantas funções ƒ: A → {0,1}
existem, para as quais há exatamente k elementos α em A com ƒ(α) = 1?
3. Seja (α1, α2, α3, α4, α5) uma sequência de cinco inteiros distintos. Diremos que esta
sequência é crescente de α1 < α2 < α3 < α4 < α5 e decresente se
α1 > α2 > α3 > α4 > α5 . Outras sequências podem apresentar padrões diferentes de <s e >s.
Na sequência (1,5,2,3,4), temos 1 < 5 > 2 < 3 < 4. Diferentes sequências podem apresentar o
mesmo padrão de <s e >s entre seus elementos. Por exemplo, (1,5,2,3,4) e (0,6,1,3,7) têm o
mesmo padrão de <s e >s, conforme ilustrado a seguir:
1 < 5 > 2 < 3 < 4.
↨ ↨
↨ ↨
0 < 6 > 1 < 3 < 7
Dada uma coleção de 17 sequências de cinco inteiros distintos, prove que duas delas têm o
mesmo padrão de <s e >s.
4. Dois números de matrícula no Seguro Social empatam nos zeros quando um algarismo de
um número é zero se e somente se o algarismo correspondente do outro também é zero. Por
exemplo, os números do Seguro Social 120-90-1109 e 430-20-5402 têm zeros empatados.
Prove: Dada uma coleção de 513 números de registro no Seguro Social, deve haver dois com
zeros empatados.
5. Uma função f: {1,2,...,n} → {1,2,...,n} é dita "crescente" se para todo x,y : se x ≥ y então f(x) ≥
f(y).
Exemplo: considere f:{1,2,3} → {1,2,3} tal que f(1) = 2, f(2) = 2 e f(3) = 3. Neste caso, f é uma
função crescente. Considere g: {1,2,3} → {1,2,3} tal que g(1) = 2, g(2) = 3, g(3) = 1. Neste caso,
g não é crescente, pois 3 > 1 mas g(3) < g(1).
Quantas funções f: {1,2,...,n} → {1,2,...,n} crescentes existem ?
Observação importante que vai ajudar a encontrar a resposta: Repare que a função crescente
f:{1,2,3} → {1,2,3} tal que f(1) = 2, f(2) = 2 e f(3) = 3 pode ser representada pela lista [2,2,3]. Em
geral, qualquer função crescente f: {1,2,...,n} → {1,2,...,n} pode ser vista como uma lista de
tamanho n, crescente e com repetições. Assim, seu trabalho consiste em contar quantas listas
de tamanho n crescentes com repetições existem com elementos no conjunto {1,2,...,n}.
6. Uma função f: {1,2,...,n} → {1,2,...,m} é dita "estritamente crescente" se para todo x,y : se x >
y então f(x) > f(y).
Exemplo: f:{1,2,3} → {1,2,3,4} tal que f(1) = 2, f(2) = 3 e f(3) = 4. Neste caso, f é uma função
estritamente crescente. Considere f:{1,2,3} → {1,2,3,4} tal que f(1) = 2, f(2) = 2 e f(3) = 4. Neste
caso f é crescente mas não estritamente crescente.
Quantas funções f: {1,2,...,n} → {1,2,...,m} (m > n) estritamente crescentes existem ?