p1_1b_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 
1a Prova 29/05/2014 
Nome:____________________________________________________________ 
__________________________________________________________________ 
 
1 – Encontrar o número de soluções em inteiros não-negativos de 
 
21xxxxxx 654321 =+++++ , 
 
nas quais exatamente 3 incógnitas são nulas. 
(Exemplo 3.7) 
 
2 – De quantos modos podemos separar 22 objetos distintos em 7 grupos, sendo 
2 grupos com 3 objetos, 3 grupos com 4 objetos e 2 grupos com 2 objetos? 
(4ª lista, ex. 24) 
 
3 – Quantos números naturais de 6 algarismos podemos formar, de modo que 
cada número seja formado por 3 pares distintos de algarismos iguais? 
(6ª lista, ex. 15) 
 
4 – Para todo inteiro n , a função u(n) é definida por 
 
1u(1) = 
5u(2) = 
)2u(n2)1u(nu(n) −+−= , 
 
para todo 2n > . Prove, usando o princípio da indução, que nn )1(2u(n) −+= . 
(Exemplo 1.8) 
 
Tempo de prova: 1 h 40 min 
 
 
 
BOA PROVA 
 
 
 
 
 
 
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
 
p
1pnCf +−= 





 −+
−=




−
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,
 
 
GABARITO 
 
1 – Devemos contar o número de soluções em inteiros positivos de 
 
21yyy 321 =++ , 
 
e multiplicar pelo número de escolhas das três incógnitas que terão valor nulo. 
Assim, temos 
 
3
6
21
02
3
6
13
121 CCCC N ⋅=⋅=
−
−
 . 
 
2 – Temos que: 
 
Escolha dos 3 objetos para o primeiro grupo: 22,31 Cn = 
Escolha dos 3 objetos para o segundo grupo: 19,32 Cn = 
Escolha dos 4 objetos para o terceiro grupo: 16,43 Cn = 
Escolha dos 4 objetos para o quarto grupo: 12,44 Cn = 
Escolha dos 4 objetos para o quinto grupo: 8,45 Cn = 
Escolha dos 2 objetos para o sexto grupo: 4,26 Cn = 
Escolha dos 2 objetos para o sétimo grupo: 2,27 Cn = 
 
 
 Pelo princípio multiplicativo, teremos 
 
2,24,28,412,416,419,322,3 CCCCCCCN' ⋅⋅⋅⋅⋅⋅= 
 
0!2!
2!
2!2!
4!
!44!
8!
!84!
12!
12!4!
16!
16!3!
19!
19!3!
22!
 
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
= 
 
232 )(2!)(4!)(3!
22!
 
⋅⋅
= 
 
 Como não há distinção entre os 2 grupos que contêm 3 objetos cada, não 
há distinção entre os 3 grupos que contêm 4 objetos cada e não há distinção entre 
os 2 grupos que contêm 2 objetos cada, devemos dividir o número de escolhas 
encontrado, temos que 
 
433 )!2()(4!)(3!
22!
!23!2!
N'N
⋅⋅
=
⋅⋅
= . 
3 – Pares distintos de algarismos iguais 
 
00 11 22 33 44 55 66 77 88 99 
 
Exemplos: 
1 3 3 2 1 2
1 1 3 3 2 2



 
 
Podemos fazer isso de 310C maneiras diferentes como estamos diante de grupos 
do tipo 
 
11 22 33 
 
devemos fazer a permutação 2,2,26P . 
O número de 6 algarismos, incluindo os que comecem por zero, nas 
condições dadas, é 
 
1 2,2,2
10,3 6N C .P= . 
 
Como existem 10 algarismos, um décimo dos números formados inicia-se por zero 
e devemos excluí-los por não serem considerados números de 6 algarismos. 
Assim, 
 
2,2,2 2,2,2
10,3 6 10,3
1N C P C P 9720
10
= − = . 
 
4 – Passo inicial: P(1) e P(2) são verdadeiras, pois 
)1(u1)1(2 11 ==−+ 
)2(u5)1(2 22 ==−+ 
 
Hipótese de indução: a relação nn )1(2u(n) −+= é válida para todo n , tal que 
kn2 ≤< . 
 Devemos provar que a relação vale para 1kn += . Temos que 
 
)1u(k2u(k)1)u(k −+=+ [ ]1k1kkk )1(22)1(2 −− −++−+= 
 
1kkk )1(2)1(22 −−⋅+−+⋅= 21k1k )1()1(2 −−+= −+ 1k1k )1(2 ++ −+= , 
 
o que comprova que 1)P(k + é válida. Dessa forma, pela segunda forma do 
princípio da indução matemática, a função u(n)é dada por nn )1(2u(n) −+= para 
qualquer inteiro 1n ≥ .