p3_1_2014

Prévia do material em texto

UERJ - Universidade do Estado do Rio de Janeiro 
Instituto de Matemática e Estatística 
Departamento de Matemática Aplicada 
Disciplina: Matemática Discreta 
Professor: Augusto César de Castro Barbosa 
3ª Prova 14/08/2014 
Nome:____________________________________________________________ 
__________________________________________________________________ 
 
 
1 – Usando funções geradoras, determine de quantas maneiras diferentes 
podemos escolher 12 latas de cerveja se existem 5 marcas diferentes. 
 
2 – Dentre os inteiros de 1 a 1.000.000, inclusive, quantos, não são quadrados 
perfeitos, cubos perfeitos e nem quartas potências perfeitas? 
 
3 – Provar, pelo princípio da indução matemática, que, para todo inteiro positivo 
n , 
 
nn
n 2
51
5
1
2
51
5
1F 





−
−




 +
= , 
 
onde 1F , 2F , ... é a sequência de Fibonacci. 
 
4 – Encontrar o número de soluções de 
 
1xxxx 4321 =+++ , 
 
em inteiros entre -3 e 3 inclusive. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
FORMULÁRIO 
 
 
n!12...2)1)(nn(nPn =⋅⋅⋅−−= . 
p)!(n
n!1))(p2)...(n1)(nn(nA pn,
−
=−−−−=
 . 
p)!(np!
n!
p!
A
C pn,pn,
−
==
 
pnn,pn, CC −=
 
1n
1pn
p
n CCR
−
−+= 
!!...nn!n!n
n!)n,...,n,nPR(n;
r321
r21 =
 
p
pm, m(AR) = 
1)!(n
n
n!(PC)n −==
 
∑
=
−
=+
n
0i
inii
n
n baCb)(a
 






−





−





−=
r21 p
11...
p
11
p
11m φ(m) 
∑∑∑
≤<<≤≤<≤=
+−=
nkji1
kji
nji1
ji
n
1i
in21 )AAn(A)An(A)n(A)A...An(A IIIUUU 
∑
≤<<<≤
−
npkji1
pkji )AAAn(A III +...+ )A...An(A1)( n211-n III− 






−++−+−=
n!
11)(...
3!
1
2!
1
1!
11n!D nn
 
∑
=
−−=
k
0i
p
ik,
i )ik(C1)(k)T(p,
 
 ...x
!r
1)r)...(u1u(u
...x
!3
)2)(u1u(u
x
!2
)1u(u
ux1x)(1 r32u ++−−++−−+−++=+ 
 
r
0r
x
r
u
∑
∞
=






=
 




=
>
+−−
=





0r, 1
0r, 
!r
1)r)...(u1u(u
r
u
 





 −+
−=




−
r 
1rn)1(
r 
n r
 
...
r!
x
...
4!
x
3!
x
2!
x
x1e
r432
x +++++++=
∑
=
−





−==
k
0i
ni )ik(
i
k)1(
k!
1k)T(n,
k!
1k)S(n,
 
p
1pnCp)f(n, +−= 
 
 
 
 
GABARITO 
 
 
1 – A função geradora ordinária que controla o número de latas de uma dada 
marca é 
 
1232 x...xxx1 +++++ . 
 
Como são 5 marcas, a resposta será o coeficiente de 12x na expansão 
 
5513
513
51232 )x1()x1(
x1
x1)x...xxx1( −−−=





−
−
=+++++ . 
 
Como 
 
∑
∞
=
−
−




−
=−
0r
r5 )x(
r 
5)x1( , 
 
o coeficiente de 12x é 
 
1820
!12
16...765
!4!12
!16
12
16
12 
1125)1(
12 
5 12
=
⋅⋅⋅⋅
==





=




 −+
=−




−
 . 
 
 
2 – A {1,2,3, ,1000000}= K 
 
 1A {x A|x é quadrado perfeito}= ∈ 
 2A {x A|x é cubo perfeito}= ∈ 
 3A {x A|x é quarta potência perfeita}= ∈ 
 
Mas 3 1A A⊂ . Logo, 
 
1 2 3 1 2n n(A) n(A A A ) n(A) n(A A )= − ∪ ∪ = − ∪ 
 1 2 1 2n(A) [n(A ) n(A ) n(A A )]= − + − ∩ 
 1 2 1 2n(A) n(A ) n(A ) n(A A )= − − + ∩ 
 
6
1n(A ) 10 1000= = 
3 6
2n(A ) 10 100= = 
6 6
1 2n(A A ) 10 10∩ = = 
 
n 1000000 1000 100 10 998910= − − + = 
 
 
3 – 
n n
n
1 1+ 5 1 1- 5F = -
2 25 5
   
   
   
 
 
(i) PI: 1
1 1 5 1 1 5F
2 25 5
   + −
= −   
   
 
 
1 2 5(1 5 1 5) 1
2 5 2 5
= + − + = = 
 
1F 1= 
2 2
2
1 1 5 1 1 5F
2 25 5
   + +
= −   
   
 
 
1 4 5(1 2 5 5 1 2 5 5 1
4 5 4 5
= + + − + − = = 
 
2F 1= 
 
(ii) HI: 
n n
n
1 1+ 5 1 1- 5F = -
2 25 5
   
   
   
, 1 n k≤ ≤ 
 
(iii) Devemos mostrar que a fórmula é válida para n = k + 1 
 
k k k 1 k 1
k 1 k k 1
1 1 5 1 1 5 1 1 5 1 1 5F F F
2 2 2 25 5 5 5
− −
+ −
       + − + −
= + = − + −       
       
 
 
k 1 k 1
k 1
1 1 5 1 5 1 1 5 1 5F 1 1
2 2 2 25 5
− −
+
       + + − −
= ⋅ + − ⋅ +       
       
 
 
k 1 k 1
1 1 5 3 5 1 1 5 3 5
2 2 2 25 5
− −
       + + − −
= ⋅ − ⋅       
       
 
 
k 1 2 k 1 2
1 1 5 1 5 1 1 5 1 5
2 2 2 25 5
− −
       + + − −
= ⋅ − ⋅       
       
 
 
k 1 k 1
1 1 5 1 1 5
2 25 5
+ +
   + −
= −   
   
 
 
Assim, pelo PIM, provamos que a fórmula é válida para todo *n Z+∈ . 
 
4 – 1 2 3 4x x x x 1+ + + = 
 
Com 13 x 3− ≤ ≤ . 
 
Devemos somar 4 a cada xi. Temos então que 
 
1 2 3 4x 4 x 4 x 4 x 4 1 16+ + + + + + + = + 
 
1 2 3 4y y y y 17+ + + = , 
 
onde i iy x 7= + , com a restrição iy 7≤ . 
 
Queremos então encontrar a solução de 
 
1 2 3 4y y y y 17+ + + = (*) 
 
com iy 7≤ . Definiremos o conjunto Ai como o conjunto das soluções de (*) com 
iy 7≤ . Estamos interessados em contar o número de soluções que estão fora da 
união das Ai’s. 
 
4 1 3
17 1 16n(A) C C−−= = 
 
1n(A ) ?= 
 
1 2 3 4y 7 y y y 17 7− + + + = − 
 
1 2 3 4µ µ µ µ 10+ + + = ; 1 1µ y 7= − 
 
4 1 3
1 10 1 9n(A ) C C−−= = 
 
Assim, 
 
6
1 2 3 9n(A ) n(A ) n(A ) C= = = 
 
1 2 1 3 1 4 2 3n(A A ) n(A A ) n(A A ) n(A A )∩ = ∩ = ∩ = ∩ 
 2 4 3 4n(A A ) n(A A ) 0= ∩ = ∩ = 
 
Exemplo: 1 2 3 4y 7 y 7 y y 17 14− + − + + = − 
 
1 2 3 4µ µ µ µ 3+ + + = 
 
1 2n(A A ) 0∩ = 
 
Portanto, 
 
1 2 3 4n n(A) n(A A A A )= − ∪ ∪ ∪ 
 
 
3 3
16 9C 4C= − , 
 
onde 
 
1 2 3 1 2 4 1 3 4n(A A A ) n(A A A ) n(A A A )∩ ∩ = ∩ ∩ = ∩ ∩ 
 
 2 3 4n(A A A ) 0= ∩ ∩ =