Universidade Estadual da Paraı́ba

Centro de Ciências e Tecnologia

Mestrado Profissional em Matemática em Rede Nacional
Componente Curricular: MA12 - Matemática Discreta
Professora: Diana Maia

Avaliação 2 - 2022.1 Data: 10/06/2022

Aluno: Nota:

1. Uma urna contém 10 bolas, das quais 6 são brancas. Dois jogadores - A e B - tiram bolas
da urna sucessivamente: primeiro A, depois B, depois A de novo e assim por diante. O
vencedor é o primeiro a tirar uma bola branca. Determine a probabilidade de vitória de
cada jogador se

(a) (1,0) cada bola for recolocada na urna após ser retirada.

(b) (1,0) as bolas retiradas não forem recolocadas na urna.

Solução:

(a) Se as retirada forem feitas com reposição, então o jogador A pode vencer nas rodadas
ı́mpares e ele ganhará na rodada 2n + 1, n ≥ 0, se saı́rem bolas que não são brancas
nas 2n primeiras retiradas e bola branca na (2n + 1)-ésima retirada. Assim, a
probabilidade de que o jogador A seja o vencedor na (2n + 1)-ésima retirada é
 2n  n
4 6 4 3
P2n+1 = · = · ,
10 10 25 5
para n ≥ 0. Assim, a probabilidade de o jogador A ganhar o jogo é
∞ ∞  n
X X 4 3
P2n+1 = ·
n=0 n=0
25 5
∞   n
3X 4
=
5 n=0 25
3 1
= · 4
5 1 − 25
3 25 5
= · = .
5 21 7
 Consequentemente, a probabilidade de o jogador B ganhar é

5 2
1− = .
7 7

(b) Se as bolas retiradas não forem recolocadas na urna, então o número máximo de
rodadas é 5, pois temos apenas 4 bolas que não são brancas. O jogador B só pode
ganhar na segunda ou na quarta retirada. E neste caso, ele ganhará

• na segunda rodada se sair um bola não branca na primeira retirada e branca

na segunda e a probabilidade de que isto aconteça é

4 6 4
· = .
10 9 15

• na quarta rodada se as três primeiras bolas não forem brancas, mas a quarta
sim. Neste caso, a probabilidade é

4 3 2 6 2
· · · = .
10 9 8 7 70

Assim, a probabilidade de que o jogador B ganhe é

4 2 31
+ = ,
15 70 105

de onde concluı́mos que a probabilidade de o jogador A ganhar é

31 74
1− = .
105 105

2. Considere, para n ≥ 0 a recorrência

xn+2 = 4xn + 6 · 2n ,

com x0 = 2 e x1 = 4.

(a) (1,5) Resolva a recorrência acima.

(b) (1,5) Mostre por indução que o xn obtido no item anterior é, de fato, a solução da
recorrência.

Solução:
(a) Inicialmente vamos encontrar a solução da recorrência homogênea

an+2 = 4an .

A equação caracterı́stica associada é

r2 − 4 = 0

que tem como raı́zes r1 = −2 e r2 = 2. Logo, a solução da recorrência homogênea

é da forma
an = C1 (−2)n + C2 2n .

Agora, vamos testar agora uma solução para a recorrência não homogênea da forma

bn = a + bn2n .

Temos

a + b(n + 2)2n+2 − 4(a + bn2n ) = 6 · 2n

−3a + 8b2n = 6 · 2n

de onde concluı́mos que a = 0 e b = 43 . Assim, a solução da recorrência é

3n 2n
xn = C1 (−2)n + C2 2n + , n ≥ 0.
4

Considerando as condições iniciais x0 = 2 e x1 = 4, temos

3 · 0 · 20

0 0
C (−2) + C 2 + =2

1 2
 
4


  C1 + C2 = 2
⇒
 1
 −2C1 + 2C2 = 5
 C1 (−2)1 + C2 21 + 3 · 1 · 2 = 4


 2
4
3 13
o que implica que C1 = 8
e C2 = 8
. Portanto, a solução da recorrência é

3 13 n 3n 2n
xn = (−2)n + 2 + , n ≥ 0,
8 8 4

ou
1
xn = [3 · (−2)n + 13 · 2n + 6n · 2n ] , n ≥ 0.
8
 (b) Queremos mostrar pelo princı́pio de indução matemática que
1
xn = [3 · (−2)n + 13 · 2n + 6n · 2n ] , n ≥ 0.
8
Para n = 0 e n = 1 a igualdade vale, pois

 1 [3 · (−2)0 + 13 · 20 + 6 · 0 · 20 ] = 2
8
 1 [3 · (−2)1 + 13 · 21 + 6 · 1 · 21 ] = 4.
8

Suponhamos que a igualdade valha para n e n + 1, sendo n ≥ 0 escolhido ao acaso.

Neste caso,
1
xn = [3 · (−2)n + 13 · 2n + 6n · 2n ]
8
1
3 · (−2)n+1 + 13 · 2n+1 + 6(n + 1) · 2n+1

xn+1 =
8
e queremos mostrar que
1
3 · (−2)n+2 + 13 · 2n+2 + 6(n + 2) · 2n+2 .

xn+2 =
8
De fato,
1
xn+2 = 4 · [3 · (−2)n + 13 · 2n + 6n · 2n ] + 6 · 2n
8
1
= [3 · 4 · (−2)n + 13 · 4 · 2n + 6n · ·2n ]
8
1
3 · (−2)n+2 + 13 · 2n+2 + 6(n + 2) · 2n+2 .

=
8
Assim, pelo princı́pio de indução matemática, a relação vale para todo n ≥ 0.

3. Considere um dominó construı́do usando os números 0, 1, . . . , n.

(a) (1,0) Quantas peças tem esse dominó se n = k, k ∈ {0, 1, 2, 3, . . . }?

(b) (1,0) É bem sabido que se n = 6, o dominó tem 28 peças. Se considerarmos n = 8,

qual é a taxa de aumento do número de peças?

Solução:

(a) Para n = 0, há uma única peça. Para n ≥ 2, há k + 1 peças com números iguais.
Quanto aos diferentes, há Ck+1,2 peças. Logo, há
(k + 1)! (k + 1)k + 2(k + 1)
Ck+1,2 + k + 1 = +k+1=
(k − 1)!2! 2
 ou seja, se n = k, o dominó terá
(k + 1)(k + 2)
.
2
(8+1)(8+2)
(b) Se n = 8, teremos 2
= 45. Assim, a taxa de aumento foi de
45 − 28
= 0.6071429,
28
ou seja, aumenta aproximadamente 60,71%.

4. (1,0) Qual é o número de soluções inteiras e positivas de

x1 + x2 + x3 + x4 + x5 < 12?

Solução: Se x1 + x2 + x3 + x4 + x5 < 12, então existe f , inteiro e positivo tal que

x1 + x2 + x3 + x4 + x5 + f = 12. Sejam yi = xi − 1, i = 1, 2, 3, 4, e g = f − 1. Então, o
número de soluções inteiras e positivas de

x1 + x2 + x3 + x4 + x5 < 12

é o mesmo número de soluções inteiras e não negativas de

y1 + 1 + y2 + 1 + y3 + 1 + y4 + 1 + y5 + 1 + g + 1 = 12

y1 + y2 + y3 + y4 + y5 + g = 6,

que é
11! 11 · 10 · 9 · 8 · 7
P R6+6−1,6,6−1 = = = 462.
6!5! 5·4·3·2

5. (1,0) Se (an ) é uma progressão aritmética de termos positivos, prove que (bn ) definida
por bn = ean é uma progressão geométrica.
Solução: Sendo (an ) é uma progressão aritmética de termos positivos, existe r positivo
tal que an+1 − an = r. Assim,
bn+1 ean+1
= an = ean+1 −an = er .
bn e
Ou seja, (bn ) é uma progressão geométrica de razão er .
6. (1,0) Mostre que em uma reunião de n pessoas há sempre 2 com o mesmo número de
conhecidos.
Solução: Se há n pessoas, o número de conhecidos varia de 0 (não conhece ninguém) a
n − 1 (conhece todas as demais pessoas excluindo a si mesmo). No entanto, 0 e n − 1 não
podem ocorrer simultaneamente, pois não pode haver alguém que não conhece ninguém
e alguém que conhece todo mundo. Logo, o número de conhecidos de alguém deve
estar no conjunto {0, 1, . . . , n − 2} ou {1, 2, . . . , n − 1}. Em ambos os casos, há n − 1
possibilidades. Como há n pessoas, pelo Princı́pio das Gavetas, há pelo menos duas
pessoas com o mesmo número de conhecidos.