p1_1a_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 – Determine o valor de ∏
=






+
−
n
1i
21)(i
11 . 
(2ª lista, ex. 2c) 
 
2 – Uma fila tem 24 cadeiras, nas quais devem sentar-se 10 meninas e 14 
meninos. De quantos modos isso pode ser feito se 2 meninas não devem ficar em 
cadeiras contíguas? 
(4ª lista, ex. 20) 
 
3 – De quantas maneiras pode-se escolher 3 números distintos do conjunto 
,50}{1,2,3,...A = de modo que sua soma seja um múltiplo de 3? 
(Exemplo 2.20) 
 
4 – Use o princípio de indução matemática para provar a desigualdade 
 
∏
=
<
n
1j
n j2 , para 4n ≥ . 
 
(3a lista, ex. 2b) 
 
 
 
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 – =





+
+
=





+
+
=





+
− ∏∏∏
===
n
1i
2
n
1i
2
2n
1i
2 1)(i
)2i(i
1)(i
i2i
1)(i
11 
 
2]1)(n...5432[
2)n(n...867564534231
+⋅⋅⋅⋅⋅
+⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅
= 
 
2]1)!(n[
2)(n...6543n)(...4321
+
+⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅
= 
 
1)(n2
2n
1)!1)(n(n!n
)!12)(n(n!n
2
1
]1)!(n[
2)!(n!n
2
1
2 +
+
=
++
++
=
+
+
= 
 
 
2 – Das 24 cadeiras, podemos escolher 10 de forma que não sejam consecutivas; 
isso pode se feito de 
 
10
15
10
11024 CCn == +− 
 
maneiras. Devemos então colocar cada menina em uma das 10 escolhidas, o que 
pode ser feito de !10P10 = maneiras. Finalmente. Devemos colocar os 14 meninos 
nas 14 cadeiras restantes.; podemos fazer isso de !14P14 = maneiras. Portanto, o 
número de maneiras de 10 meninas e 14 meninos sentarem em 24 cadeiras em 
fila, de modo que 2 meninas não sentem em cadeiras contíguas, é 
 
10
151410 C!14!10nPPN ⋅⋅=⋅⋅= . 
 
3 – Sejam os conjuntos: 
 
,48}{3,6,9,...1,2,3,...}k 3k,x|A{xB ===∈= 
...,49}{1,4,7,10,1,2,3,...},0k 1,3kx|A{xC ==+=∈= 
...,50}{2,5,8,11,1,2,3,...},0k 2,3kx|A{xD ==+=∈= 
 
Assim, temos que 
 
16n(B) = 
17n(C) = 
17n(D) = 
 
Encontramos múltiplos de 3 se realizamos as seguintes somas: 
 
a) 3 números quaisquer pertencentes a B � 560
!13!3
!16C16,3 == 
b) 3 números quaisquer pertencentes a C � 680
!14!3
!17C17,3 == 
c) 3 números quaisquer pertencentes a D � 680
!14!3
!17C17,3 == 
d) 1 elemento de cada conjunto � 4624171716CCC 17,117,116,1 =⋅⋅=⋅⋅ 
 
 Podemos escolher 3 números distintos de A , de modo a obter um múltiplo 
de 3, de 
 
6544CCCCCC N 17,117,116,117,317,316,3 =⋅⋅+++= . 
 
4 – (i) PI: 24161.2.3.4j2
4
1j
4 <⇒=< ∏
=
 
 
A desigualdade vale para n = 4. 
 
(ii) HI: kn4 , j2
n
1j
n ≤<< ∏
=
 
 
(iii) A partir da hipótese de indução devemos provar que a desigualdade vale para 
n = k +1. 
 
k 1 k
k k 1
j 1 j 1
j (k 1). j (k 1) 2 2
+
+
= =
= + > + >∏ ∏ . De fato, pois 
 
k k 1(k 1)2 2 k 1 2 k 1,++ > ⇒ + > ⇒ > 
 
o que está correto, uma vez que k 4≥ . Logo, para n 4≥ , 
 
n
n
j 1
2 j 
=
< ∏ .