Lista 1

Prévia do material em texto

DEPARTAMENTO DE MATEMA´TICA PUC-RIO
MAT1310 – MATEMA´TICA DISCRETA – 2012.1 – LISTA DE EXERCI´CIOS I
1. Sejam dadas as seguintes proposic¸o˜es:
p : “Voceˆ esta´ em Seul”.
q : “Voceˆ esta´ em Gwangju”.
r : “Voceˆ esta´ na Coreia do Sul”.
(a) Traduza a proposic¸a˜o seguinte para s´ımbolos de lo´gica formal: Se voceˆ na˜o esta´ na
Coreia do Sul, enta˜o voceˆ na˜o esta´ em Seul ou em Gwangju.
(b) Traduza a seguinte proposic¸a˜o formal para o portugueˆs comum:
q ⇒ (r ∧ (∼ p)).
2. Sejam dadas as seguintes proposic¸o˜es:
p : “Amauri esta´ com fome”.
q : “A geladeira esta´ vazia”.
r : “Amauri esta´ zangado”.
(a) Use os conectivos para traduzir a proposic¸a˜o seguinte para lo´gica formal: Se Amauri
esta´ com fome e a geladeira esta´ vazia, enta˜o Amauri esta´ zangado.
(b) Considerando todos as possibilidades de valores lo´gicos (F ou V) para as pro-
posic¸o˜es p, q e r, determine o valor lo´gico da proposic¸a˜o do item (a). (Ou seja,
construa a tabela verdade para a proposic¸a˜o do item (a).)
(c) Suponha que a proposic¸a˜o dada em (a) seja verdadeira, e suponha tambe´m que
Amauri na˜o esta´ zangado e a geladeira esta´ vazia. Amauri esta´ com fome? Justi-
fique sua resposta.
3. Sejam p e q sa˜o proposic¸o˜es. Dizemos que p e´ mais forte que q se p⇒ q.
Qual e´ a proposic¸a˜o mais forte? Explique.
(i) Manchester United e´ o melhor time de futebol da Inglaterra.
(ii) Manchester United e´ o melhor time de futebol da Europa.
4. Quais das proposic¸o˜es abaixo representam ∼ A sabendo que A e´ a proposic¸a˜o: “Se e´
caro, enta˜o a comida e´ boa e o servic¸o e´ excelente”?
(a) E´ caro, e, e´ falso que a comida e´ boa ou o servic¸o e´ excelente.
(b) Se na˜o e´ caro, enta˜o a comida na˜o e´ boa ou o servic¸o na˜o e´ excelente.
(c) E´ caro, e, a comida e´ ruim ou o servic¸o tambe´m.
(d) Na˜o e´ caro ou a comida e o servic¸o sa˜o ruins.
(e) E´ caro e a comida e´ ruim, ou enta˜o e´ caro e o servic¸o na˜o e´ excelente.
5. Treˆs pessoas prestam depoimento e o que dizem esta´ registrado a seguir:
Bernardo : “Joa˜o e´ culpado e Saul e´ inocente.”
Joa˜o : “Se Bernardo e´ culpado, Saul tambe´m e´ culpado.”
Saul : “Eu sou inocente, mas, pelo menos, um dos outros e´ culpado.”
A partir desses depoimentos, pede-se:
(a) Identifique os inocentes e os culpados, supondo que todos os depoimentos tenham
sido verdadeiros.
(b) Identifique os mentirosos, admitindo-se que todos sejam inocentes.
6. Prove, caso seja verdadeira ou exiba um contra-exemplo caso seja falsa as afirmac¸o˜es a
seguir:
(a) A soma de dois inteiros ı´mpares e´ um inteiro par.
(b) O produto de dois inteiros ı´mpares e´ um inteiro ı´mpar.
(c) Se a soma de dois nu´meros e´ um irracional enta˜o pelo menos um deles e´ irracional.
(d) Um nu´mero e´ mu´ltiplo de 3 se e so´ se seu quadrado for mu´ltiplo de 3.
(e)
√
3 e´ um nu´mero irracional.
(f) O produto de dois irracionais e´ um irracional.
(g) A soma de dois nu´meros primos e´ um nu´mero primo.
(h) Se o cubo de um nu´mero e´ mu´ltiplo de 2 enta˜o este nu´mero e´ mu´ltiplo de 2.
(i) Todo inteiro mu´ltiplo de 9 e´ mu´ltiplo de 3.
(j) A soma de treˆs inteiros consecutivos e´ um inteiro mu´ltiplo de 3.
(k) Seja (xn)n∈N uma sequeˆncias de nu´meros reais. Se xn < xn+1 ∀n, enta˜o ∃m tal que
xm e´ positivo.
7. Dados os predicados:
P (x) = “x e´ par”.
Q(x) = “x e´ menor que 5”.
R(x) = “x e´ primo”.
determinar o maior subconjunto de U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} onde cada proposic¸a˜o
abaixo e´ verdadeira:
(a) P (x)⇒ Q(x) ∨R(x)
(b) (∼ P (x)⇔ Q(x)) ∧R(x)
8. Sejam os predicados P (x, y) : x2 = y e Q(x, y) : x + y ≥ 0, onde as varia´veis x e
y esta˜o no universo U = {−1, 0, 1}. Determine o valor lo´gico das sentenc¸as abaixo
(justificando):
(a) (∀x)(∃y)P (x, y).
(b) (∃x)(∀y)Q(x, y).
9. Considerando verdadeiro que: “Nenhum surfista e´ estudioso” e “Algum informa´tico e´
estudioso”. Pode-se corretamente concluir que (demonstre):
a) Todo informa´tico e´ surfista.
b) Todo informa´tico na˜o e´ surfista.
c) Algum informa´tico e´ surfista.
d) Algum informa´tico na˜o e´ surfista.
e) Nenhum informa´tico e´ surfista.
10. Prove por induc¸a˜o:
(a) 1 + 3 + 5 + · · ·+ (2n− 1) = n2, ∀n ≥ 1.
(b) 1 + 2 + 3 + · · ·+ n = n(n+1)
2
,∀n ≥ 1 (Nu´meros triangulares).
(c) 1 + 2 + 22 + · · ·+ 2n−1 = 2n − 1,∀n ≥ 1.
(d) 12 + 22 + 32 + · · ·+ n2 = 1
6
(2n3 + 3n2 + n), ∀n ≥ 1 (Nu´meros piramidais).
(e) 13 + 23 + 33 + · · ·+ n3 = 1
4
n2(n+ 1)2, ∀n ≥ 1.
(f) 1 · 2 + 2 · 3 + 3 · 4 + · · ·+ n · (n+ 1) = 1
3
n(n+ 1)(n+ 2), ∀n ≥ 1.
(g) 2 + 6 + 18 + ...+ 2 · 3n = 3n+1 − 1,∀n ∈ N.
(h) 1
2!
+ 2
3!
+ 3
4!
+ · · ·+ n
(n+1)!
= 1− 1
(n+1)!
,∀n ≥ 1.
(i) 1 · 1! + 2 · 2! + 3 · 3! + · · ·+ n · n! = (n+ 1)!− 1,∀n ≥ 1.
(j) n < 2n,∀n ∈ N. (Dica: comece a recursa˜o de 1, e trate n = 0 a parte.)
(k) 2n < n!,∀n ≥ 4.
(l) 7n + 2 e´ divis´ıvel por 3,∀n ∈ N.
(m) n2 > n+ 1, ∀n > 1.
(n) (1 + x)n ≥ 1 + nx, ∀x > 0,∀n ∈ N (Desigualdade de Bernoulli).
(o) Seja H(n) = 1+ 1
2
+ 1
3
+ · · ·+ 1
n
. Prove que: H(2n) ≤ 1 + n
2
,∀n ≥ 3. (Divergeˆncia
da se´rie harmoˆnica).
11. Prove que ∀n > 0,
(
n∑
k=1
k
)2
=
n∑
k=1
k3.
12. Quantas soluc¸o˜es possui a desigualdade x + y + z ≤ 10 , sendo x, y, z inteiros na˜o
negativos? (Deˆ uma resposta nume´rica expl´ıcita.)
13. Determine o nu´mero de soluc¸o˜es inteiras da inequac¸a˜o x+y+z+t ≤ 25 com as restric¸o˜es:
x > 0, y ≥ −5, z ≥ 0, t > 3.
14. Quantas soluc¸o˜es possui a equac¸a˜o x + y + z = 21 , sendo x, y, z nu´meros ı´mpares
positivos?
15. Determine o nu´mero de soluc¸o˜es inteiras positivas da equac¸a˜o x · y · z · t = 512.
16. Determine o nu´mero de soluc¸o˜es da equac¸a˜o x · y · z · t = 1024 , sendo x, y, z, t inteiros
maiores ou iguais a 2.
17. De quantos modos pode-se repartir 100 moedas iguais entre 5 pessoas de modo que cada
pessoa receba pelo menos duas moedas?
18. Considere um torneio em que cada um dos n jogadores joga contra todos os outros e
cada jogador ganha pelo menos uma partida. Mostre que, ao final do torneio, existem
pelo menos dois jogadores com o mesmo nu´mero de vito´rias.
19. Mostre que em qualquer conjunto de 52 inteiros existe um par de inteiros cuja soma ou
cuja diferenc¸a e´ divis´ıvel por 100.
20. De um baralho comum (52 cartas) sacam-se sucessivamente e sem reposic¸a˜o treˆs cartas.
Quantas sa˜o as extrac¸o˜es nas quais a primeira carta e´ de copas, a segunda e´ um rei e a
terceira na˜o e´ uma dama?
21. Uma part´ıcula estando no ponto (x, y) do plano cartesiano pode se movimentar para o
ponto (x+ 1, y) ou para o ponto (x, y + 1).
(a) Quantos sa˜o os trajetos poss´ıveis que esta part´ıcula pode percorrer do ponto (0, 0)
ate´ o ponto (10, 3)?
(b) Escolhendo-se ao acaso um dos trajetos definidos no item (a), qual e´ a probabilidade
de que ele passe pelo ponto (2, 2)?
22. Tem-se uma rede de caminhos conforme a figura abaixo. Do ponto O partem 216 homens.
Metade parte na direc¸a˜o l e metade na direc¸a˜o m. Ao chegar ao primeiro cruzamento
cada grupo de divide: uma metade segue na direc¸a˜o l, a outra na direc¸a˜o m. Numeremos
as linhas e os cruzamentos a partir do zero; assim, o ponto O e´ o zero-e´simo cruzamento
da linha zero e o ponto A e´ o primeiro cruzamento de linha 4. Seja B um ponto que
corresponde ao quinto cruzamento da linha 10. Partindo de O, quantos homens chegam
a B?
23. Demonstre que
p
(
n
p
)
= n
(
n− 1
p− 1
)
.
24. Demonstre que(
n
0
)
−
(
n
1
)
+
(
n
2
)
+ · · ·+ (−1)n−1
(
n
n− 1
)
+ (−1)n
(
n
n
)
= 0.
25. Utilize o resultado do exerc´ıcio anterior e a propriedade da soma dos elementos das
linhas para concluir que(
n
0
)
+
(
n
2
)
+
(
n
4
)
+ · · · =
(
n
1
)
+
(
n
3
)
+
(
n
5
)
+ · · · = 2n−1.
isto e´, na n-e´sima linha, a soma dos elementos nas colunas pares da´ 2n−1, e a soma dos
elementos nas colunas ı´mpares tambe´m.
26. Determine o valor das somas seguintes:
(a) 1 · 3 + 2 · 5 + 3 · 7 + 4 · 9 + · · ·+ 100 · 201;
(b) 1 · 3 + 2 · 4 + 3 · 5 + · · ·+ 99 · 101;
(c) 1 · 2 · 3 + 2 · 3 · 4 + 3 · 4 · 5 + · · ·+ 98 · 99 · 100.
27. Determine o coeficiente de x11 no desenvolvimentode
(
x5 +
2
x3
)7
.
28. Determine o coeficiente de a3b3c3 no desenvolvimento de (a+ b+ c)9.
29. Determine o coeficiente de x15y10 no desenvolvimento de (2x5 + y2/2)8.
30. Sejam n e m inteiros naturais e defina S(n) =
∑n
k=0
(
m+k
k
)
. Considere o predicado p(n):
“S(n) =
(
m+n+1
n
)
”.
(a) Prove a propriedade p(n) por induc¸a˜o.
(b) Calcule o valor da soma:
(
200
10
)
+
(
201
11
)
+
(
202
12
)
+ . . .+
(
250
60
)
.
31. Considere a identidade, para n ≥ 1:
n∑
k=1
k ·
(
n
k
)
= n · 2n−1.
(a) Prove a identidade por induc¸a˜o.
(b) Prove a identidade a partir do binoˆmio de Newton para (1+x)n e da sua derivac¸a˜o.
32. Seja Fn o n-e´simo termo da sequeˆncia de Fibonacci definida por F0 = F1 = 1 e, para
n ≥ 2, Fn = Fn−1+Fn−2. Em particular, os primeiros termos sa˜o 1,1,2,3,5,8,13,21,34,. . .
Considere a soma S(n) =
∑n
k=1 F2k.
(a) Sabendo que S(n) e´ da forma S(n) = FX − Y , estabelec¸a uma fo´rmula para X em
func¸a˜o de n e um valor real constante para Y .
(b) Mostre por induc¸a˜o que a fo´rmula determinada no item anterior e´ correta.
33. Seja Fn o n-e´simo termo da sequeˆncia de Fibonacci. Mostre por induc¸a˜o que ∀n ∈
N, F 20 + F 21 + F 22 + · · ·+ F 2n = FnFn+1.
34. Seja Fn o n-e´simo termo da sequeˆncia de Fibonacci. E seja Sn =
∑n
k=1 Fk.
(a) Calcule S1, S2, S3, S4, S5 e expresse Sn em func¸a˜o de um u´nico Fk.
(b) Mostre por induc¸a˜o que sua fo´rmula e´ correta.
35. De quantas maneiras e´ poss´ıvel preencher de domino´s (isto e´, retaˆngulos 2 × 1) um
retaˆngulo 2× n? Encontre antes uma expressa˜o recursiva, e demonstre-a por induc¸a˜o.
36. Considere a sequeˆncia P (1) = 1 · 1, P (2) = 2 · 2 − 1 · 1, P (3) = 3 · 3 − 2 · 2 + 1 · 1,
P (4) = 4 · 4− 3 · 3 + 2 · 2− 1 · 1.
(a) Adivinhe uma lei geral para P (n).
(b) Prove por induc¸a˜o o que voceˆ apresentou no item anterior.
37. Seja S(n) = 9 · 100 + 9 · 101 + 9 · 102 + · · ·+ 9 · 10n−1.
(a) Escreva S(n) em termos de S(n− 1).
(b) Encontre uma fo´rmula fechada para S(n).
(c) Prove por induc¸a˜o o resultado encontrado no item anterior.
38. Nu´meros figurados podem ser definidos como sendo o nu´mero de pontos em uma certa
configurac¸a˜o geome´trica. Assim, os primeiros cinco nu´meros pentagonais sa˜o 1, 5, 12, 22, 35.
Os cinco primeiros esta˜o representados nas figuras abaixo
Seja xn o n-e´simo nu´mero pentagonal.
(a) Expresse recursivamente xn em func¸a˜o de xn−1.
(b) Encontre uma fo´rmula fechada para xn.
(c) Prove por induc¸a˜o o resultado encontrado no item anterior.
39. Queremos colocar bandeiras de treˆs tipos em um mastro de n metros de altura. Esta˜o
dispon´ıveis quantidades suficientes de bandeiras vermelhas (de 1 metro), azuis (de 2
metros) e verdes (tambe´m de 2 metros).
(a) Expresse recursivamente o nu´mero de maneiras distintas de embandeirar o mastro
em toda sua extensa˜o, sem folgas.
(b) Prove, por induc¸a˜o que este nu´mero e´ igual a 2
3
2n + 1
3
(−1)n.
40. Observe a sequeˆncia de figuras a seguir. Em cada uma delas as circunfereˆncias cortam-
se sempre em dois pontos e treˆs circunfereˆncias na˜o passam nunca pelo mesmo ponto.
Assim, se ha´ n circunfereˆncias, a colocac¸a˜o de mais uma acrescenta 2(n− 1) regio˜es a`s
ja´ existentes. Seja Rn o nu´mero de regio˜es em que n circunfereˆncias assim constru´ıdas
dividem um plano, enta˜o R1 = 2, R2 = 4, R3 = 8, R4 = 14.
Circunfereˆncias delimitando regio˜es do plano (inclusive a regia˜o externa)
(a) Expresse Rn em func¸a˜o de Rn−1.
(b) Encontre uma fo´rmula fechada para Rn.
(c) Prove por induc¸a˜o a fo´rmula que voceˆ obteve no item anterior.