Prova 1 - Análise Combinatória (2015/1) (com gabarito) - Prof. Rodrigo Machado

Prévia do material em texto

Teoria dos Grafos e Análise Combinatória – Turma A – 2015/1
Prova 1 – Análise Combinatória – Prof. Rodrigo Machado
Nome: Cartão UFRGS:
Regras: a folha de consulta (tamanho A4, manuscrita, frente e verso) e os rascunhos
utilizados devem ser entregues junto com a prova. Respostas finais a caneta. Simplifique
as expressões o máximo possível. Respostas podem ser expressas em termos das quatro
operações aritméticas básicas, raízes, potências e fatorial (mas não símbolos combinato-
riais).
Questões:
1. [1pt]Considere o seguinte mapa de ruas:
A • • • • •
• • • • • •
• • • • • •
• • • • • • • •
• • •
• • C
Considerando somente movimentos para a direita e para baixo, de quantas formas
distintas podemos sair do ponto A e alcançar o ponto C?(
8
3
)
×
(
4
2
)
= 336
2. [11/2pt]Considere uma máquina caça-níqueis com quatro slots, como abaixo:
Ao ativarmos a alavanca, cada slot é preenchido aleatoriamente com um dos seguintes
símbolos:
{♠,♣,�,♥,♦,4}
O apostador é premiado quando a sequência sorteada satisfaz uma das seguintes
condições:
• todos os símbolos da sequência sorteada são distintos
• todos os símbolos da sequência sorteada são iguais
Determine:
(a) quantas sequências distintas podem ser sorteadas?
64 = 1296
1
(b) qual a chance de um apostador ganhar nessa máquina caça-níqueis ativando a
alavanca uma única vez?
• Número de sequências com o mesmo símbolo: 6
• Número de sequências com símbolos distintos: 6× 5× 4× 3 = 360
• Número de sequências premiadas: 6 + 360 = 366
• Chance de ser sorteado na máquina com uma aposta: 366
1296
≈ 28, 24%
3. [1pt]Dados 10 livros de português, 8 de matemática, 8 de química e 7 de física, qual a
quantidade mínima de livros que devemos retirar (sem olhar) para que tenhamos
certeza que retiramos 5 livros de uma mesma disciplina?
17 livros.
4. [1pt]Quantas soluções em inteiros não-negativos há para
x+ y + z = 10
onde x < 3?
Contaremos todas as soluções para a equação sem restrição e vamos depois subtrair
as soluções onde x ≥ 3.(
10 + 3− 1
3− 1
)
−
(
7 + 3− 1
3− 1
)
=
(
12
2
)
−
(
9
2
)
= 30
5. [1pt]Quantos anagramas da palavra MARMOTA satisfazem ambas as condições abaixo?
(a) o anagrama termina com a letra R;
(b) as duas letras M ocorrem juntas.
5!
2!
=
120
2
= 60
6. [1pt]Seja A = {1, 3, 5, 7, 9, 11} e B = {a, b, c}. Quantas funções totais sobrejetoras do tipo
A→ B existem?
1 · 36 − 3 · 26 + 3 · 16 + 1 · 06 = 729− 192 + 3 = 540
7. [1pt]Determine a função geradora ordinária para a sequência
(1, 3, 5, 7, 9, 11, 13, 15, . . . )
isto é, (an) = 2n+ 1
2x
(1− x)2 +
1
(1− x) =
1 + x
(1− x)2
2
8. [1pt]Determine o coeficiente de a2b2c3d1 na expansão da seguinte expressão:
(a+ b+ c+ d)8
8!
2!2!3!1!
= 1680
9. [11/2pt]Derive uma fórmula de contagem para palavras de tamanho k sobre o alfabeto
{↑, ↓,←,→}
tal que
• o símbolo ← ocorre um número par de vezes (lembre que 0 é par);
• o símbolo → ocorre um número ímpar de vezes;
• os símbolos ↑ e ↓ podem ocorrem um número arbitrário de vezes (inclusive
nenhuma vez).
Função geradora exponencial (inicial):(
ex + e−x
2
)(
ex − e−x
2
)
e2x
Função geradora exponencial (após simplificação):
1
4
(e4x − 1)
Fórmula de contagem:[
xk
k!
]
1
4
(e4x − 1) = 4k−1 −
{
1
4
se k = 0
0 se k > 0
Uso do professor (não preencher)
Questão: 1 2 3 4 5 6 7 8 9 Total
Pontos: 1 11/2 1 1 1 1 1 1 11/2 10
Nota:
3