Análise Combinatória - Prova 1 - 2013/2

Prévia do material em texto

Teoria dos Grafos e Análise Combinatória – Turma A – 2013/2
Prova 1 – 23 de Setembro de 2013 – Prof. Rodrigo Machado
Nome: GABARITO Cartão UFRGS:
Questões:
1. [11/2pt]Quantos anagramas da palavra MARMOTA começam com consoante?
6!
2!
+
6!
2!2!
+
6!
2!2!
= 6! = 720
2. [1pt]De quantas maneiras distintas 2 americanos, 3 espanhóis e 2 japoneses podem sentar
em fila, de modo que os de mesma nacionalidade sentem juntos?
3!× 2!× 3!× 2! = 144
3. [11/2pt]De quantas formas distintas podemos distribuir 12 objetos idênticos em 3 caixas
enumeradas garantindo que cada caixa possua no mínimo 2 objetos?(
(12− 6) + 3− 1
3− 1
)
=
(
8
2
)
= 28
4. [2pt]Considere uma máquina caça-níqueis com três slots:
Quando a alavanca é ativada, cada slot seleciona um dos seguintes itens:
{
, , , ,
}
Esta máquina dá prêmios quando:
• Os três símbolos sorteados são iguais.
• Os três símbolos são distintos e consecutivos no círculo abaixo, não importando
o sentido (horário ou anti-horário).
Responda:
(a) Qual a chance de um jogador ganhar um prêmio nessa máquina?
5 + 5 + 5
53
=
3
25
1
(b) Imagine uma outra máquina onde, ao invés de termos os dois critérios acima
para ganhar, tivéssemos somente um: que os três símbolos sorteados fossem
distintos (em qualquer ordem). Calcule a chance do jogador ganhar o prêmio
nesta segunda máquina, e compare com a da primeira máquina: ela é maior ou
menor?
5× 4× 3
53
=
12
25
As chances aumentam na segunda máquina.
5. [11/2pt]Calcule:
(a) A sequência codificada pela função geradora ordinária 1
(1−x)x
2.
(0, 0, 1, 1, 1, 1, . . .)
(b) A sequência codificada pela função geradora exponencial e2x + ex.
(2, 3, 5, 9, 17, 33, . . .), ou (an) = 2n + 1
6. [11/2pt]Imagine o jogo de apostas descrito abaixo:
Há 20 números distintos ao total. Cada jogador escolhe 4 números para formar sua
aposta. O sorteio é feito removendo ao acaso esferas numeradas (de 1 a 20) de um
globo, sem colocar a esfera de volta. A cada número retirado, é verificado se o número
está contido na aposta de algum jogador. Se for o caso, o prêmio é dividido entre
todos os jogadores cuja aposta contém o número. Se o número não estiver contido na
aposta de nenhum jogador, outro número é retirado, sendo esse processo é repetido
até que haja no mínimo um ganhador.
Imagine uma instância desse jogo, onde há 3 apostadores com as respectivas apostas
indicadas abaixo:
• Goku = {1, 5, 6, 7}
• Piccolo = {1, 2, 8, 9}
• Gohan = {3, 15, 19, 20}
Qual o número mínimo de esferas que precisam ser retiradas nessa instância do jogo
para termos certeza de que haverá no mínimo um ganhador?
A = (Goku ∪ Piccolo ∪ Gohan)
B = {1 . . . 20} − A
B = {4, 10, 11, 12, 13, 14, 16, 17, 18}
|B| = 9
Portanto, precisamos de no mínimo 10 esferas retiradas para garantirmos que haverá
alguma esfera do conjunto A presente no sorteio.
2
7. [1pt]Considere agora uma máquina caça-níqueis similar à da questão 4. Suponha que ela
atue sobre o mesmo conjunto de símbolos. A diferença está no fato desta máquina
possuir 7 slots, e no critério para ganhar: é necessário ter os cinco símbolos distintos
ocorrendo na sequência sorteada para que esta ganhe o prêmio.
Apresente a expressão que conta o número de sorteios premiados. A resposta pode
estar no formato [..](..) (método das funções geradoras) ou então como uma expressão
numérica (não é necessário calcular até o final, simplemente descreva a expressão em
termos de operações básicas e notação binomial).
Expressão por funções geradoras: [
x7
7!
]
(ex − 1)5
Expressão pela fórmula de funções sobrejetoras:
5∑
i=0
(−1)i
(
5
i
)
(5− i)7
Expressão por contagem de anagramas de palavras com repetição de letras (dois
casos: símbolos extras iguais ou diferentes):(
5
1
)
×
(
7
3, 1, 1, 1, 1
)
+
(
5
2
)
×
(
7
2, 2, 1, 1, 1
)
Uso do professor (não preencher)
Questão: 1 2 3 4 5 6 7 Total
Pontos: 11/2 1 11/2 2 11/2 11/2 1 10
Nota:
3