Apendice_A

Prévia do material em texto

APÊNDICEA
Muitas sugestões e 
comentários; algumas 
respostas
1.1 Desculpe, não há nenhuma sugestão 
para este problema; que poderia aca-
bar totalmente com o propósito! Con-
fie em si mesmo e continue pensando 
sobre isso. Você terá sucesso e quando 
tiver a resposta, terá certeza absoluta 
de que está certo — você não precisará 
da parte de trás do livro para te dizer!
2.1 Aqui está uma solução para o quebra-
-cabeça.
 Ao escrever suas instruções, dê nomes 
descritivos para as peças, tais como 
paralelogramo, quadrado e triângulo 
reto isósceles grande.
3.1 Para determinar se a|b é verdadeiro, 
veja se você consegue encontrar um 
inteiro x de modo que ax = b.
3.2 No problema anterior existem números 
inteiros a e b em que b|a é verdadeiro, 
mas a
b
 não é um inteiro.
3.3 Leia a Definição 3.6 com cuidado. 
Verifique cada número para ver se ele 
preenche todos os requisitos previstos 
na definição.
3.4 Sua definição para ≤ deve ficar assim:
 Sejam x e y inteiros. Dizemos que x 
é menor que ou igual a y (escrito x ≤ y) 
contanto que... 
em que ... representa uma condição en-
volvendo x, y e os números naturais.
  Depois de definir ≤, você pode usar 
este conceito para definir <, > e ≥.
3.5 Você precisa fazer duas coisas:
(1) Explicar por que os inteiros são 
números racionais. Você deve explicar 
por que, se x é um inteiro, então você 
pode encontrar inteiros a e b de modo 
que x = ab. Os inteiros a e b dependem 
de x e você pode encontrar valores 
simples para eles. Cuidado para não 
escolher b = 0.
(2) Explique por que alguns núme-
ros racionais não são inteiros. Tudo o 
2 Matemática discreta
que é necessário é que você encontre 
um número racional que não seja um 
inteiro.
3.6 O número 169 é quadrado. Como você 
convence alguém que isso é verdade? 
Você precisaria dizer-lhes sobre o nú-
mero 13.
 Aqui está a resposta completa:
 Um inteiro x é chamado quadrado 
perfeito desde que exista um inteiro tal 
que x = y2.
3.7 Sua resposta deve começar: “Um nú-
mero x é uma raiz quadrada do número 
y dado que...”
3.9 Use a notação d(A, B) para indicar a 
distância entre os pontos A e B. Deter-
mine uma relação entre d(A, B), d(B, 
C), e d(A, C) que determine se C está 
entre A e B.
3.10 O ponto médio de um segmento de 
linha AB é um ponto C no segmento, 
de modo que a distância de A a C seja 
igual a distância de C a B.
3.11 Resposta completa para (b): A pessoa 
A é a avó da pessoa B desde que A seja 
do sexo feminino e A seja parente de 
um dos parentes de B.
Alternativamente: Uma pessoa X é 
avó se X for do sexo feminino e X for 
mãe de alguém que também é mãe.
3.12 Para pequenos números, a coisa mais 
fácil a fazer é simplesmente escrever 
todas as possibilidades. Para números 
maiores, tente desenvolver um método 
melhor. Tente fatorar os números em 
números primos. A fatoração e os nú-
meros primos são discutidos em pro-
fundidade na Seção 39.
3.13 A resposta para (a) é melhor encon-
trada, começando com 2 e verificando 
cada número. Você deve encontrar a 
resposta rapidamente.
A parte mais difícil para (b) é es-
crever uma sub-rotina para verificar 
se, dados os inteiros a e b, a|b é ver-
dadeiro. Uma maneira de fazer isso é 
calcular a/b e, em seguida, arredondar 
para baixo, para o inteiro mais próxi-
mo que dá o inteiro c. Em seguida, ve-
rifique se ac = b. Preste atenção que 
esta ideia funciona bem quando a e b 
são positivos e isso é suficiente para o 
problema em questão. No entanto, se 
você planeja usar essa sub-rotina em 
outros projetos, vale a pena escrever 
uma sub-rotina que funcionará corre-
tamente para qualquer par de inteiros 
a e b.
4.1 Resposta para (a): Se x é um inteiro 
ímpar e y é um inteiro par, então xy é 
um inteiro par.
Resposta para (f): Se DABC ≅ 
DXYZ, então, a área de DABC é igual 
a área de DXYZ.
Sugestão para (g): Ao invés de es-
crever, “se a, b, e c são inteiros con-
secutivos...” expresse os inteiros como, 
digamos, n, n + 1 e n + 2.
4.2 Resposta para (a): Se B, então A é ver-
dadeiro (porque todos os quadrados 
são retângulos), mas as outras afirma-
ções são falsas.
Sugestão para (e): 1900 não foi um 
ano bissexto.
4.3 Existem muitas respostas corretas pos-
síveis. Por exemplo, a afirmação “Se 
(A) um animal, é um gato, então (B) ele 
é um mamífero” é verdadeiro, mas “Se 
(B) um animal é um mamífero, então 
(A) ele é um gato” é falso.
Agora crie seus próprios exemplos.
4.4 A afirmação “Se A, então B” é verda-
deira, a menos que A seja verdadeiro e 
B seja falso.
Uma afirmação “ou” é verdadeira, 
a menos que ambas as condições sejam 
falsas. Isto te diz quando “(não A) ou 
3Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
B” é verdadeiro e quando ele é falso. 
Compare para “Se A, então B.”
4.7 Para que tipo de triângulos o Teorema 
de Pitágoras se aplica?
4.8 Para que tipo de triângulos o Teorema 
de Pitágoras se aplica?
4.9 Uma distância é um número e linhas 
são infinitas. Em sua reescrita, use o 
termo segmento de linha.
4.10 Confira a anatomia do porquinho-da-
-índia.
M
ic
ha
el
 N
ew
m
an
/P
ho
to
 E
di
t, 
In
c.
4.11 O preceito é um e existe outro.
4.12 (a) Resposta completa: A soma dos pri-
meiros n números ímpares é n2.
(d) Sugestão: Rabisque como um lou-
co, mas mantenha um registro cuida-
doso de seus rabiscos.
(e) Sugestão: Tente este procedimento 
para um número pequeno de armários, 
digamos dez. Escrevendo - para fecha-
do e + para aberto, aqui está o que de-
vemos ver depois de cada rodada:
Rodada Padrão
1. -------------
2. -+-+-+-+-+
3. -+++---+++
4. -++-----++
5. -++-+---+-
6. -++-++--+-
7. -++-+++-+-
8. -++-+++++-
9. -++-++++--
10. -++-++++-+
5.1 Aqui está uma resposta completa:
Convertidos para a forma se-então, 
o problema pede para você provar: Se 
x e y são inteiros ímpares, então x + y 
é par.
Prova. Sejam x e y inteiros ímpares. 
Pela  definição  de  ímpar,  existe  um 
inteiro a de modo que x = 2a + 1. Da 
mesma forma, existe um inteiro de 
modo que y = 2b + 1. Portanto
 x + y = (2 a + 1) + (2b + 1)
 = 2a + 2b + 2 
 = 2 (a + b + 1)
Como a e b são inteiros, portanto a + 
b + 1. Portanto, pela definição de divi-
sível, x + y é divisível por 2. Portanto, 
pela definição de par, x + y é par.
5.2 A primeira linha da prova é: Seja x um 
inteiro ímpar e seja y um inteiro par.
A última linha da prova é: Portanto, 
x + y é ímpar.
5.3 O que você sabe: n = 2a + 1 para algum 
inteiro a. O que você precisa demons-
trar: –n = 2b + 1 para algum inteiro b. 
Descubra a relação entre a e b.
A primeira linha da sua prova deve 
ser lida: “Seja n um inteiro positivo 
ímpar”. A última linha da sua prova 
deve ser lida: “Portanto, -n é ímpar”.
5.4 Uma linha, no meio desta prova, é
xy = (2a)(2b) = 4ab = 2(2ab).
5.6 (2a + 1)(2b + 1) = 2(2ab + a + b) + 1.
5.7 Este é o corolário do Exercício 5.6.
5.8 Você pode expandir (2a + 1)3 e ver o 
que acontece. Alternativamente, se você 
resolveu o Exercício 5.6, pode aplicar 
esse resultado e evitar toda álgebra.
5.9 Pode ser mais trabalhoso, mas se você 
fizer o Exercício 5.11 primeiro, pode 
derivar isso como um corolário.
5.10 Veja a sugestão anterior.
5.11 Se você fez os dois problemas ante-
riores sem antes fazer esse, você pode 
usá-los para fazê-lo.
4 Matemática discreta
5.13 (⇒) Suponha que x seja ímpar. ... Por-
tanto x + 1 é par.
(⇐) Suponha que x + 1 seja par. ... 
Portanto x é ímpar. Truque algébrico: 
2b – 1 = 2(b – 1) + 1.
5.14 Aqui está a primeira parte da prova na 
íntegra:
(⇒) Suponha que x seja ímpar. En-
tão, há um número inteiro tal que x = 
2a +1. Seja b = a +1; note que b é um 
número inteiro. Observe que
2b – 1 = 2(a + 1) – 1 = 2a + 2 – 1 = 2a + 1 = x.
Portanto x = 2b – 1 para algum número 
inteiro b.
Aqui está um esboço para a segun-
da metade da prova.
Portanto x = 2b – 1 para algum nú-
mero inteiro b. Portanto x é ímpar.
5.16 O menor número inteiro positivo é 1 e 
a < b implica que b – a > 0. Certifique-
-se de provar as duas metades desta 
afirmação se e apenas se.
5.18 Quadrados perfeitos consecutivospo-
dem ser expressos como n2 e (n + 1)2 
para algum inteiro n.
5.19 Você sabe: a é o quadrado de algum 
inteiro. E se esse inteiro passa a ser ne-
gativo?
5.20 Use as Propriedades de Ordenação da-
das no Apêndice D.
5.22 2a + 1 = (a) + (a + 1).
5.23 Construa uma afirmação da forma “Se 
A ou B, então C” que é falsa, mas “Se 
A, então C” é verdadeira.
5.24 Temos certeza agora de que sempre que 
A é verdadeiro, B também é, e sempre 
que B é verdadeiro, A também é?
6.1 Inteiros negativos.
6.3 Não escolha a para ser um número pri-
mo.
6.6 Uma calculadora ou um computador 
ajudará com isto.
6.7 Para este problema, você certamente 
vai querer usar um computador. Um 
sistema de álgebra computacional, 
como Maple, Mathematica ou Sage 
será de valor inestimável. O pacote de 
teoria dos números Pari/GP pode fazer 
estes cálculos muito bem:
gp > n = 2^ (2^4)+1
%1 = 65537 
gp > isprime(n)
%2 = 1
 Isso mostra que 224 + 1 é primo. Pari/
GP está disponível gratuitamente aqui: 
http://pari.math.u-bordeaux .fr/
Inteiros da forma 22n + 1 são conhe-
cidos como números Fermat. Fermat 
conjecturou (incorretamente) que to-
dos esses números são primos.
6.9 Não há muito pequenos valores de n 
para os quais n2 + n + 41 não seja pri-
mo. Você tem que considerar n como 
sendo moderadamente grande. Se você 
escolher o n correto, não precisará fa-
zer quaisquer cálculos para ver que 
n2 + n + 41 é composto.
7.1 (b) verdadeiro. (c) falso.
7.3 Faça uma tabela verdadeira para (x ∧ y) 
∨ (x ∧ ¬ y) e verifique que a coluna 
para x combina exatamente com a co-
luna para (x ∧ y) ∨ (x ∧ ¬ y).
7.4 Faça uma tabela da verdade para am-
bos e verifique se eles são os mesmos.
7.9 Mais de 1.000. Tente alguns pequenos 
exemplos primeiro.
7.10 Resposta para (b): Considere x = falso 
e y = verdadeiro. Então x → y avalia 
para verdadeiro, enquanto x ↔ y avalia 
para falso.
7.11 Para mostrar que (a) é uma tautologia, 
construímos a seguinte tabela da ver-
dade.
5Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
x y x ∨ y x ∨ y
(x ∨ y) ∧
(¬(x ∧ y))
T T T T T
T F T T T
F T T F T
F F F T T
Solução para a parte (a):
(x ∨ y) ∨ (x ∨ ¬ y) = (x ∨ x) ∨ (y ∨ ¬ y)
= x ∨ verdadeiro = verdadeiro
onde usamos a associatividade e a co-
mutatividade na primeira etapa, o fato 
de que y ∨ ¬ y = verdadeiro na segunda 
e o elemento de identidade na última.
7.13 Aqui está uma tabela da verdade para a 
parte (a):
x y x ∨ y x ∨ ¬ y ¬ x
(x ∨ y)∧ 
(x ∨ ¬ y) ∧¬ y
T T T T F F
T F T T F F
F T T F T F
F F F T T F
(⇒) Suponha que A seja logicamente 
equivalente a B. ...Portanto, A ↔ B é 
uma tautologia.
(⇐) Suponha que A ↔ B seja uma tau-
tologia. ... Portanto A é logicamente 
equivalente a B.
7.16 Para (c) mostramos x ∨ y = (x ∨ y) ∧ 
(¬ (x ∨ y)) segundo a seguinte tabela.
x y x ∨ y (x ∨ y) ¬ (x ∧ y)
(x ∨ y) ∧ 
(¬ (x∧y))
T T F T F F
T F T T T T
F T T T T T
F F F F T F
Se necessário, você pode anotar todas 
as tabelas possíveis e encontrar manei-
ras de expressar cada uma. No entanto, 
existe um modo mecânico para con-
verter uma operação booleana binária 
arbitrária utilizando ∧, ∨ e ¬.
8.1 Como há 5 vogais, sua lista deve ter 
5 × 5 = 25 entradas.
Destas, 20 não têm repetição.
A propósito, algumas destas combi-
nações de duas letras são palavras reais. 
Por exemplo, um io é um tipo de ave.
8.3 2k.
8.5 Se uma música pode estar em ambas 
as listas, há (500)20 maneiras de carre-
gar a lista “Exercitando” e, de novo, 
(500)20 para a lista “Relaxante”. Isso 
dá [(500)20]
2 maneiras possíveis de 
carregas as músicas. Não é necessá-
rio multiplicar isso, mas se você fez, o 
valor que deve obter é de aproximada-
mente 9,7 × 10112.
8.6 Para a primeira pergunta, vamos escre-
ver todas as possibilidades quando n = 
4. As listas que podemos formar (usan-
do os elementos 1, 2, 3 e 4) são estas:
111 121 131 141
212 222 232 242
313 323 333 343
414 424 434 444
8.7 Sugestão para (b): Imagine que você 
esteja etiquetando as fotos, com cada 
uma de duas etiquetas “Amigos” ou 
“Família”.
8.9 Tente uma versão menor deste proble-
ma primeiro. Por exemplo, mostre que 
existem 36 maneiras de colocar torres 
não atacando emparelhadas em um ta-
buleiro de xadrez de 3 × 3.
8.12 (a) 109. (c) 59. (e) 99.
8.13 Quantas listas de 2 elementos alguém 
pode formar, cuja entradas são ex-
traídas de um conjunto de n elemen-
tos? Quantas não têm uma repetição? 
Quantas devem ter uma repetição?
8.14 Divida este problema em 8 casos, de-
pendendo do comprimento do nome e 
totalize sua resposta.
6 Matemática discreta
8.17 A resposta é 20 × 19 × 18 × ... × 2 × 1.
8.18 A resposta não é (10 × 9 × ... × 2 × 1)2.
9.2 Aqui está uma resposta para uma per-
gunta que não fizemos. 6! × 8! × 5! for-
mas de colocar os livros na prateleira, 
se os livros franceses devem estar à 
esquerda, os livros russos no meio e os 
livros espanhóis à direita.
9.3 O ponto desta discussão é que o produ-
to de uma lista que contém apenas um 
número deveria ser o número na lista. 
Nenhuma multiplicação real ocorre.
9.4 Tente usar a fórmula nŠ
.n k/Š
 para calcu-
lar (3)6.
9.6 2100 = (24)25 = 1625.
9.7 O erro aproximado é calculado como 
valor aproximado – valor verdadeiro 
valor verdadeiro
9.8 (a) 945; (b) 0.
9.9 Resposta para (e): 719 A propósito: 6! 
= 720).
9.10 A resposta é não 20.
9.11 Os dois últimos nesta lista, agem de 
forma ligeiramente diferente dos ou-
tros.
9.13 n! = n × (n – 1)!.
9.14 OK, vamos receber muitas críticas por 
isso porque a maioria dos matemáticos 
diria que 00 é indefinido. Mas desta 
perspectiva da matemática discreta, há 
uma resposta natural. Você pode pen-
sar sobre isso como o resultado de um 
problema de uma lista de contagem ou 
usar o raciocínio de Alice/Bob.
9.15 Sugestão para (c): Escreva n = 2k + 1 
para algum inteiro k e, em seguida, en-
contre uma fórmula do produto em que 
a variável falsa vai de 0 a k.
9.16 (x4)″″ = (4x3)′″ = (12x2)″ = (24x)′ = 24.
10.1 (a) {0, 3, 6, 9}. 
(f) {–10, 10, –20, 20, –50, 50, –100, 100}.
10.2 Resposta para (c): {x ∈  : x é ímpar} 
ou {x ∈  : x > 0 e x é par}.
10.3 (a) 21.
10.4 (a) 2 ∈{1, 2, 3}.
(b) {2} ⊆ {1, 2, 3}.
(c) {2} ∈ {1}, {2}, {3}}.
10.5 Em alguns casos, você vai precisar fa-
zer conjuntos cujos elementos são eles 
próprios conjuntos.
10.7 Para (a), a parte principal da sua prova 
deve ser desta forma: 
Prova. Suponha que x ∈ A... Portanto, 
x ∈ C. Portanto, A ⊆ C.
10.9 Use os Exercícios 10.7(a) e 10.8.
10.12 Seja x ∈ C = {x ∈  : x|12}, portanto, 
x é um divisor de 12; ou seja, 12 = xa 
para algum inteiro a. Multiplique am-
bos os lados por 3 e temos 36 = 3xa = 
(3a)x. Portanto, x é um divisor de 36 e 
x ∈ D. Portanto, C ⊆ D.
10.15 Você precisa encontrar um triplo (a, b, 
c) que está em um dos conjuntos, mas 
não no outro. Como T ⊆ P, você deve-
ria tentar encontrar um terno pitagóri-
co (a, b, c) ∈ P do qual (a, b, c) ∉ T.
Como uma sugestão extra: O que 
você pode dizer sobre o termo do meio 
dos três (p, q, r) ∈ T?
11.1 (a) ∀x ∈ , x é primo.
(g) ∀x ∈ , ∃y ∈ , xy = 1.
11.2 (a) ∃x ∈ , x não é primo. “Existe um 
inteiro que não é primo.”
(g) ∃x ∈ , ∀y ∈ , xy ≠ 1. “Há um 
inteiro x tal que não importa qual intei-
ro nós multiplicamos por x, a resposta 
nunca é 1.”
11.4 (a) Falso. (g) Verdadeiro.
11.5 (a) ∃x ∈ , x </  0: Existe um inteiro que 
não é negativo.
(g) ∃x ∈ , ∀y ∈ , x + y ≠ 0: Existe 
um inteiro x com a propriedade que, 
para qualquer número inteiro y, a soma 
de x e y não é zero.
11.8 (a) Uma região R é convexa desde que
∀a ∈ R, ∀b ∈ R, ∀x ∈ L(a, b), x ∈ R.
7Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
Nota: Pedimos uma sentença com três quanti-
ficadores [S], mas aqui está uma alter-
nativa que utiliza apenas dois:
∀a ∈ R, ∀b ∈ R, L(a, b) ⊇ R.
(b) Uma região R não é convexa desde que
∃a ∈ R, ∃b ∈ R, ∃x ∈ L(a, b), x ∉ R.
(c) Uma região não é convexa, desde que 
existam dois pontos nesta região, de tal 
modo que o segmento de linha que une 
esses pontos contém um ponto que não 
está na região.
(d) Aqui está um diagrama parailustrar 
(b) [e (c)]:
a bx
L(a, b)
R
12.1 (b) {4, 5}. (c) {1, 2, 3}. (e) {1, 2, 3, 6, 7}.
12.2 Use a Proposição 12.4.
12.4 A resposta para (a): |1 \ 2| = 0 exata-
mente quando as linhas são paralelas 
ou ainda |1 \ 2| = 1 quando elas são 
interceptadas (cruzadas).
12.9 Isto é falso. Encontre um contraexem-
plo.
12.11 Isto é verdadeiro. Aqui está um esboço 
para a sua prova.
(⇒) Suponha A [ B = A [S] B. Que-
remos provar A = B.
Suponha x ∈ A.... Portanto, x ∈ B.
Suponha x ∈ B. ... Portanto, x ∈ A.
Portanto, A = B.
(⇐) Suponha A = B. ... Portanto, 
A [ B = A \ B. 
12.16 (⇐) Se A – B = ;, então, se x ∈ A, en-
tão x também deve estar em B (caso 
contrário A – B não estaria vazio), por-
tanto, A ⊆ B.
(⇒) Por outro lado, se A ⊆ B, clara-
mente não há elementos em A que não 
estejam em B, portanto A – B = ;.
12.19 Use a Lei de DeMorgan da álgebra 
booleana.
12.20 Você deve mostrar que (a) é falso e (b) 
é verdadeiro. Mas espere! Você pode 
ter pensado sobre duas regiões que não 
se interceptam. No entanto, o conjunto 
vazio é, de fato, convexo porque satis-
faz vagamente a definição de convexi-
dade.
12.21 A maioria é falso. Os diagramas de 
Venn irão ajudá-lo a descobrir quais 
são verdadeiros e quais são falsos. Em 
seguida, construa pequenos contrae-
xemplos (para os falsos).
12.23 Uma maneira de fazer isso: comece 
com um diagrama de Venn padrão com 
três círculos (para os conjuntos A, B e 
C) e, em seguida, adicione uma forma 
complicada para D.
Note que deve haver pelo menos 16 
regiões na figura final.
12.24 Seja X = A [ B. Aplique a Equação (4) 
para |X [ C|. Você agora tem
|A [ B [ C| = |X [ C| = |X| + |C| – |X \ C|.
Aplique o que você sabe para encon-
trar |X| e |X \ C| e substitui-lo na equa-
ção acima para terminar a prova.
12.25 Certifique-se de ter feito o Exercício 
7.16.
12.26 A união ([) é comutativa.
12.27 Certifique-se de ter feito o Exercício 
12.25 e use as propriedades da ideia 
correspondente da álgebra booleana
12.29 Use o Princípio da Multiplicação (Teo-
rema 8.2).
12.30 Aqui está um modelo para uma prova 
da parte (a).
Para mostrar que dois conjuntos são 
iguais, usamos o Modelo da Prova 5.
8 Matemática discreta
Suponha primeiro que x ∈ A × (B [ C). ... 
Portanto, x ∈ (A × B) [ (A × C).
Depois suponha que x ∈ (A × B) [ (A × C). 
... Portanto, x ∈ A × (B [ C).
Portanto, A × (B [ C) = (A × B) [ (A × C).
Nós estendemos isso um pouco como 
segue.
Suponha primeiro que x ∈ A × (B [ C). Isso 
significa x = (a, z) em que a ∈ A e 
z ∈ B [ C. ...Portanto, x ∈ (A × B) 
[ (A × C).
Suponha depois que x ∈ (A × B) [ (A × C). 
Assim, tanto x ∈ A × B como x ∈ A × 
C.... Portanto, x ∈ (A × (B ∈ C).
Portanto, A × (B [ C) = (A × B) [ (A × C).
E podemos expandir ainda mais para 
dar a seguinte estrutura para você com-
pletar.
Suponha primeiro que x ∈ A × (B [ C). Isso 
significa que x = (a, z) em que a ∈ A 
e z ∈ B [ C. Temos dois casos:
– Se z ∈ B, então...
– Se z ∈ C, então...
... Portanto, x ∈ (A × B) [ (A × C).
Depois suponha que x ∈ (A × B) [ (A × C). 
Assim, tanto x ∈ A × B ou x ∈ A × C. 
Temos dois casos:
– Se x ∈ A × B, então...
– Se x ∈ A × C, então...
... Portanto, x ∈ A × (B [ C).
Portanto, A × (B [ C) = (A × B) [ (A × C).
13.1 Use a seguinte questão: quantas listas 
de comprimento n podemos formar 
usando os elementos 0 e 1 (repetição 
permitida), nas quais os elementos não 
são todos zero?
13.2 Para a primeira parte, a expressão deve 
simplificar para xn–1.
Para a segunda parte, seja x = 2.
13.3 Para a primeira parte, use a questão 
“Quantas listas de tamanho n podemos 
formar usando os elementos em {1, 2, 
3} nos quais os elementos não são to-
dos 3?”
Para a segunda parte, note que 99 + 
1 = 100, 999 + 1 = 1.000 e assim por 
diante.
13.4 Crie dois padrões de pontos. No pri-
meiro padrão, os pontos são dispos-
tos em uma grade retangular de linhas 
a – b e colunas a + b. É evidente que 
este padrão tem pontos (a – b)(a + b). 
Agora, encontre um rearranjo dos pon-
tos que tenha claramente a2 – b2 pontos.
13.5 Não use álgebra! Forneça duas res-
postas diferentes à pergunta “quantas 
listas de dois comprimentos podemos 
fazer de n elementos?”
13.6 Para (a), liste (a, b) de modo que a < 
b ou a > b sejam os mesmos que nas 
listas com a ¤ b, e este é um problema 
que já solucionamos neste livro.
Para (b), considere os diferentes va-
lores possíveis para b.
13.7 A resposta para a primeira pergunta é 
2a – 1 porque existem as listas da forma 
(?, a) e outras listas a da forma (a, ?). 
No entanto, isso conta a lista (a, a) duas 
vezes, então a resposta final é 2a – 1.
14.1 Resposta para (a): {(1,2), (1,3), (1,4), 
(1,5), (2,3), (2,4), (2,5), (3,4), (3,5), 
(4,5)}.
14.2 Resposta para (a): é-um-menos-que.
14.3 (a) reflexiva, simétrica, antissimétrica, 
transitiva
(b) irreflexiva, antissimétrica
14.4 (a) reflexiva, simétrica, transitiva.
(b) irreflexiva, antissimétrica.
14.5 Você precisa provar: ∀x, y ∈ , (x = 
y ∧ y = x) ⇒ x = y.
Você tem que mostrar que x = y, mas 
é dado que x = y. Em outras palavras, 
não há nada para provar!
9Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
14.6 (d) é verdadeiro. Aqui está uma prova 
completa: Suponha x R y. Então, |x – y| 
≤ 2.
Note que |x – y| = |y – x|, portanto, |y – 
x| ≤ 2. Portanto, y R x.
(f) é falso. Você deveria encontrar 
três números a, b e c com a R b, b R c, 
mas um R/ c.
14.7 (a) R–1 = {(2, 1), (3, 2), (4, 3)}.
(b) R–1 = {(x, y) : x, y ∈ , x – y = –1} 
ou R–1 = {(x, y) : x, y ∈ , y – x = 1}.
14.8 Lembre-se que R, S, R–1 e S–1 são con-
juntos. Para mostrar que dois conjun-
tos são iguais, use o Modelo da Prova 
5.
14.9 Isto é falso. Encontre um contraexem-
plo com A = {1, 2}.
14.10 Todas as provas e contraexemplos para 
este problema são bastante curtos. Por 
exemplo, aqui está a prova de que a re-
lação “tem-a-mesma-dimensão-que” R 
é transitiva.
Sejam A, B e C conjuntos finitos de 
números inteiros e suponha A R B e B 
R C. Isto significa que |A| = |B| e |B| = 
|C|. |A| = |C| e assim A R C. Portanto, R 
é transitivo.
14.11 Para uma parte deste problema, o Exer-
cício 10.8 é útil.
14.13 Para a parte (b): Isto parece impossí-
vel? Não é. Talvez você esteja racioci-
nando como se segue:
Seja x ∈ A. Para que R seja reflexi-
vo, temos que ter x R x. Para que R seja 
irreflexivo, temos que ter x R/ x. Não 
podemos ter as duas coisas (x ou é ou 
não é relacionado a si mesmo).
O erro neste raciocínio está na primei-
ra sentença.
14.14 Aqui está um modelo de prova para 
este problema.
(⇒) Suponha que R seja simétrico. Para 
mostrar que R = R–1, precisamos pro-
var que os dois conjuntos, R e R–1 são 
os mesmos. Usamos o Modelo de 
Prova 5.
Suponha (x, y) ∈ R. ... (x, y) ∈ R–1.
Suponha (x, y) ∈ R–1. ...(x,y) ∈ R. 
Portanto, R = R–1.
(⇐) Suponha que R = R–1. Deve-
mos provar que R é simétrico. Supo-
nha x R y. ... Portanto, y R x, assim R 
é simétrico.
15.1 Lembre-se: a ≡ b (mod N) esse N divi-
de a – b. Resposta para (a): 2, 5 e 10.
15.3 (a) Sim. (f) Não. (g) Sim.
15.4 Aqui está a prova para a primeira afir-
mação:
Suponha que x e y sejam ambos 
ímpares. Por definição, podemos en-
contrar números inteiros a e b de modo 
que x = 2a + 1 e y = 2b + 1. Agora 
x – y = (2a + 1) – (2b + 1) = 2a – 2b = 
2(a – b), assim 2|(x – y). Portanto, x ≡ 
y (mod 2).
15.5 O que é a – (–a)?
15.6 Certifique-se de ter feito o Exercício 
5.9.
15.7 (a) [1] = {1, 2}.
(e) [você] é o conjunto contendo todas 
as pessoas nascidas em seu aniversário.
15.8 Resposta para (b): 366 (Você se lembra 
de 29 de fevereiro?)
15.9 Você pode usar o Modelo de Prova 
5 (a maneira padrão para provar que 
conjuntos são iguais), mas você terá 
mais facilidade se aplicar a Proposição 
15.12.
15.13 Aqui está uma nota útil para este pro-
blema. Escreva [a]R para a classe de 
equivalência de R com respeito à rela-
ção R e [a]S para a classe de equivalên-
cia com respeito a S. Ou seja,
10 Matemática discreta
[a]R = {x ∈ 2 A : x R a}
[a]S = {x ∈ 2 A : x S a}.
15.16 É doloroso escrever uma relaçãode 
equivalência como um conjunto com-
pleto de pares ordenados. Por exem-
plo, considere a relação
R = {(1, 1), (1, 2), (2, 1), (2, 2),
(3, 3), (3, 4), (4, 3), (4, 4)}.
É mais simples apenas escrever as suas 
classes de equivalência: {1, 2} e {3, 
4}. Uma abreviação conveniente para 
isso é apenas escrever 12/34.
16.1 Use a anotação 1/23 como base para a 
partição {{1}, {2, 3}},
As partições de {1, 2, 3} são 1/2/3, 
1/23, 2/13, 3/12 e 123.
Há 15 partições de {1, 2, 3, 4}.
16.2 Resposta para (d): 7Š2Š 3Š.
16.5 Aqui está um esboço para esta prova:
Parte (1): Seja [a] uma classe equi-
valente de P. Prove que existe uma 
parte P ∈ P de modo que [a] = P (você 
terá que provar que os dois conjuntos 
são iguais aqui).
Parte (2): Seja P uma parte de P, ou 
seja, P ∈ P. Demonstre que existe um 
elemento a ∈ A de modo que [a] = P.
Você mostrou que a classe de equi-
valência de P é uma parte de P e, por 
outro lado, que toda parte de P é uma 
classe de equivalência de P.
16.7 Imagine que 12 pessoas estão dispos-
tas em torno de uma face do relógio. 
De quantas maneiras você pode locali-
zá-las em torno do relógio? [Resposta: 
12!.] Claro que, se todos se moverem 
uma posição no sentido horário, o ar-
ranjo é equivalente. Desenvolva uma 
relação de equivalência no conjunto 
de arranjos e descubra a dimensão das 
classes de equivalência.
16.8 Seja cuidadoso. É fácil estar fora por 
um fator de 2 neste problema.
16.9 É fácil estar fora por um fator de 2 nes-
te problema também.
16.10 129260083694424883200000, mas 
esta é uma maneira terrível para relatar 
a resposta.
16.11 Imagine o primeiro alinhamento de 
20 pessoas. De quantas maneiras isso 
pode ser feito? [Resposta: 20!.] As 
primeiras 10 pessoas na linha formam 
uma equipe e as últimas 10 pessoas na 
linha formam a outra equipe.
Considere dois alinhamentos equi-
valentes se eles resultarem nas mesmas 
duas equipes sendo formadas. Conte a 
dimensão das classes de equivalência e 
descubra o número de classes. Observe 
que, se mudarmos todos os jogadores 
de ambos os times, realmente não mu-
damos nada.
Teste a sua resposta considerando 
o número de maneiras para dividir 6 
pessoas em duas equipes de 3. A res-
posta deve ser 10: 123/456, 124/356, 
125/346, 126/345, 134/256, 135/246, 
136/245, 145/236, 146/235 e 156/234.
16.15 Tente trabalhar vários exemplos com 
valores pequenos de n. Por exemplo, 
quando n = 3, existem três partições 
com exatamente duas partes: 1/23, 
12/3 e 13/2.
Quando n = 4 há sete partições 
de duas partes: 1/234, 12/34, 13/24, 
14/23, 123/4, 124/3, 134/2.
16.16 Imagine isso como um problema de 
lista de contagem. Para cada número k 
de 3 a 100, temos que decidir em qual 
parte k deve cair: 1, 2 ou 3.
16.17 Depois de ter as expressões, eu reco-
mendo que você simplesmente use uma 
calculadora para descobrir qual é maior.
16.20 Sim. Encontre o conjunto A.
17.1 (a) 1, (b) 1, (c) 9, (d) 9, (e) 0, (f) 1, 
(g) 1, (h) 0.
11Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
17.3 Resposta para (b): –4.320.
17.4 A segunda resposta é o dobro da pri-
meira.
17.7 Sua resposta deve avaliar até 34650, 
mas esta não é uma boa maneira de es-
crever o seu resultado.
17.8 A resposta para (b) é 5010 .
17.9 O gráfico parece com isso:
f1; 2; 3g $ f4; 5; 6; 7g
:::
f5; 6; 7g $ f1; 2; 3; 4g
17.10 Para (b), considere os casos com zero, 
com uma e com duas duplas separada-
mente.
17.11 Aviso: Há uma pequena armadilha es-
perando por você. Certifique-se de que 
não entrou nela.
17.13 Expanda n
k e nn k em termos de fato-
riais, e então usa a álgebra para mos-
trar que eles são iguais.
17.14 A questão é: “Quantos subconjuntos 
um conjunto de n elementos tem?”
17.15 Expanda (1 – 1)n.
A equação significa que o número 
de subconjuntos de um conjunto de 
n elementos com um número par de 
elementos é igual ao número de sub-
conjuntos com um número ímpar de 
elementos.
17.19 Considere um conjunto de 2n + 2 pes-
soas com dois estranhos.
17.20 Algebricamente, simplifique a expres-
são n – n2 e então, considere os seguin-
tes casos separadamente: n = 1, n = 2, 
n = 3 e n > 3.
17.21 A fórmula de Stirling é n! 
p
ne n.
Para a segunda parte, note que 4n = 
22n.
17.22 Coloque tudo sobre um denominador 
comum e não perca sua coragem.
17.23 A questão é: “Quantos subconjuntos de 
3 elementos {1, 2, 3,. . . , n} tem?”
E considere, quantos desses sub-
conjuntos de 3 elementos têm o maior 
elemento 3? ... maior elemento 4? ... 
maior elemento n?
17.26 Pense em uma sala de aula contendo n 
meninas e n meninos.
17.28 A resposta é nk . Podemos pensar neste 
processo de rotulagem enquanto sele-
cionamos os elementos k de A que re-
cebem a etiqueta “bom” (e aos restan-
tes são atribuídas “ruim”). Portanto, há 
uma correspondência de um-para-um 
entre a atribuição de etiquetas e a sele-
ção um subconjunto de elemento k de A.
17.29 (a) Em caso de dúvida, escreva todas 
as possibilidades. Não existem tantas 
assim.
(b) Note que 1 + 2 + 5 ¤ 10, portanto, 
não  há  rótulos  suficientes. A  resposta 
para este problema é um número e a 
palavra “impossível”.
(d) Dado que não existem etiquetas do 
Tipo 3 disponível, isto reduz ao pro-
blema anterior; a resposta é um coefi-
ciente binomial.
(e) Mudar os nomes das etiquetas não 
altera o número de maneiras de distri-
buí-las.
17.30 Para (a), pense no processo de etique-
tagem como decorrendo em duas fases. 
Primeiro vamos atribuir as etiquetas de 
Tipo 1 (de quantas maneiras?) e, em 
seguida, vamos atribuir as etiquetas de 
Tipo 2 (de quantas maneiras?).
Para (b), você pode usar (a) e ex-
pandir os coeficientes binomiais em 
fatoriais, mas há uma prova combi-
natória. Os n elementos em uma lista 
livre de repetição (em quantas manei-
ras?). Em seguida, forneça os primei-
ros elementos a na lista de etiquetas 
Tipo 1, os próximos elementos b, eti-
quetas Tipo 2 e os últimos elementos c, 
12 Matemática discreta
etiquetas Tipo 3. Considere duas listas 
equivalentes se elas resultam na mes-
ma distribuição de etiquetas e conte o 
número de classes de equivalência.
17.31 A prova é similar àquela do Teorema 
17.8.
17.32 Resposta: 525 .
17.33 (a) 13 × 48. (d) 13 × 43 × 12 × 
4
2 .
17.35 Para verificar a fórmula para n4 , use o 
Teorema 17.12.
Para a segunda parte, você vai 
achar a função fatorial dupla útil: 7! = 
7 · 5 · 3 · 1
17.36 Anote as primeiros seis ou sete filei-
ras do triângulo de Pascal. Em uma 
cor diferente, registre ao lado de cada 
entrada quantas adições leva para cal-
cular esse valor. Observe que os 1s nas 
extremidades de cada linha exigem 0 
cálculos.
Agora, para calcular um valor in-
terno, como nk , você calcula n 1k 1 (que 
exige um certo número de adições) e 
n 1
k (que exige um certo número de 
adições). Finalmente, para calcular nk 
você faz mais cálculos.
Você vê um padrão? Isso permitirá 
que você encontre o número de adi-
ções para computar 10030 .
18.1 Para 32 : Listamos todos os seis mul-
ticonjuntos de 2 elementos que podem 
se formar com os elementos em {1, 2, 
3}. São eles 〈1,1〉, 〈1, 2〉, 〈1, 3〉, 〈2, 2〉, 
〈2, 3〉, 〈3, 3〉.
O Teorema 18.8 dá 32 D
3C2 1
2 D
4
2 D 6. 
3
2 D
3C2 1
2 D
4
2 D 6.
Dê uma resposta semelhante para 
2
3 .
18.2 Para 32 : **l l, *|*|, *||*, |**|, |*|* e ||**.
18.3 Você pode conferir suas respostas 
usando a tabela. O ponto deste proble-
ma é verificar a primeira linha e a pri-
meira coluna do gráfico.
18.5 〈1, 4, 4, 4〉.
18.6 Por “avalie por este princípio” quere-
mos dizer que você não deveria tra-
duzir 2
k
 em um coeficiente binomial, 
mas derive o valor apenas consideran-
do o significado da notação.
Por exemplo, 25 = 6 porque há seis 
multiconjuntos de tamanho 5 que po-
demos formar a partir dos elementos 
de {1,2}, nomeadamente: 〈1,1,1,1,1〉, 
〈1,1,1,1, 2〉, 〈1,1,1, 2, 2〉, 〈1, 1,2,2, 2〉, 
〈1, 2, 2, 2, 2〉 e 〈2, 2,2, 2, 2〉.
18.7 Se seus cálculos estão corretos, um 
destes é duas vezes tão grande quanto 
o outro. A propósito, 84 = 330.
Isso prenuncia o Exercício 18.11.
18.8 Converta para um coeficientebino-
mial.
18.9 Reescreva nn como 2n 1n e compare 
isso com 2nn .
Para a segunda parte do problema, 
você pode facilmente adivinhar a res-
posta calculando 42 e 22 .
18.10 O resultado para x = 2 é sem sentido. 
Obtemos 1+2+4+8+ · · · = –1.
No entanto, para x = 110 temos
1 C 1
10
C 1
100
C 1
1000
que, quando expresso como um deci-
mal, é 1,11111... Esta dízima periódica 
avalia para 10/9 e, na verdade, substi-
tuindo 1/10 por1/(1 – x) objetos 10/9—
a resposta correta.
O ponto é que as identidades com 
somas infinitas precisam ser manusea-
das com cuidado.
18.11 Converta tudo para fatoriais e não se 
afogue na álgebra.
18.13 Você pode recorrer a fatoriais se ne-
cessário. Aqui está uma ideia melhor: 
*↔|.
18.15 Isto pede uma prova combinatória. A 
questão é: “Quantos multiconjuntos de 
13Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
elemento k podemos formar usando os 
números inteiros de 1 a n?” A primeira 
resposta é nk . A segunda resposta de-
pende da multiplicidade do elemento n 
no multiconjunto.
Este problema também pode ser re-
solvido por conversão para coeficien-
tes binomiais.
18.16 Este problema exige uma prova combi-
natória. Você deve encontrar uma per-
gunta que seja respondida por ambos 
os lados esquerdo e direito da equação. 
A pergunta deve ser “Quantos mul-
ticonjuntos de k elemento podem ser 
formados usando inteiros escolhidos 
de {1,2,..., n}?”
O lado esquerdo da equação é cla-
ramente uma resposta. Tente descobrir 
como o lado direito é também uma 
resposta. E para ajudá-lo com isso, res-
ponda ao seguinte:
Quantos multiconjuntos tem di-
mensão 10, com elementos que são 
escolhidos de {1, 2, ..., 99}, cujo ele-
mento 23 é o maior? Resposta: 239 .
18.17 Para (b) você deve encontrar n4 = (n4 
– 6n3 + 11n2 – 6n)/4! e n4 = (n4 + 6n3 
+ 11n2 + 6n)/4!. Observe que a substi-
tuição de –n em um dá o outro!
18.19 Na formula (1 – x)–n = 
P
k
n
k x
k, subs-
titua n = 1/2 e aplique sua resposta ao 
Exercício 18.17(d).
19.1 Chame os quatro grupos de pessoas 
A1, A2, A3 e A4. O problema te dá as di-
mensões destes conjuntos e suas várias 
interseções. Você precisa encontrar 
|A1 [ A2 [ A3 [ A4|.
19.2 Aqui está uma resposta completa.
Seja A esses números inteiros entre 
1 e 100 que são divisíveis por 2. Seja B 
aqueles que são divisíveis por 5. O pro-
blema nos pede para encontrar |A [ B|. 
Note que A \ B são os números intei-
ros entre 1 e 100 que são divisíveis por 
ambos, 2 e 5, isto é, que são divisíveis 
por 10.
Nós calculamos que |A| = 100/2 = 
50, |B| = 100/5 = 20 e |A \ B| = 100/10 
= 10.
Portanto, |A [ B| = |A| + |B| – |A \ B| 
= 50+20–10 = 60.
19.3 Sejam A, B, C os subconjuntos de 
{1,..., 106} que contêm os múltiplos 
de 2, 3 e 5 respectivamente. Calcule 
|A [ B [ C| e subtraia de um milhão.
No seu cálculo, você precisa conhe-
cer |A \ B|: este é o número de inteiros 
entre 1 e um milhão, que são divisíveis 
por ambos 2 e 3, ou seja, são divisíveis 
por 6. Há 166.666 destes números (di-
vida um milhão por 6 e arredonde para 
baixo).
19.4 Isto é verdadeiro, por isso não tente re-
futar. Comece de
jA [ B [ C j D jAj C jBj C jC j
A \ B A \ C B \ C j
C jA \ B \ C j
e cancele |A [ B [ C| = |A| + |B| + |C|.
19.5 Primeiro conte as palavras “ruins” e 
subtraia de 265.
Denote B1 o conjunto de palavras 
cujas primeiras duas letras são as mes-
mas. Denote B2 o conjunto de palavras 
cujas primeiras duas letras são as mes-
mas. E assim por diante.
Descubra as dimensões das várias 
interseções e aplique a inclusão-exclu-
são.
19.6 Para (a), escreva 9n = [10 + (–1)]n.
Para (b), a prova combinatória, 
você necessita da pergunta certa. Aqui 
está uma boa maneira de começar a 
sua pergunta: Quantas listas de com-
primento n podemos fazer usando os 
dígitos padrões de 0 a 9 em que ...?
14 Matemática discreta
19.8 O número de trajetórias que passam 
por A é 64
12
5 . Quantos caminhos pas-
sam por B? Quantos passam por am-
bos?
19.11 A segunda parte deste problema pede 
para você criar n conjuntos (digamos, 
para n = 4), para que a desigualdade
jA
X
i
jAi njA1 Anj
seja falsa.
20.1 (a) Se x2 não é ímpar, então x não é ímpar.
(d) Se um paralelogramo não é um lo-
sango, então, suas diagonais não são 
perpendiculares.
20.2 Lembre-se: ¬ ¬ B = B.
20.4 (b) Sejam a e b inteiros negativos. Su-
ponha, por causa da contradição, que 
a + b.
(d) Sejam p e q primos para que p + q 
também seja primo.
Suponha, por causa da contradição, 
que nem p nem q sejam iguais a 2.
20.5 A sua prova deve começar como se-
gue:
Sejam x e x + 1 inteiros consecuti-
vos. Suponha, por causa da contradi-
ção, que x e x + 1 sejam ambos pares...
20.8 Use as propriedades de ordenação de 
números reais no Apêndice D. Em par-
ticular, pela propriedade da tricotomia, 
você pode dividir sua prova em três ca-
sos: x < 0, x = 0 e x > 0.
20.9 Sua prova deve começar: Sejam a e d 
números reais, com ab = 0. Suponha, 
por causa da contradição, que nem a 
nem b sejam 0.
Mais uma sugestão: Se b ¤ 0, então 
b–1 existe.
20.10 Sabemos que a > 1. Precisamos provar 
duas desigualdades: 1 < 
p
a e 
p
a < a. 
Aqui está uma prova da primeira.
Suponha, por causa da contradição, 
que 
p
a  1. Isso significa que 
p
a ≤ 1. 
Como 
p
a ≤ 1, temos 
p
a
2
  <  12 que 
dá a ≤ 1, mas a  >  1. ⇒⇐ Portanto, 
p
a > 1.
20.12 Aqui está uma resposta completa.
(⇒) Suponha que N seja divisível 
por 10, mas (por contradição), quando 
escrito na base 10
N = dk 10
k + dk–110
k–1 + … + d110 + d0
seu dígito um não é zero; isto é, d0 ∈ 
{1, 2, ..., 9}. Sabemos que 10|N então 
N = 10a para algum inteiro a. Desde 
que
10a = dk 10
k + dk–110
k–1 + … + d110 + d0
temos
d0 = 10a – (dk 10
k + dk–110
k–1 + … + d110)
= 10 [a – dk 10
k–1 + dk–110
k–2 + … + d] 
e portanto,
d0
10
 = a – dk10
k–1 + dk–110
k–2 + …+d1
é um número inteiro. No entanto, ne-
nhum 1
10
; 2
10
; ; 9
10
 é um inteiro. ⇒⇐ 
Portanto, o último dígito na represen-
tação da base dez de N é um zero.
(⇐) Suponha que o último dígito 
na representação da base dez de N seja 
um zero. Isto é,
N = dk 10
k + dk–110
k–1 + … + d110 + 0.
Disto segue que N = 10a em que a é o 
inteiro
a = dk 10
k–1 + dk–110
k–2 + …+ d1
e, portanto, 10|N.
20.13 Suponha (A – B) \ (B – A) ¤ ;. Isto 
significa que há um elemento x em am-
bos A – B e B – A. Argumente a partir 
daqui para uma contradição.
20.14 Este é um teorema de estilo se-e-ape-
nas-se; tenha a certeza de provar as 
duas metades. Ambas podem ser pro-
vadas por contraposição.
15Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
20.15 Uma prova direta aqui é possível. O 
ponto deste problema é introduzir a 
termo conversão.
20.16 Resposta para (a): Dizemos que x é 
um elemento menor de A dado que (1) 
x ∈ A e (2) se y ∈ A, então x ≤ y.
Primeira sentença para (b): Supo-
nha, por causa da contradição, que E 
contém um elemento x menor.
Comentário para (c): Isto é bastante 
óbvio, mas por favor, escreva uma pro-
va cuidadosa por contradição usando 
o Modelo da Prova 14. Aqui está um 
bom início para a sua prova: “Seja A 
um subconjunto dos inteiros com um 
elemento menor. Suponha, por causa 
da contradição, que A contém dois ele-
mentos distintos menores a e b...”
21.1 Não existe tal coisa.
21.6 Aqui está uma prova completa.
Suponha que a Proposição 13.2 seja 
falsa e seja X o conjunto de contra- 
exemplos, isto é,
X D fx 2 ZC W 1 1Š C 2 2Š x xŠ 6D .x C 1/Š 1g
e seja n ser o menor membro de X.
Note que n ¤ 1 porque ambos 
1 · 1! e (1 + 1)! – 1 igual a 1. Então, 
n > 1 e assim n – 1 é um número inteiro 
positivo que não é um contraexemplo. 
Assim,
1 · 1! + ... + (n – 1) · (n – 1)! = [(n – 1) + 1]! – 1.
Adicionando n · n! em ambos os lados dá
1 · 1! + ... + (n – 1) · (n – 1)! + n · n! = 
= n! – 1 + n · n!
= (n + 1)n! – 1 
= (n + 1)! – 1
contradizendo o fato de que n ∈ X.
21.7 É útil usar um computador para gerar 
os primeiros vários números de Fibo-
nacci e os valores de 1.6n, embora uma 
calculadora manual seja suficiente.
Você deve achar quea desigualdade 
vale para todo n ≥ 29.
21.8 Aqui está um gráfico útil para você co-
meçar.
n Fn F0 + ... + Fn
0 1 1
1 1 2
2 2 4
3 3 7
4 5 12
5 8 20
6 13 33
7 21 54
8 34 88
9 55 143
10 89 232
Compare os números na terceira colu-
na com aqueles na segunda.
21.10 Expresso como um teorema, você pre-
cisa mostrar: Para cada n ∈ , a enési-
ma fileira do triângulo de Pascal é
n
0 ;
n
1 ;
n
2 ; : : :
n
n 1 ;
n
n .
22.2 Nós reivindicamos que, para cada in-
teiro positivo n, o enésimo dominó na 
linha é derrubado.
Prova. A prova é por indução em n. 
Para n = 1 sabemos que somos capa-
zes de derrubar o primeiro dominó. E 
sabemos que se o dominó k cair, então, 
o dominó k + 1 também deve cair. Por-
tanto, por indução, sabemos que para 
todo n, o enésimo dominó deve cair.
22.4 Aqui está uma resposta completa para 
(a).
Prova (por indução em n):
Caso base n = 1. Ambos os lados da 
equação avaliados para 1, portanto, o 
caso base é verdadeiro.
Hipótese de indução: Suponha que 
o resultado seja verdadeiro quando 
n = k.
16 Matemática discreta
Isto é, temos
1 C 4 C 7 .3k 2/ D k.3k 1/
2
. /:
Queremos mostrar
1C4 .3k 2/CŒ3.kC1/ D
.k C 1/Œ3.k C 1/
2
:
Adicione 3(k + 1) – 2 = 3k + 1 em am-
bos os lados de (*) para obter
1C4 .3k 2/C.3kC1/ D k.3k 1/
2
C .3k C 1/
D
.3k2 k/ C .6k C 2/
2
D
3k2 C 5k C 2
2
D .k C 1/.3k C 2/
2
D .k C 1/Œ3.k C 1/
2
:
Para (c), note que esta é uma gene-
ralização sofisticada do fato que 999 = 
1000 – 1.
Aqui está uma resposta completa 
para (f).
Caso base: Começamos a indução 
com n = 0 porque é ligeiramente mais 
fácil. Observe
lim
x!1
x0
ex
D lim
x!1
1
ex
D 0:
Hipótese de indução: Suponha que 
a fórmula valha para n = k. Nós calcu-
lamos:
lim
x!1
xkC1
ex
D lim
x!1
.k C 1/xk
ex
D .k C 1/ lim
x!1
xk
ex
D 0
em que a primeira igualdade é pela re-
gra de L’Hôpital e a última é por in-
dução.
Para (g), é um pouco mais fácil co-
meçar com o caso base n = 0. Para a 
etapa de indução, você usará a integra-
ção por partes.
22.5 Aqui está uma prova de (a):
Caso base n = 1. O lado esquerdo é 
avaliado como 2 e o lado direito como 
4 – 1 – 1 = 2, então o caso base é ver-
dadeiro.
Hipótese de indução: Suponha que 
o resultado seja verdadeiro quando n = 
k, ou seja, nós temos
2k ≤ 2k +1 – 2k–1 – 1. (*)
Queremos provar
2k+1 ≤ 2k+2 – 2k – 1.
Para este fim, multiplicamos ambos os 
lados de (*) por 2: 
2 2k 2 2kC1 2k 1 1
D 2kC2 2k 2
D 2kC2 2k 1 1
2kC2 2k 1:
Para a parte (b), a parte (a) é útil.
22.6 Avalie a soma para n = 1, 2, 3 e assim 
por diante e obtemos os seguintes va-
lores: 0, 2, –1, 4, –4, 9, –12, 22, –33 e 
assim por diante. Observe que, se sub-
trairmos um de todos esses números
– 1, 1, –2, 3, –5, 8, –13, 21,...
e estes são justamente os números de 
Fibonacci com sinais alternados.
Em outras palavras, prove que a 
soma é igual (–1)n Fn–1 + 1 para todo 
n > 0.
22.7 As provas das desigualdades (*) e (**) 
são as partes mais importantes deste 
problema; suas provas são semelhan-
tes às por indução de outras desigual-
dades nesta seção.
Uma vez que você estabeleceu (*) e 
(**) prove ζ (2) ≥ 1 e ζ (2) ≤ 2 cada um 
por contradição. A suposição que ζ (2) 
< 1 implica que todas as somas parciais 
1/12 + ... +1/n2 são menores que 1. A 
suposição de que ζ(2) > 2 implica que 
existe alguma soma parcial 1/12 + ... + 
1/n2 que excede 2.
Na verdade, pode-se mostrar atra-
vés de técnicas mais avançadas que 
ζ(2) = p2/6  1,6449 que é, realmente, 
entre 1 e 2.
17Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
22.9 Este fato é bastante óbvio. O ponto 
aqui é obter prática, escrevendo provas 
por indução. Seja n o número de pes-
soas na linha. No caso base, n = 2.
22.10 O caso base para a indução é n = 3 e 
você pode assumir que a soma dos ân-
gulos de um triângulo é 180°.
A figura a seguir mostra a essência 
da etapa de indução.
X1
X2
X3
X4
Xk
Xk+1P
TQ
22.11 O caso base é fácil, pois ambos os la-
dos são iguais a 1. Para a hipótese de 
indução, suponha que o resultado seja 
verdadeiro para n = m e anote o que 
isso significa. Multiplique ambos os 
lados por (x + y). À direita, recolha os 
termos semelhantes, aplique a identi-
dade de Pascal (Teorema 17.10) e seja 
corajoso através da álgebra.
22.12 A prova é por indução sobre o número 
de discos.
22.13 Sugestão: A “prova” em (a) não mos-
traria, por exemplo, que o conjunto de 
números primos tem um elemento a 
menos; por quê?
22.15 Nós recomendamos que você utilize 
a indução forte sobre o tamanho da 
grade (isto é, o número de pontos na 
grade). O caso base (uma grade com 
apenas um ponto) só tem um caminho 
de canto a canto: o caminho vazio! As-
sim, a fórmula 00 está correta.
Para descobrir a indução, tente 
isto: Em uma grade de 5 × 5, escreva 
o seguinte em cada ponto da grade: o 
número de caminhos a partir do can-
to inferior esquerdo para esse ponto. 
Quando você faz isso, a linha inferior 
dos pontos e a coluna à esquerda de-
les serão todas marcadas com um 1. 
O ponto um passo acima e um passo 
a direita do canto inferior será marca-
do com um 2. E assim sucessivamente, 
até o canto superior direito que deve ser 
marcado com 70 = 84 . O que você vê? 
Observe que os números justamente 
para a esquerda e para baixo de 70 são 
ambos 35 e que 70 = 35 + 35. Por quê?
22.16 Esta é uma resposta completa para (a).
Os próximos três termos da sequên-
cia são a4 = 31, a5 = 63 e a6 = 127.
Para provar: an = 2
n + i – 1.
Caso base: Quando n = 0, apenas 
precisamos notar que a0 = 1 = 2
0+1 – 1 = 
2 – 1, como exigido.
Hipótese de indução: Suponha ak = 
2k+1 – 1.
Precisamos provar que ak+1 = 2
(k+1)+1 
– 1. Note que
akC1 D 2ak C 1 por definição
D 2
h
2kC1 1
i
C 1 por indução
D 2kC2 2 C 1 D 2kC2 1
como requerido.
22.17 Denote an o número de possíveis solu-
ções. Encontre uma relação de recor-
rência para an.
22.18 Use a indução forte. Se n é um número 
de Fibonacci, não há nada para provar. 
Se n não é um número de Fibonacci, 
seja Fk o maior número de Fibonacci 
menor que n. Você vai querer mostrar 
que n – Fk < Fk.
22.19 Usamos a indução em n = last-first.
O caso base é, quando n = 0. Neste 
caso, first é igual a last, de modo 
que o programa retorna array[first], 
que é o único valor sob consideração.
18 Matemática discreta
Hipótese de indução: Assuma que o 
resultado é verdadeiro para todos os 
valores de last-first que são meno-
res que n.
Suponha que o programa seja cha-
mado com last-first = n. Note que 
mid está entre o first e o last e nós 
temos mid < last, então, por indução, 
a linha
a = findMax(array,first,mid);
define a variável a para o maior valor 
na matriz first ao índice last. Além 
disso, mid+1 é maior que first,, assim, 
por indução, a linha
b = findMax(array,mid+1,last);
define b ao maior valor na matriz do 
índice mid+1 para o índice last.
Finalmente, as duas últimas linhas 
do programa retornam o maior de a e 
b, que deve ser o maior valor na matriz 
do índice first ao índice last.
22.21 O ponto deste problema é que você não 
deve ser capaz de fazer este problema! 
A resposta completa correta para este 
problema é: “Eu desisto! ”
Na prova neste livro, utilizamos a 
seguinte hipótese de indução:
Hipótese de indução 1: Cada polígo-
no triangular com a maioria dos lados 
k tem pelo menos dois triângulos ex-
teriores.
Seu trabalho é tentar trabalhar a 
partir desta hipótese de indução: Hi-
pótese de indução 2: Cada polígono 
triangular com a maioria dos lados k 
tem pelo menos um triângulo exterior.
A hipótese 1 é mais fácil de usar 
porque lhe dá mais influência. Isto é 
conhecido como carregamento por in-
dução.
22.22 Lembre-se das seguintes fórmulas de 
ângulo-soma para seno e cosseno:
sen.˛ C ˇ/ D sen ˛ cos ˇ C senˇ cos ˛
cos.˛ C ˇ/ D cos ˛ cos ˇ sen˛ senˇ
É difícil provar estas identidades uma 
de cada vez; é muito melhor prová-las 
em uma única prova; este é um outro 
exemplo de carregamento por indução.
22.23 A prova é similar a do Teorema 22.2.
22.24 Aqui estão as primeiras poucas linhas 
de uma prova para vocêcomeçar.
O caso base é 0. Neste caso pode-
mos escrever 0 como uma soma vazia.
Seja n um inteiro positivo e supo-
nha que o resultado foi mostrado para 
todos os números naturais menores 
que n. Seja k o maior número natural 
tal que 2k ≤ n. (Há apenas um número 
finito de números naturais ≤ n e 20 ≤ n; 
assim k existe.)
23.1 Aqui está uma resposta completa para 
(a).
a0 D 1 (dado)
a1 D 2a0 C 2 D 2 1 C 2 D 4
a2 D 2a1 C 2 D 2 4 C 2 D 10
a3 D 2a2 C 2 D 2 10 C 2 D 22
a4 D 2a3 C 2 D 2 22 C 2 D 46
a5 D 2a4 C 2 D 2 46 C 2 D 94:
Para as outras partes, aqui está a5: (b) 
20, (c) 11, (d) 0, (e) 15 e
23.2 (a) an D 4. 23 /n. a9 D 211=39 D 2048=19683.
(e) an D 192 .3/n C
1
2
. a9 D 186989.
(h) an D 2 2n 2. a9 D 1022.
(n) an D 5. 1/n 6n. 1/n. a9 D 49.
(o) an D 32 .1C
p
3/n C 3
2
.1
p
3/n. a9 D 12720.
23.3 Aqui está uma solução completa para 
(b). Anotamos as sequências an, Dan, 
D2an, e assim por diante até alcançar-
mos a sequência de todos-zeros:
6 5 6 9 14 21 30
1 1 3 5 7 9
2 2 2 2 2
0 0 0 0
19Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
Então, usamos os primeiros termos 
de cada linha e aplicamos o Teorema 
23.17 para obter
an D 6
 
n
0
!
C . 1/
 
n
1
!
C 2
 
n
2
!
D 6 n C n.n 1/ D n2 2n C 6:
23.4 O operador da diferença aplica-se na 
sequências, não aos números indi-
viduais. A notação (Da)n significa o 
enésimo termo da sequência Da; este 
é o significado pretendido. A notação 
D(an) não está definida, desde que an 
é um número e não atribuímos um sig-
nificado para D, aplicado a um único 
número.
23.5 Seja k um inteiro positivo e seja an = 
n
k . 
Sabemos que n D nk D nk 1 . Re-
petindo isso, vemos que j an D nk j . 
Assim, temos
a0 D
 
0
k
!
D 0
0 D
 
0
k 1
!
D 0
2a0 D
 
0
k 2
!
D 0
:::
k 1a0 D
 
0
k .k 1/
!
D
 
0
1
!
D 0;
mas ka0 D 00 D 1.
23.6 Podemos expressar an na forma c1r
n
1 + 
c2r
n
2 em que r1, r2 são as raízes de uma 
equação quadrática. Encontre r1, r2 pri-
meiro. Em seguida, crie duas equações 
e duas incógnitas para encontrar c1, c2.
23.8 Seja an = 1
t + 2t + ... + nt. Note que Dan 
= (n + 1)t. Aplique D outras t + 1 ve-
zes. O que você obtém? Use o Teorema 
23.17 para concluir que an pode ser es-
crito como uma expressão polinomial.
23.10 Por exemplo, quando s = 3, precisamos 
resolver an = 3Dan. Lembre-se que Dan 
= an+1 – an, portanto, o que realmente 
queremos resolver é an = 3(an+1 – an), 
que pode ser rearranjado para an+1 = 
4
3
an. Esta recorrência não está exatamen-
te na forma padrão mas é equivalente a 
an = 
4
3
an–1.
23.11 Resposta para (a): a5 = 80.
23.12 D2an = an+2 – 2an+1 + an.
23.14 (a) A resposta é an = 3
n – 2n + 1.
(d) A forma da respostas é an = c15
n + 
c2 + c3n.
(e) A forma da respostas é an = c13
n + 
c2n3
n + c3.
(f) an é dado por um polinômio qua-
drático.
23.15 Aqui está uma solução completa para 
(a). Pela relação de recorrência an = 
4an–1 – an–2 – 6an–3, formamos a equa-
ção cúbica associada x3 – 4x2 + x + 6 
= 0. Estes fatores (x – 2)(x – 3)(x + 1) 
= 0; portanto, as raízes são 2, 3 e –1. 
Esperamos, portanto, que an seja da 
forma c12
n + c23
n + c3(–1)
n.
Agora usamos os valores para a0, a1 
e a2 para resolver para c1, c2, c3:
 a0 = 8 = c1 + c2 + c3 
 a1 = 3 = 2c1 + 3c2 – c3 
 a2 = 27 = 4c1 + 9c2 + c3.
Isto dá c1 = 1, c2 = 2 e c3 = 5. Portanto,
an = 2
n + 2 · 3n + 5(–1)n.
23.16 Implemente este programa em sua lin-
guagem favorita. No início do proce-
dimento, adicione uma declaração de 
depuração que imprima o argumento. 
Algo como isso:
print ’Calling get_term with argument ’ n
Agora chame get_term(10) e veja o 
que acontece.
Note que para calcular a0 ou a1, 
apenas uma chamada para get_term 
é gerada. Para computar a2, três cha-
20 Matemática discreta
madas são geradas (a chamada original 
get_term(2) além das duas chamadas 
incorporadas.
Para calcular a3, get_term é cha-
mado cinco vezes: uma vez para a 
chamada original get_term(3) e, em 
seguida, chama get_term(2) (três 
chamadas para fazer isso) e get_
term(1) (uma chamada para esse). Os 
primeiros poucos valores de bn são 1, 
1, 3, 5, 9, 15, 25.
23.17 Para (a), utilizar a recorrência para 
gerar os valores a1, a2, a3, a4, mas não 
realizar as multiplicações reais.
A resposta para (b) é an = 2
(2n).
Para (c), escreva os primeiros vá-
rios valores. Você notará que an não 
se encaixa exatamente no padrão que 
você deve observar. É bom relatar sua 
resposta na forma
an D
(
1 se n D 0,
uma fórmula se n > 0.
A parte (d) também tem a dificulda-
de que a0 não se encaixa no padrão dos 
termos subsequentes. Tente encontrar 
uma recorrência de segunda ordem da 
forma an = s1an–1 + s2an–2 que funciona 
quando n ≥ 3 e resolva isto.
A parte (e) é um problema não re-
solvido. Os valores an são chamados 
caóticos, e não espera-se que exista 
nenhuma fórmula razoável.
23.18 A sequência c0, c1, c2, ... começa 1, 1, 2, 5, 
14. Você deve descobrir que c8 = 1.430.
Resposta para (d): Estes são os nú-
meros pentagonais.
Para (e): Você pode notar esta se-
quência se visitar um edifício alto e 
sofre de triscaidecafobia.
24.1 Uma resposta completa para (a): f é uma 
função, dom f = {1, 3} e im f = {2, 4}. f 
é um-para-um e f –1 = {(2, 1), (4, 3)}.
24.2 Existem tais funções 23 e nenhuma de-
las é um-para-um.
Uma das funções é {(1, 4), (2, 4), 
(3, 4)}; não é nem um-para-um nem 
sobre.
24.3 Existem tais funções 32, e nenhuma de-
las está sobre B.
Uma das funções é {(1, 3), (2, 3)}. 
Não é nem um-para-um nem sobre B.
24.4 Aqui está uma resposta completa.
Função Um-para-um? Sobre?
{(1, 3), (2, 3)} não não
{(1, 3), (2, 4)} sim sim
{(1, 4), (2, 3)} sim sim
{(1, 4), (2, 4)} não não
24.6 Resposta para (b): im f = , os núme-
ros naturais (isto é, os inteiros não ne-
gativos).
24.7 (a) Para mostrar que f não é um-para-
-um, encontre dois elementos diferen-
tes de A, digamos a1 e a2, dos quais 
f(a1) = f(a2).
(b) Para mostrar que f não é sobre, en-
contre um elemento b ∈ B e prove que 
não há a ∈ A de modo que f(a) = b.
24.9 Resposta para (a): Uma função f é um-
-para-um quando cada linha horizontal 
intercepta o gráfico de f no máximo 
uma vez. Aqui está a prova:
(⇒) Suponha que f seja um-para-
-um e suponha, por contradição, que 
alguma linha horizontal (com a equa-
ção y = b) intercepta o gráfico de f em 
dois (ou mais) pontos distintos, diga-
mos (x1, b) e (x2, b). Isso significa que 
f(x1) = b e f(x2) = b, mas então f(x1) = 
f(x2) contradizendo o fato de que f é 
um-para-um. Portanto, cada linha ho-
rizontal intercepta o gráfico de f no 
máximo uma vez. ⇒ ⇐ Portanto, toda 
linha horizontal intersecta o gráfico de 
f no máximo uma vez.
21Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
(⇐) Suponha que cada linha ho-
rizontal intercepta o gráfico de f no 
máximo uma vez. Para mostrar que f é 
um-para-um, usamos o Modelo da Pro-
va 20. Suponha que temos f(x1) = f(x2) 
= b, para algum número real b. Então a 
linha horizontal y = b intercepta o grá-
fico em (x1, b) e (x2, b). Uma vez que 
esta linha horizontal intercepta o gráfi-
co de f no máximo em um ponto, estes 
dois pontos devem ser os mesmos, isto 
é, x1 = x2. Portanto f é um-para-um.
24.10 Aqui está uma solução completa.
Se a ¤ 0 então f é tanto um-para-
-um como sobre.
Um-para-um. Suponha que f(x) = 
f(y). Então ax + b = ay + b. Subtraindo 
b de ambos os lados dá ax = ay e de-
pois dividindo por a dá x = y. Portanto 
f é um-para-um. 
Sobre. Seja y qualquer número real. 
Precisamos encontrar um x de modo 
que f(x) = y. Pegando x = (y – b)/a cal-
culamos
f(x) = f [(y – b)/a] = a[(y – b)/a] + b = [y – b] + b = y
e assim f é sobre.
Se a = 0, então f não é nem um-pa-
ra-um nem sobre.
Para mostrar que f não é um-para-
-um, notamos que f(1) = b e f(2) = b. 
Para mostrar que f não é sobre, consi-
dere qualquer número real c ¤ b. En-
tão, para qualquer x, f(x) = b assim não 
existe x de modo que f(x) = c.
24.11 Quando a = 0, reduz para o Exercí-
cio 24.10. Quando a ¤ 0, o gráfico de 
f é uma parábola e você pode aplicar o 
Exercício24.9. Alternativamente, uma 
solução algébrica pode ser desenvolvida.
24.12 Em (a), não existe um conjunto explícito 
B para o qual a definição se aplica. Em 
particular, cada função f é sobre se pen-
sarmos B como sendo a imagem de f.
Em (b), a notação f : A ! B estabe-
lece um contexto para a frase “f é so-
bre.” Neste contexto, o problema é: im 
f é igual a B?
24.14 Aqui está uma resposta completa para 
(a).
Primeiro, f é um-para-um. Prova: 
Precisamos mostrar que, se f(a) = f(b), 
então a = b. Assim, suponha que temos 
inteiros a, b com f(a) = f(b). Por defi-
nição de f, temos 2a = 2b. Dividindo 
ambos os lados por 2 dá a = b. Portanto 
f é um-para-um.
Segundo, f não é sobre. Prova: 
Afirmamos que 1 ∈ , mas não existe 
x ∈  com f(x) = 1. Suponha, por uma 
questão de contradição, que existe um 
número inteiro x tal que f(x) = 1. Então 
2x = 1, e assim x = 12. Contudo. 
1
2 não 
é um inteiro, por isso, não há inteiro x 
com f(x) = 1. Portanto, f não é sobre.
24.16 Esse problema requer que você escre-
va três provas:
1. Se (a) e (b), então (c).
2. Se (a) e (c), então (b).
3. Se (b) e (c), então (a).
Para  esta  finalidade,  a  Proposição 
24.24 (o Princípio de Pigeonhole) é 
muito útil.
24.19 Note que se d é um divisor positivo 
de n, então também é n/d. O Exercício 
5.17 é útil.
24.20 Quantos subconjuntos de A têm exata-
mente k elementos?
24.22 Veja os Exercícios 17.29 e 17.30.
24.23 (a) f (X) = {0, 1, 2}.
(c) f (X) = [1
2
, 2].
24.24 Resposta para (a): f –1(Y) = {–3, –2, –1, 
1, 2, 3}.
25.1 Se N ≥ 1010 então N tem 11 (ou mais) 
dígitos. Como há apenas 10 dígitos 
possíveis, deve haver uma repetição.
25.2 Não esqueça o 29 de fevereiro!
22 Matemática discreta
25.4 Número de cabelos na cabeça de uma 
pessoa: Cerca de 100.000.
25.5  Quantos diferentes padrões de <s e >s 
são possíveis em uma sequência de 
cinco inteiros distintos?
25.7 Crie seis categorias de inteiros com 
base em seus dígitos. Uma vez que 
existem sete inteiros no conjunto, dois 
destes devem estar na mesma categoria.
25.9 Aplique o Princípio de Pigeonhole, fa-
zendo buracos de pombo no quadrado.
25.10 Pense sobre a paridade das coordenadas.
25.11 O número 9 deve aparecer em sua pro-
posição.
25.12 Aqui está uma sequência de compri-
mento nove sem subsequência monó-
tona de comprimento quatro.
3 2 1 6 5 4 9 8 7.
Tente generalizar isso e use o Princí-
pio de Pigeonhole em sua prova de que 
a sequência não contém uma subsequên-
cia monótona de comprimento n + 1.
25.14 Se a sequência tem comprimento n, 
então ela tem 2n subsequências. Mes-
mo para valores moderados de n, é 
altamente ineficiente tentar verificar 
através de todas as sequências. Em vez 
disso, use o sistema de rotulagem na 
prova do Teorema 25.3.
26.1 (a) g B f = {(1, 1), (2, 1), (3, 1)} e f B g 
= {(2, 2), (3, 2), (4, 2)}; g B f ¤ f B g.
(c) g B f = {(1, 1), (2, 5), (3, 3)} mas 
f B g é indefinido.
(g) (g B f)(x) = x + 1 e (f B g)(x) = x – 1; 
g B f ¤ f B g.
26.8 Quais são o domínio e a imagem de 
 f B f–1?
26.11 A resposta para ambos é sim se o con-
junto A é finito. No entanto,…
26.12 A parte (a) que já foi tratada no Exer-
cício 26.9. A parte (b) é falsa; encontre 
um contraexemplo. A parte (c) é verda-
deira; use o Exercício 26.7.
26.14 Resposta para (a): f (n)(1) = 2n+1 – 1.
Prova. Por indução em n. Para o caso 
base, n = 1, temos f(1) = 3 e 2n+1 – 1 = 
22 – 1 = 3, de modo que o resultado é 
verdadeiro para n = 1.
Suponha que a fórmula esteja cor-
reta quando n = k, isto é, f (k)(1) = 2k+1 
– 1. Então,
f .kC1/.1/ D .f ı f .k//.1/ D f
h
2kC1 1
i
D 2
h
2kC1 1
i
C 1 D 2kC2 2 C 1
D 2.kC1/C1 1
como requerido.
26.15 Qual função é aplicada primeiro na no-
tação afg versus f B g?
27.2 A resposta para (a) é (1, 2, 4)(3, 6, 5).
27.3 Para n = 3 a resposta é duas: (1, 2, 3) e 
(1, 3, 2). Para n = 4 a resposta é seis.
27.4 Este é um problema desordenado.
27.5 A resposta para (a) é (1, 4, 7, 6, 9, 3, 
2,5, 8) e a resposta para (b) é diferente. 
A resposta para (d) é (1)(2, 5, 4, 3)(6, 
9, 8, 7), embora isto também possa ser 
escrito (1)(5, 4, 3, 2)(9, 8, 7, 6).
27.6 Isso é falso.
27.8 Isso foi tratado em um problema na Se-
ção 26.
27.11 Note que para qualquer transposição t, 
temos t B t = i. Portanto, t–1 = t.
Para provar que duas permutações 
são inversas uma da outra, apenas as 
componha e mostre que a resposta 
deve ser i.
27.12 Suponha p não tenham nenhum.
27.15 É dado p B s = s. Compor à direita por 
s–1 dá 
ı D
ı ı 1 D ı 1
ı ı 1/ D
ı D
D
27.17 A resposta para (a) é que p = (1, 2)(2, 
3)(3, 4)(4, 5), tem quatro inversões, e 
ele é par.
23Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
27.18 Uma grande sugestão: Desenhe a fi-
gura de uma seta da esquerda para a 
direita da permutação e sua inversa, e 
conte os cruzamentos.
27.21 Imagine que o espaço em branco leva 
o número 16. Então, vários movimen-
tos do quebra-cabeça resultam em uma 
permutação dos números de 1 a 16. Em 
particular, um único lance de Fifteen 
Puzzle é uma transposição.
27.22 Para(a) você deve encontrar que 
P D
" 0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
#
.
Para (d), você deve provar que 
Ps · Pp = PpBs. Para fazer isso, note que 
a entrada ij de Ps · Pp é calculado como 
segue:
ŒP P ij D
nX
kD1
ŒP ik ŒP kj :
Esta soma é zero a menos que haja um 
k tal que [Ps]ik = [Pp]kj = 1. Quando isso 
acontece?
Para (e), mostre que Pp e Pp–1 são 
inversos um do outro, multiplique es-
tas duas matrizes e mostre que a ma-
triz de identidade é o resultado. Então, 
para mostrar que PTp = Pp–1, funcionam 
onde o 0s e 1s destas duas matrizes de-
vem ficar.
28.1 Por favor, note que
R90 D .1; 2; 3; 4/;
FH D .1; 2/.3; 4/; e
Fn D .1/.2; 4/.3/:
Agora calcule (1, 2)(3, 4) o (1, 2, 3, 4).
28.2 Você deve encontrar quatro simetrias 
de um retângulo.
28.4 Há seis simetrias de um triângulo equi-
látero.
28.5 Existem duas simetrias.
28.7 Há dez simetrias: uma identidade, qua-
tro rotações e cinco giros.
28.10 A resposta para (c): A diferença é que 
as primeiras 24 simetrias envolvem a 
rotação do cubo. A segunda coleção de 
24 são as imagens de espelho das pri-
meiras 24.
28.11 Uma rotação através de um ângulo  
pode ser representada pela matriz
h
cos sen
sen cos
i
.
29.1 Para (b), expanda 1,1n usando o Teore-
ma Binomial:
1:1n D .1 C 0:1/n
D 1nC
 
n
1
!
1n 1.0:1/1C
 
n
2
!
1n 2.0:1/2
e dispense os termos que você não pre-
cisa.
29.2 (c) é falso. Por exemplo, [0,7 + 0,8] = 
[1,5] = 1, mas [0,7] + [0,8] = 0 + 0 = 0.
29.3 Aqui está uma prova completa.
Como f(n) é O(g(n)), há um número 
positivo A de modo que, com no máxi-
mo uma quantidade finita de exceções,
|f(n)| ≤ A|g(n)|.
Similarmente, como g(n) é O(h(n)), 
existe um número positivo B tal que, 
no máximo muitas exceções finitas,
|g(n)| ≤ B|h(n)|.
Combinando essas duas desigualdades 
temos,  no  máximo  um  número  finito 
de exceções,
|f(n)| ≤ A|g(n)\ ≤ AB|h(n)|
Suponha que f(n) seja O(g(n)).
29.4 Aqui está uma resposta completa: Por 
definição, existe um número M0 de 
modo que |f(n)| ≤ M0 para todos, mas 
um número finito de valores de n. Seja 
M qualquer número maior que M0 e to-
dos os valores de f(n) em que n é uma 
24 Matemática discreta
exceção para | f(n) | ≤ M0. Então | f (n)| 
≤ M para todo n.
29.5 Há apenas muitos números finitos n ∈ 
 de modo que f(n) ¤ 0.
29.9 Use a identidade
loga n = (logb a) (loga n).
29.11 A resposta é ou 
l
x 1
2
m
ou
j
x C 1
2
k
.
29.12 A resposta para este problema seria 
muito fácil se você fosse autorizado a 
utilizar a função mod; seria apenas n 
mod 10.
29.13 Se x é um número inteiro, a expressão 
é avaliada como 0. Caso contrário, es-
creva x = n + t em que n é um número 
inteiro e 0 < t < 1. Considere os casos  
t ≥ 12 e t > 
1
2 separadamente.
29.14 Devemos mostrar que
lim
x!1
xn
ex
D 0:
Proceda por indução em n. Lembre-se 
da regra de L’Hôpital.
29.15 Aproxime R n
1
dx
x
 pela soma da área dos 
retângulos acima e abaixo da curva y = 
1/x.
30.1 x = 0,6.
30.3 Existe, na verdade,três equações, a 
terceira sendo x + y + z = 1. Agora re-
solva.
30.5 Se fosse assim, então o que você pode 
dizer sobre a soma das probabilidades 
dos resultados nos dois espaços amos-
trais?
30.7 Um resultado desta experiência pode 
ser registrado como (a, b) em que a 
é ou H ou T (o resultado da virada da 
moeda) e b é um número inteiro com 1 
≤ b ≤ 6 (a face de cima do dado). Assim,
S D
˚
.H; 1/; .H; 2/; .H; 3/;
.H; 4/; .H; 5/; .H; 6/;
.T; 1/; .T; 2/; .T; 3/;
.T; 4/; .T; 5/; .T; 6/ :
Todos esses resultados 2 × 6 = 12 são 
igualmente prováveis, portanto, P : 
S !  é dado por P(s) = 112 para todo 
s ∈ S
30.8 Para (a): O espaço amostral é (S, P) em 
que S = {1, 2, 3, 4} e P(s) = 14 para to-
dos s ∈ S.
30.9 Uma resposta completa para (b): O 
conjunto S consiste de todos os sub-
conjuntos de 5 elementos do conjunto 
{1, 2, ..., 20}. Assim, |S| = 205 . Todos 
esses resultados são igualmente prová-
veis, então, P(s) = 1/ 205 para todo s ∈ S.
30.10 Aqui está a resposta para a região 3: 
P(3) = 516
Explicação: A área total do alvo (to-
das as quatro regiões juntas) é de 16p. 
A área da região 3 é de 9p – 4p = 5p. 
Então região 3 cobre 5
16
 da área total.
30.11 Seja S = {1, 2, 3} e seja P(1) = 1, P(2) 
= 0, e P(3) = 0.
30.12 Seja S = {1} e seja P(1) = 1.
Note que se um espaço amostral (S, 
P) tem dois (ou mais) elementos, não 
podemos ter P(s) = 1 para todo s ∈ S; 
se |S| > 1, então
X
s2S
P.s/ D
X
s2S
1 D jS j > 1
que é proibido.
30.13 Veja a discussão “Muito barulho por 
0!” na Seção 9.
30.14 Para (b), lembre-se que a soma da série 
geométrica infinita a + ar + ar2 + ... é a/
(1 – r). Você deve derivar que a + r = 1.
25Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
31.1 Solução para (a): A = {2, 4, 6, 8,10} e 
P(A) = 12.
31.2 Aqui está a resposta para k = 4. Temos 
A4 = 3 (2,2), (3,1)} e P(A4) = 316.
31.3 A = {hhtt, htht, htth, thht, thth, tthh}, e 
P(A) = 616 D
3
8
.
Note que |A| = 42 = 6.
31.6 (a) A = {HTHTHTHTHT, THTHTH-
THTH}. (b) P(A) = 2/210 = 2–9 = 1/512.
31.7 A = {(2, 6), (3, 5), (4, 4), (5, 3), (6, 2)}.
31.10 O conjunto A contém 1 + 2 + 3 + 4 + 5 
resultados.
31.11 Chame as caixas 1, 2, 3,..., 10. O espa-
ço amostral S contém todas as listas de 
comprimento dois de caixas sem repe-
tição. Portanto, |S| = (10)2 = 90. Vamos 
assumir que a caixa 1 seja a menos va-
liosa e assim por diante, até a caixa 10 
ser a mais valiosa. Agora este proble-
ma é como o problema anterior.
31.12 Para comparar os dados 1 e 2 fazemos 
um gráfico. As linhas do gráfico são 
indexadas pelos números no dado 1 e 
as colunas pelos números no dado 2. 
Nós colocamos uma * para cada com-
binação em que o dado 1 ganha do 
dado 2.
2 3 4 15 16 17
5 * * *
6 * *
7 * * *
8 * * *
9 * * *
18 * * * * * *
Note que existem 21 maneiras em que 
1 vence 2, portanto, a probabilida-
de de que o dado 1 vença o dado 2 é 
21
36
D 7
12 58,33%.
31.13 Aqui está uma resposta completa para 
(b). Há 13 escolhas para o qual o valor 
será usado no triplo e para cada tal va-
lor, 43 = 4 escolhas das quais os cartões 
serão utilizadas nesse triplo. Dada a es-
colha do triplo, existem 12 opções para 
cujo valor será usado no par. Dado o 
valor, existem 42 = 6 opções para cada 
carta que usamos no par. Assim, exis-
tem 13 × 4 × 12 × 6 = 3.744 diferentes 
casas cheias. Por conseguinte, a proba-
bilidade de escolher uma casa cheia é
3744
52
5
D
3744
2598960
D
6
4165
0,14%:
As respostas numéricas aproximadas 
para as outras partes são as seguintes:
(a) 2,11%, (c) 42,26%, (d) 4,75% e 
(e) 0,198%.
31.14 Por convenção, uma soma vazia tem 
valor 0, então P(;) = 0.
Este P(S) = 1 decorre da definição 
de espaço amostral.
Se A \ B = ;, então P(A [ B) = 
P(A) + P(B) – P(A \ B) = P(A) + P(B) 
– P(;) = P(A) + P(B).
31.15 (a) 105 =210 D 63256 24,61%
(b) 27/210 = 2–3 = 18 = 12,5%.
(c) 72 =210 D 211024 2,05%.
(d) Pela Proposição 31.7, a probabili-
dade é
10
5
210
C
27
210
7
2
210
D
359
1024
35,06%:
31.16 Este problema pode ficar confuso, por 
isso, ele ajuda a ter uma boa notação. 
Seja A o evento que vemos pelo menos 
um 1, e seja B o evento que vemos pelo 
menos um 2. As partes deste problema 
pedem pelo seguinte:
(a) P(A).
(b) P(A) = 1–P(A).
(c) P(B) (que é o mesmo que P(A)).
(d) P(A [ B). Note que isto é o mesmo 
que P(A [ B).
(e) P(A [ B) = 1 – P(A [ B).
(f) P(A \ B) = P(A) + P(B) – P(A [ B).
31.17 Note que (A \ B) \ (A \ B) = ;. Tam-
bém note que (A \ B) [ (A \ B) = A. 
26 Matemática discreta
Portanto,
P.A/ D P .A \ B/ [ .A \ B/
D P.A \ B/ C P.A \ B/ P.;/
D P.A \ B/ C P.A \ B/:
31.18 Aqui está a prova. Note que
P.A/ D
X
s2A
P.s/ e P.B/ D
X
s2B
P.s/:
Como A ⊆ B, cada termo na primei-
ra soma também está presente na se-
gunda. Uma vez que as probabilidades 
são não-negativas, isto implica que a 
segunda soma é pelo menos tão grande 
quanto a primeira; isso é, P(B) ≥ P(A).
31.20 Use a prova por contradição.
31.21 Use a Proposição 31.8 e a indução.
31.22 P(A \ A) = P(;) = 0. Interpretação: 
É impossível para um evento, ambos 
ocorrerem e não ocorrerem.
31.24 k = 57.
32.1 Complete a resposta para (a): P(A|B) = 
P(A \ B)/P(B) = P({2, 3})/P({2, 3, 4}) = 
0,3/0,5 = 3/5 = 60%.
32.3 Aqui está uma resposta completa. Seja 
A o evento que nenhum dado mostra 
um 2 e seja B o evento que eles somam 
a 7. Note que P(B) = 636 = 
1
6. Portanto, 
A \ B = {(1, 6), (3, 4), (4, 3), (6, 1)}. 
Portanto, P(A \ B) = 436 D
1
9. Assim, 
P(A|B) D P.A\B/P.B/ D
1=9
1=6
D 6
9
D 2
3
.
32.4 Este problema não é o mesmo que o 
anterior e possui uma resposta diferen-
te. Neste problema você precisa en-
contrar P(B|A), enquanto no problema 
anterior você encontrou P(A|B). A res-
posta é P(B|A) = 425 .
32.6 Nominalmente, você precisa provar 
(1) ⇐⇒ (2), (1) ⇐⇒ (3) e (2) ⇐⇒ 
(3). No entanto, é suficiente provar (1) 
⇒ (2) ⇒ (3) ⇒ (1). Ou mais simples 
ainda, apenas provar (1) ⇐⇒ (3) por-
que (2) ⇐⇒ (3) tem uma prova idênti-
ca. Estes dois implicam (1) ⇐⇒ (2).
32.7 Eventos disjuntos não são, em geral, 
independentes. Por exemplo, conside-
re o rolamento de um dado. Seja A o 
evento que rolamos um número par e 
seja B o evento que rolamos um núme-
ro ímpar. Então, P(A \ B) = 0 ¤ P(A)
P(B) = 14 .
32.11 Duas sugestões: Primeira A \ B e A \ B 
são eventos disjuntos, portanto, P(A \ 
B) + P(A \ B) = P[(A \ B) [ (A \ B)]. 
Segundo, (A \ B) [ (A \ B) = A \ (B 
[ B) por esta propriedade distributiva.
32.12 A resposta é sim em ambos os casos. 
Use as fórmulas P(A|B) = P(A \ B)/
P(B) e P(B|A) = P(A \ B)/P(A) para 
mostrar por quê.
32.13 Sim. Suponha P(A|B) > 0. Isso diz que 
P(A \ B)/P(B) > 0. Portanto, P(A \ B) 
> 0. Como A ≥ B \ A, temos (ver Exer-
cício 31.18) P(A) ≥ P(A \ B) > 0.
32.15 Para a equação fazer sentido, precisa-
mos do fato que P(A) ¤ 0 (do contrá-
rio P(B|A) é indefinido). Isso decorre 
do Exercício 31.18 porque A ⊆ A \ B, 
portanto, P(A) ≥ P(A \ B) > 0. Agora 
é só usar a definição da probabilidade 
condicional.
32.16 Para (b), note que Ak+j \ Aj = Ak+y.
Para (c), seja a = P(0) = 1 – P(A1). 
Primeiro prove que P(Ak) = (1 – a)
k 
(use a indução) e depois use isso para 
calcular P(k) = P(Ak) – P(Ak+1).
32.17 (a) P(A) = 1352 D
1
4
.
(b) P(B) = 452 D
1
13
.
(c) P(A \ B) = 152 .
(d) Sim, porque P(A \ B) = P(A)P(B).
32.18 Você precisa calcular P(A), P(B) e 
P(A \ B) e verificar se P(A)P(B) = 
P(A \ B). Você deve descobrir que 
P(A \ B) = 1221 .
32.19 A princípio, você precisa calcular 
P(A), P(B), e P(A \ B) e verificar se 
P(A)P(B) = P(A \ B). No entanto, para 
27Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
este problema, note que P(A \ B) = 0, 
mas P(A)P(B) ¤ 0. Portanto, os even-
tos não são independentes.
32.21 Aplique a Definição 32.5 diretamente.
32.23 Ambas as afirmações são verdadeiras. 
Para (a) use o Exercício 31.17. Para 
(b), use (a).
32.25 Todas as três são falsas! Aqui está um 
contraexemplo para (a). Suponha que o 
espaço amostral seja o espaço amostral 
par-de-dados do Exemplo 30.4. Deixe 
os três eventos serem como segue:
– A, os dadossomam 2; isto é, A = 
{(1, 1)},
– B, os dados somam 17; ou seja, B = ;, e 
– C, os dados somam 12; isto é, C = 
{(6, 6)}.
Note que A e B são independentes (por-
que P(B) = 0 — ver Exercício 32.24) e 
B e C são independentes (de novo, por-
que No entanto, P(B) = 0). No entanto, 
A e C não são independentes porque
P.A \ C / D 0 6D 1
362
D P.A/P.C /:
32.26 S2 = {(1,1), (1,2), (1,3), (1,4), (2,1), 
(2,2), (2,3), (2,4), (3,1), (3,2), (3,3), 
(3,4), (4,1), (4,2), (4,3), (4,4)}.
Suas probabilidades são as seguintes:
D 1
4
D 1
8
D
1
16
D
1
16
D 1
8
D 1
16
D 1
32
D 1
32
D 1
16
D 1
32
D
1
64
D
1
64
D
1
16
D
1
32
D 1
64
D 1
64
32.27 Seja A o evento em que os dois giros 
somam 6. Como um conjunto, A = {(2, 
4), (3, 3), (4, 2)}. Portanto,
P.A/ D 1
4
1
8
C 1
8
1
8
C 1
8
1
4
D 5
64
:
32.29 (a) A = {hhttt, hthtt, httht, httth, thhtt, 
ththt, THTTH, TTHHT, TTHTH, 
TTTHH}.
(b) P(A) = 10p2(1 – p)3.
32.30 O conjunto A contém sequências nh , 
todas têm a mesma probabilidade.
32.31 Resposta para (a): p(1 – p).
Para (c), lembre-se que P(A|A [ B) 
D P ŒA\.A[
P.A[B/ .
32.32 Olivia.
32.33 (a) a0 = 0 e a2n = 1.
(b) ak = pak+1 + qak–i (em que q = 1 – p).
(c) Existe uma fórmula para ak da for-
ma ak = c1 + c2s
k em que c1, c2 e s são 
números específicos e s ¤ 1.
Use a parte (b) para encontrar s e use a 
parte (a) para encontrar c1, c2.
33.1 Resposta completa para (a): “X > 3” é 
o conjunto
{s ∈ S : X(s) > 3} = {c, d}
e P(X > 3) = 0,7.
Comentário para (c): O evento “X > 
Y” é o conjunto {s ∈ S : X(s) > Y(s)}. 
Quais a, b, c e d estão neste conjunto?
Sugestão para (f): É verdade que 
P(X = m ∧ Y = n) = P(X = m)P(Y = n) 
para todos os inteiros m e n?
33.2 Aqui está uma resposta completa para 
este exercício.
(a) Os valores de s de modo que (X)
(s) = 2s < 10 são 1, 2, 3 e 4. Portanto,  
P(X < 10) =  410 D
2
5
.
(b) Os valores de s de modo que (Y)(s) 
= s2 < são 10 P(Y < 10) =  310 .
(c) (X + Y)(s) = X(s) + Y(s) = 2s + s2.
(d) Os valores de s de modo que Y(s) = 
s2 < 10 são e 2. Portanto, P(X + Y < 10) 
= 210 D
1
5
.
(e) O único valor de s de modo que 
X(s) > Y(s) é 1. Portanto, P(X > Y) = 110 .
28 Matemática discreta
(f) O único valor de s de modo que X(s) 
= Y(s) é 2. Portanto, P(X = Y ) = 110 .
(g) X e Y não são independentes. Por 
exemplo, P(X = 2) = 110 ., P(Y = 1) = 
1
10
., 
mas P(X = 2 ∧ Y = 1) = 0 ¤ P(X = 2)
P(Y = 1).
33.3 Aqui está uma solução completa.
(a) Seja (S, P) o espaço de amostra 
para o girador, assim S = {1, 2, 3, 4}. 
Então X : S !  é definido por X(1) = 
10, X(2) = 20, X(3) = 10 e X(4) = 20.
(b) O evento “X = 10” é o conjunto {1, 3}.
(c) P(X = 10) = 12 C
1
8
D 5
8 e P(X = 20) 
= 38. Para todos os inteiros a (ou seja, 
a ¤ 10 e a ¤ 20), temos P(X = a) = 0.
33.4 A resposta para (c) é 48 D
1
2
.
33.5 A resposta para (a) é 3.
P.X D 1/ D 10
36
D 5
18
. P.X 2/ D 0.
33.7 Se a < 0 ou a > 10 então P(X = a) é 
zero. Do contrário, isso é apenas como 
uma variável binomial aleatória em 
que a probabilidade de sucesso é 1
6
.
33.8 Não. Note que P(Xh = 1) = P(XT = 1) 
>  0, mas P(XT = 1 ∧ Xh = 1) = 0 ¤ 
P(Xh = 1)P(Xh = 1).
33.9 Calcule P(X1 = 5), P(X2 = 5) e P(X1 = 5 
e X2 = 5).
33.10 
P.X D 5/ D 105
1
2
5
1
2
5
D 252
1024
D 63
256
0,246.
33.13 Use a primeira parte para mostrar que 
P(X é par) = P(X é ímpar).
33.14 Sua resposta deve ser uma fração que 
seja de aproximadamente 0,4979.
33.16 Sim. Seja a qualquer valor no conjunto
{2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A}
e seja b qualquer valor no conjunto 
f ; }; ~; g. Note que P(X = a) = 1
13
 e 
P(Y = b) = 14. Finalmente,
P.X D a ^ Y D b/ D 1
52
D
1
13
1
4
D P.X D a/P.Y D b/:
Portanto, X e Y são variáveis aleatórias 
independentes.
33.17 Calcule P(X = 2), P(Y = 2) e P(X = Y = 2).
34.1 E(X) = 1 × 0,1 + 3 × 0,2 + 5 × 0,3 + 8 × 
0,4 = 5,4.
34.2 E(X) = 133 ,E(Y) = 0 e E(Z) = 
13
3 .
34.4 Seja (S, P) o espaço de amostra para 
um único dado; isto é, S = {1, 2, 3, 4, 
5, 6}. Seja X(s) = s2. Encontre E(X).
34.5 Seja X1 o número no primeiro semi-
condutor e X2 o número no segundo. 
Assim, X = X1 + X2. Note que E(X1) = 
E(X2) = (1 + 2 + ... + 100)/100 = 50,5, 
portanto, E(X) = 101.
34.6 Resposta para (d): Por simetria, sim.
Resposta para (e): Como 100 = E(Z) 
= E(Xh + XT) = E(Xh) + E(XT) e como 
E(Xh) = E(XT), temos claramente E(Xh) 
= E(XT) = 50.
34.7 As regiões dos pontos 30, 40 e 50, po-
dem ser modeladas como círculos de 
raio 1. Então, a região do ponto 20 é um 
círculo de raio de 3 menos os círculos 
dos pontos 30 e 40. A região do ponto 
10 consiste de um semicírculo de raio 
5 e um retângulo de 10 × 5 (menos os 
outros alvos inclusos). A probabilidade 
de aterrissagem na região é a área desta 
região dividida pela área de toda a área 
alvo (que é 25
2
 p + 50).
34.9 Seja X uma variável aleatória zero-um. 
Então, E(X) = 0 × P(X = 0) + 1 × P(X = 
1) = P(X = 1).
34.10 Note que 12 = 1 e 02 = 0.
34.11 Expresse X como a soma de n variáveis 
aleatórias indicadoras zero-um e apli-
que a linearidade da expectativa.
34.12 Para (a), note que há tantos números 
binários, cujos enésimos dígitos biná-
rios é um 1 como existem aqueles cujo 
enésimo dígito binário é 0.
Para (b), use o fato que X = X1 + X2 
+ ... + Xn + Xn.
29Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
Para (c), denote M o número total 
de 1s em todos os números binários 
de 0 a 2n – 1. Explique porque E(X) = 
M/2n e resolva para M.
34.14 As partes (a) e (b) são um pedaço de 
arenque vermelho; você não precisa da 
suposição de independência!
34.16 Aplique a Proposição 34.4.
34.18 Anteriormente, mostramos que E(X) = 
5,4. Podemos calcular
Var.X/ D EŒ.X 5,4/2
D .1 5,4/2 0,1 C .3 5,4/2 0,2
C .5 5,4/2 0,3 C .8 5,4/2 0,4
D . 4,4/2 0,1 C . 2,4/2 0,2
C . 0,4/2 0,3 C .2,6/2 0,4
D 5,84:
Alternativamente, podemos usar a fór-
mula Var(X) = E(X2) – E(X)2. Temos
E.X2/ D 12 0,1 C 32 0,2 C 52 0,3 C 82 0,4
D 35:
e então Var(X) = E(X 2) – E(X )2 = 35 – 
5,42 = 5,84.
34.19 Aqui estão duas soluções completas 
para a parte (a).
Primeiro, podemos trabalhar dire-
tamente a partir da Definição 34.16 
Var(X) = E[(X – m)2] em que m = E(X). 
Começamos calculando m:
m = E(X) = 1(0,1) + 1(0,2) + 2(0,3) + 10(0,4)
 = 4,9).
Em seguida, calculamos a variância:
Var(X ) = E[(X – m)2]
 = (1 – 4,9)2 × 0,1 + (1 – 4,9)2 × 0,2 
 + (2 – 4,9)2 × 0,3 + (10 – 4,9)2 × 0,4 
 = 17,49.
Em segundo lugar, aplicamos a fór-
mula Var(X) = E(X 2) – E(X )2 da Propo-
sição 34.19. Como acima, temos E(X) 
= 4,9 e então E(X)2 = 4,92 = 24,01. 
Próximo,
 E(X2) = 12 × 0,1 + 12 × 0,2 + 22 × 0,3 + 102 × 0,4 
= 41,5. 
Concluímos Var(X ) = E(X 2) – E(X)2 = 
41,5 – 24,01 = 17,49.
34.22 Use a fórmula Var(Z) = E(Z2) — E(Z)2. 
Para a segunda parte, veja o Exercício 
34.18.
34.23 Use o Exercício 34.22.
34.24 Use a desigualdade de Markov (Exer-
cício 34.17).
35.1 A resposta para (b) é q = –34 e r = 2.
35.2 A resposta para (b) é –100 div 3 = –34 
e –100 mod 3 = 2.
35.3 Resposta para (a): N = 17, 18, 19, 20. 
Existem duas soluções para (c).
35.4 A resposta para (a) é “sim” e aqui está 
uma prova.
Suponha, por causa da contradição, 
que a ¤ b. Sem perda de generalida-
de, a < b. Isto implica que a mod b = 
a. Mas como b > a, temos que b mod 
a ≤ a – 1. ⇒ ⇐ Por isso a = b. (Por-
tanto, a = b.
35.7 eia atentamente a primeira frase do 
Definição 35.6.
35.8 Esta é a metade mais difícil da prova.
(⇒) Suponha a  b (n). Isso signi-
fica que n|(a – b), ou, de forma equiva-
lente, a – b = kn para alguns inteiros k. 
Se dividirmos a e b por n, temos
 a = qn + r
 b = qn + r
com 0 ≤ r, r < n. Note que r = a mod 
n e r = b mod n.
Se subtrairmos estas equações, ob-
temos
a – b = (q – q)n + (r – r)
e como a – b = kn, podemos reescrever 
isso como
kn D .q q0/n C .r r 0/
) r r 0 D .k q C q0/n
30 Matemática discreta
então, r – r é um múltiplo de n. Mas 
r e r estão entre 0 e n – 1, portanto, 
sua diferença não é mais que n – 1. As-
sim, devemos ter r – r = 0; isto é, r = 
r. Como r = a mod n e r = b mod n, 
temos
a modn = b mod n.
35.9 Péssima ideia: Chamar os três inteiros 
consecutivos a, b e c.
Boa ideia: Chamar os três inteiros 
consecutivos a, a + 1 e a + 2.
35.12 Aqui está uma boa definição para a 
parte (a): Sejam p e q polinomiais. Di-
zemos que p divide q (e escrevemos 
p|q) desde que haja um polinomial r de 
modo que q = pr.
36.1 A resposta para (d) é gcd(–89, –98) = 1.
36.2 A resposta para (d) é (–89)(11) + (–98)
(–10) = 1.
36.3 Para (d), seu programa deve encontrar 
gcd(–89, –98) = 1 e pegar quatro itera-
ções.
36.5 Tente alguns exemplos.
36.6 Use o Modelo de Prova 14.
36.7 Sim, eles ainda estão corretos. Expli-
que a igualdade gcd(a, b) = gcd(b, c) 
neste caso.
36.8 É o suficiente para provar que, se a ≥ b 
> 0, então b ≥ a mod b.
36.10 (a) Uma resposta completa: O máximo 
divisor comum de três inteiros, a, b e 
c é um inteiro d com as seguintes pro-
priedades: (1) d|a, d|b e d|c, e (2) se e|a, 
e|b e e|c, então e ≤ d.
(b) A frase a, b, c são pares relativamente 
primos significa que gcd(a, b) = gcd(a, 
c) = gcd(b, c) = 1.
36.11 Use o Corolário 36.9.
36.12 Tente encontrar inteiros X e Y tal que 
X(2a + 1) + Y(4a2 + 1) = 1; os números 
inteiros X e Y dependerão de a.
36.14 Use a prova por contradição.
36.15 Use o fato de que podemos encontrar 
inteiros x, y assim ax + by = 1.
Portanto, c = cax + cby.
36.16 Use o Corolário 36.9.
36.17 Use o Corolário 36.9.
36.18 Inverta os papéis de a, b e x, y.
36.19 Explique por que podemos pegar b > 
0 e depois escolher b como o menos 
possível (invocando assim o Princípio 
da Boa Ordenação).
36.20 Numere as crianças de 0 a n – 1 e ima-
gine o professor dando tapinhas na ca-
beça da criança 0primeiro.
Observe que, se k = 4 e n = 10, o 
professor nunca dará tapinhas nas ca-
beças das crianças com números ímpa-
res.
No entanto, se k = 3 e n = 10, então, 
as crianças serão batidas na ordem 0, 3, 
6, 9, 2, 5, 8, 1, 4, e depois 7, portanto, 
todas as crianças levarão tapinhas.
36.21 5 × 13 – 8 × 8 = 1.
37.1 Algumas respostas: (a) 6. (g) 6. (n) 7.
37.2 A ordem das operações para aritmética 
modular é a mesma que a da aritmética 
comum, portanto, fazemos ˝ e ˛ an-
tes ˚ e .
Embora os três primeiros possam 
ser feitos pelo método adivinhar-e-ve-
rificar, o quarto não é receptivo a tal 
ataque de força bruta. Em cada caso, 
você precisa calcular um recíproco de 
n. Você pode fazer isso usando o Al-
goritmo de Euclides expandido.
37.3 Uma vez que o coeficiente de x em 
cada um desses problemas é não inver-
tível, o método normal para resolver 
estas equações não funcionará. Para 
estas, recomendamos que você recor-
ra ao adivinhar-e-verificar. É possível 
que não haja soluções.
37.4 Use adivinhar-e-verificar. A resposta 
para (d) é 2, 7, 8 e 13.
31Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
37.6 Utilize o fato que
 a ˚ b = (a + b) mod n, e
 a  b = (a – b) mod n.
A primeira é da Definição 37.1, e a se-
gunda é da Proposição 37.7.
37.7 Use o Teorema 35.1.
37.9 Você deve assumir que a  b = (a – b) 
mod n, e precisa provar que b ̊ (a  b) 
= a.
37.10 A resposta é que
a ˝ b = 0 ⇐⇒ a = 0 ou b = 0
é um teorema se e somente se n é primo.
A estrutura da prova é um pouco 
complicada.
Primeiro, suponha que n seja primo 
e, em seguida, prove que 
a ˝ b = 0 ⇐⇒ a = 0 ou b = 0
Segundo, suponha que n não seja 
primo e, em seguida, prove que 
a ˝ b = 0 ⇐⇒ a = 0 ou b = 0
seja falso.
37.11 Este é, na verdade, um problema fácil. 
Você precisa provar que o inverso de 
a–1 é a. Leia a Definição 37.9 devagar 
e com cuidado.
37.12 Aqui está uma resposta completa para 
(a). Falso. Contraexemplo: Note que 
em 5 ambos 2 e 3 são reversíveis (2
–1 
= 3 e 3–1 = 2), contudo, 2 ˚ 3 = 0 não é 
reversível.
37.14 Para calcular 332, você pode primeiro 
encontrar 316 e depois calcular 332 = 316 
˝ 316.
38.3 Aqui está uma solução completa para 
(a).
Sabemos primeiro que x  4 (5). 
Isto significa que podemos escrever
x = 4 + 5k
em que k é um número inteiro. Nós 
substituímos este na segunda equação 
x  7 (11) e temos
4 + 5k  7 (11) ⇒ 5k  3 (11).
Para resolver 5k  3 (11), multiplica-
mos ambos os lados por 5–1 em 11.
Utilizando o método GCD estendido, 
temos 5–1 = 9. Então, nós multiplica-
mos ambos os lados por 9:
9 ˝ 5 ˝ k = 9 ˝ 3 = 5
assim k  5 (11). Isto significa que po-
demos escrever k como
k = 5 + 11j
para algum inteiro j. Substituindo isto 
de volta em x = 4 + 5k obtemos
x = 4 + 5k = 4 + 5(5 + 11j) = 29 + 55j
e assim vemos que x  29 (55).
Para (c), resolva os primeiros dois 
equivalentes para obter uma resposta 
intermediária da forma x ? (28) e, em 
seguida, resolva o sistema
x ? (28) e x  8 (25)
pelo método usual.
Para (d), primeiro simplifique as 
duas equações de modo que sejam am-
bas da forma x ? (?).
38.4 O menor número de moedas que torna 
a história correta é 371.
38.8 Aqui está uma resposta completa para (a).
Seja b1 = 8
–1 = 12 em 19. Seja b2 = 
19–1 = 3–1 = 3 em 8. Assim,
 x0 = m1b1a2 + m2b2a1 
 = 8 · 12 · 2 + 19 · 3 · 3. 
 = 363.
Note que 363 mod 8 = 3 e 363 mod 19 
= 2 como requerido.
Como 8 x 19 = 152, podemos re-
duzir x0 módulo 152 para dar 363 mod 
152 = 59. Note que 59 mod 8 = 3 e 59 
mod 19 = 2.
Uma resposta completa para este 
problema é x = 59 + 152k em que 
32 Matemática discreta
k ∈ . No entanto, também podemos 
escrever x = 363 + 152k em que k ∈ . 
Esta é exatamente a mesma resposta; 
ela está apenas expressa de uma forma 
diferente.
39.1 Aqui está uma boa maneira de começar 
a sua prova: “Suponha, por uma questão 
de contradição, que existe um número 
inteiro composto n em que todos os fato-
res (exceto 1) são maiores que pn...”
39.2 Resposta para (b): 4200 = 23 · 3 · 52 · 7.
39.3 A generalização é: Sejam p e q primos 
desiguais. Então, p|x e q|x se e somente 
se (pq)|x.
39.5 Comece fatorando a e b (exclusiva-
mente) em primos.
39.8 Aqui está uma prova completa:
(⇒) Suponha que a e b sejam primos 
entre si. Isso significa que gcd(a, b) = 1. 
Seja p qualquer primo. Se, por causa da 
contradição, p|a e p|b, então, p é um di-
visor comum de a e b e, como p > 1, isso 
contradiz o fato de que 1 é o máximo 
divisor comum de a e b. ⇒⇐ Portanto, 
não existe primo que divide a e b.
(⇐) Suponha que não há primo p 
tal que p|a e p|b. Suponha, por contra-
dição, que a e b não sejam primos entre 
si. Seja d = gcd(a, b) > 1 e seja p um 
divisor primo de d. Como p|d, temos 
p|a e p|b (pela Proposição 5.3). [S]Por-
tanto, a e b são primos entre si. [S]Por-
tanto, a e b são relativamente primos.
39.9 Use o Exercício 39.8.
39.10 Note que para quaisquer dois números 
s e t, temos 
s + t = min[s, t] + max[s, t].
39.13 Chame os quadrados perfeitos conse-
cutivos a2 e (a + 1)2 (em que a seja um 
número inteiro) e suponha que (por 
causa da contradição) que existe um 
primo p que divide ambos.
39.14 Note que 18 = 21 · 32, portanto, todo di-
visor positivo de 18 está na forma 2ª 3b 
em que 0 ≤ a ≤ 1 e 0 ≤ b ≤ 2. Assim, 
existem 2 opções para a e 3 para b dado 
2 × 3 = 6 divisores positivos.
39.15 Os divisores de n são 2k e 2k(2a – 1) 
para todo 0 ≤ k < a.
39.16 É fácil descobrir quantos números en-
tre 1 e n são não primos relativos para n.
A resposta para (f) é (5041) = 
4970. Para ver porquê, note que os 
únicos números entre 1 e 712 que não 
são relativamente primos para 712 são 
os múltiplos de 71: 71, 2 × 71, 3 × 71, 
..., 71 × 71. Portanto, há 5.041 – 71 = 
4.970 inteiros de 1 a 712 que são pri-
mos relativos para 712.
39.18 Use a inclusão-exclusão. Denote Ai o 
conjunto de múltiplos de pi entre 1 e n.
39.20 A frase a seguir é útil: Se n não é um 
quadrado perfeito, então deve ser um 
primo p que aparece um número ímpar 
de vezes na fatoração do primo n.
39.22 Seja x: = log23. Isso significa que 
2x = 3. Suponha x = ab para alguns nú-
meros inteiros a e b, e argumente para 
uma contradição.
39.24 Aqui está uma resposta completa para (c).
Suponha w; z 2 ZŒ
p
. Isso signi-
fica que w D a Cb
p
3 e z D c C d
p
3 
em que a, b, c, d ∈ . Note que
wz D a C b
p
3c C d
p
3
D .ac 3bd/ C .ad C bc/
p
3
e como ac – 3bd e ad + bc são inteiros, 
temos wz 2 ZŒ
p
.
Aqui está uma sugestão para (d). Se 
w D a C b
p
3, então
w 1 D
a
a2 C 3b2
C
b
a2 C 3b2
p
3:
Tente deduzir: Para quais inteiros a e 
b são a
a2C3b2 e 
b
a2C3b2 também inteiros?
33Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
39.25 Para (a), seja w D a C b
p
3 e 
z D c C d
p
3. Para provar que N(wz) 
= N(w)N(z), apenas expanda tudo em 
termos de a, b, c e d e tenha cuidado 
com a álgebra.
Aqui está uma resposta parcial para 
(b).
Não há w 2 ZŒ
p com N(w) = 2. 
Prova: Suponha N.a C b
p
3/ = a2 + 
3b2 = 2. Se b ¤ 0 temos N(w) ≥ 3, as-
sim b = 0. Isso nos deixa com a2 = 2, o 
que é impossível, uma vez que a ∈ .
Há exatamente seis valores possí-
veis para w com N(w) = 4.
39.26 Primeiro prove o seguinte lema: Se 
N(w) é primo, então w é irredutível.
39.27 Se a instrução fosse falsa, poderíamos 
encontrar um contraexemplo w com 
N(w) menor possível.
39.28 Queremos escrever 4 = ab com a, b ¤ 
±2, ±1. Tomando as médias de ambos 
os lados de 4 = ab, obtemos 16 = N(4) 
= N(ab) = N(a)N(b). Não podemos ter 
N(a)N(b) = 2 × 8 porque não existe um 
elemento com a média 2. Portanto, de-
vemos ter N(a) = N(b) = 4.
40.1 Aqui está uma solução completa.
(a) Sim, ? está fechado nos números 
inteiros: Se x e y são números inteiros, 
então x ? y = |x – y| também é um nú-
mero inteiro.
(b) Sim, ? é comutativo: Sejam x e y 
quaisquer dois inteiros. Porque x – y = 
–(y – x) temos |x – y| = |y – x| dos quais 
temos x ? y = y ? x.
(c) Não, ? é não associativa. Considere 
as duas maneiras de agrupar 3 ? 0 ? –2:
(3 ? 0) ? –2 = 3 *–2 = |3 – (–2)| = 5 mas
3 ? (0 ? –2) = 3 * 2 = 1
e, portanto, (3 ? 0) ? –2 ¤ 3 ? (0 ? –2).
(d) Não, ? não tem um elemento de 
identidade. Se ele não tivesse um ele-
mento de identidade e, então, teríamos 
e ? –2 = –2, mas e ? –2 = |e – (–2)| = 
|e + 2| que não pode ser negativo. ⇒⇐ 
Portanto, ? não tem um elemento de 
identidade. E assim, a segunda parte 
desta questão (sobre inversos) é discu-
tível.
(e) Não, (, ?) não é um grupo porque 
a sua operação não é associativa e não 
existe nenhum elemento de identidade.
40.3 Torne 1 o elemento de identidade, 
definindo x ?1 = 1?x = x. Note que 
para x real, não zero, temos x?(–x) = 
–x2/(x – x) e deixamos esse resultado 
ser 1.
Agora, verifique as propriedades 
necessárias:
1. 8x; y 2 R̃; x ? y 2 R̃.
2. 8x; y; z 2 R̃; x ? .y ? z/ D .x ? y/ ? z.
3. 9e 2 R̃; 8x 2 R̃; e ? x D x ? e D x. [Claro, 
e D 1.]
4. 8x 2 R̃; 9y 2 R̃; x ? y D y ? x D e.
5. 8x; y 2 R̃; x ? y D y ? x.
40.6 Responda para ∧: A operação ∧ está fe-
chada, comutativa e associativa e ver-
dadeiro é um elemento de identidade. 
No entanto, falso não tem um inverso. 
Portanto, ({verdadeiro, falso}, ∧) não 
é um grupo.
40.8 Avalie: a * b * c.
40.9 Para mostrar que X e Y são inversos, 
você só precisa mostrar que X * Y = Y * 
X = e. Para este problema, você precisa 
mostrar que o inverso de g–1 é g. Sua 
resposta deve ser muito curta.
40.12 Limpe a poeira de seu texto de álgebra 
linear e releia o material sobre a deter-
minante de uma matriz.
40.13 Lembre-se que 2A representa o con-
junto de todos os subconjuntos de A e 
que D é a operação de diferença simé-
trica.
Para provar que (2A, D) é um grupo, 
prove as quatro propriedades: fecha-
34 Matemática discreta
mento, associatividade, identidade e 
inversos. Nota: Uma delas já foi pro-
vada.
40.14 Isso significa que você deve provar 
que f : G ! G é um-para-um e sobre. 
Aqui está um esqueleto da prova.
Primeiro provamos que f é um-pa-
ra-um. Suponha f(g) = f(k) para algum 
g, k ∈ G. ... Portanto g = k, e assim f é 
um-para-um.
Segundo, provamos que f é sobre. 
Seja b ∈ G. Seja x ∈ G definido por... 
Portanto, f(x) = b, e, assim f é sobre.
Assim f é uma permutação.
40.15 Veja a sugestão para o Exercício 40.14.
40.16 O Exercício 40.14 é útil aqui. Note 
que a linha da tabela * correspondente 
ao elemento a que contém todos os ele-
mentos da forma a * g em que g é um 
membro arbitrário de G.
40.17 Lembre-se: Para provar que X e Y são 
inversos, mostre que X * Y * X = e.
40.19 Verifique se ? satisfaz as quatro pro-
priedades necessárias. Observe que a 
identidade e os inversos para * e ? são 
os mesmos.
40.20 Use a prova por contradição. Seja G 
um grupo com um elemento par e su-
ponha que e seja o único elemento que 
é o seu próprio inverso...
40.21 Este exercício é semelhante ao Exercí-
cio 40.16.
40.22 A resposta para (c) é 15; aqui está por 
quê. A expressão que precisamos ava-
liar é 1, 2, +,3, 4, ×, +. A porção 1,2, + 
avalia para 3 e a porção 3, 4, × avalia 
para 12. A expressão foi reduzido para 
3, 12, + e esta avalia para 15.
40.23 A resposta para (a) é 2, 3, +, 4, 5, +, ×.
40.24 Aqui está um teorema que você deve 
provar:
Seja  uma lista de números e ope-
rações. Afirmamos que  é uma ex-
pressão RPN válida se e somente se as 
duas seguintes condições se mantém: 
(1) o número de operações em  é um 
menos o número de números, e (2) as 
sub-listas de  começando do início de 
 e incluindo todos os membros de  
até qualquer ponto na lista, deve conter 
mais números que operações.
Prove ambas as direções deste teo-
rema se-e-apenas-se por indução.
41.1 Você precisa encontrar uma função 
um-para-um e sobre
f :{0, 1, 2,..., 9} [S] {1, 2, 3, ..., 11}
com a propriedade que
(x + y) mod 10 = z ⇐⇒ [f(x) × f(y)] mod 11 = f(z).
Comece com f(1) = 2. A partir daí você 
pode trabalhar f(1 + 1), etc.
41.2 Seja f [(1, 1)] = 1.
41.3 Um desses grupos é cíclico; o outro 
não é.
41.4 É suficiente apenas considerar (a, ˚) 
× (b, ˚) para todos os inteiros positi-
vos a e b. Os dois problemas anteriores 
mostram que (2, ˚) × (3, ˚) é cícli-
co mas (3, ˚) × (3, ˚) não é.
Comece sua investigação vendo 
quando (1, 1) é um gerador.
41.5 Considere f(e * e).
41.6 Para provar que f(g) e f(g–1) são inver-
sos, ? os junto e espero que consiga a 
identidade.
41.8 Aqui está um esboço da prova. Preen-
cha os espaços em branco.
Seja f : G ! h um isomorfismo.
(⇒) Suponha (G, *) seja abelia-
no. Seja x, y ∈ h arbitrário... Portanto 
x ? y = y ? x, e assim, (h, ?) é abeliano.
(⇐) Suponha que (h, ?) seja Abe-
liano... Portanto, (G, *) é
41.9 Defina f : 
~
 !  por f(x) = 1/x (com 
um tratamento razoável para f(1)). 
Verifique se f é uma função de 
~
 para 
35Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
, que f seja um-para-um e sobre, e 
que f satisfaça a condição de isomor-
fismo ∀x, y ∈ 
~
 f(x ? y) = f(x) + f(y).
41.10 Não. O grupo S4 é não-Abeliano, mas 
(24, ˚) é Abeliano.
41.12 O grupo 4 Klein é definido na Seção 
40. Ele tem quatro elementos: (0, 0), 
(0, 1), (1, 0) e (1, 1).
Lembre-se que o conjunto; 2{1, 2} é o 
conjunto de todos os subconjuntos de 
{1, 2} e que D é a diferença simétrica.
41.13 Defina um mapa F : G ! h por F(a) = 
fa. Prove que F é uma bijeção e que 
F(a * b) = F(a) B F(b).
41.14 Os geradores de (10, ˚) são 1, 3, 7 
e 9. Note que estes são exatamente os 
elementos de 10 que são relativamen-
te primos para 10.
Se você puder provar a sua respos-
ta, o professor lhe dará um tapinha na 
cabeça.
41.15 A resposta não é “nunca”!
O elemento de identidade e é o 
gerador de um grupo cíclico se e so-
mente se e for o único elemento desse 
grupo.
41.17 Aqui está a resposta para *5. Em 
*
5, 
note que 21 = 2, 22 = 4, 23 = 3 e 24 = 1. 
Assim, 2 é um gerador para *5.
42.1 Os subgrupos de (6, ˚) são {0}, {0, 
3}, {0, 2, 4} e {0, 1, 2, 3, 4, 5}.
42.2 Existem três subgrupos.
42.3 Existem cinco subgrupos.
42.4 Não perca uma hipótese principal: 
h ¤ ;.
Dado que
(1) h é fechado sob *.
(2) h ¤ ;
(3) Para todo g ∈ h, g–1 ∈ h.
Você precisa mostrar
(a) h é fechado sob *.
(b) e ∈ h.
(c) Para todo g ∈ h, g–1 ∈ h.
Provando que (a) e (c) é trivial. En-
tão, você precisa mostrar como (b) re-
sulta de (1), (2) e (3).
42.5 Você sabe que (a) h ¤ ; e (b) para 
todo g, h ∈ h, g * h–1 ∈ h.
Você deve provar: (1) h está fecha-
do para *,(2) e ∈ h, e (3) se g ∈ h, 
então g–1 ∈ h.
Prove estes na ordem (2), então (3), 
então (1).
42.6 Seja h um subgrupo de (, +). Pense 
sobre o elemento menos positivo de h 
(se houver).
42.7 Comece sua prova como esta: um sub-
grupo de G. Como G é cíclico, ele tem 
um gerador, g.”
Em seguida, seja k o número inteiro 
positivo menor, de modo que gk ∈ h. 
Você deve se preocupar um pouco se 
existe esse k. [Aqui está um exemplo 
quando isso não acontece: Se G = (, +) 
e h = ({0}, +).] Em seguida, mostre 
que cada elemento de h pode ser ex-
presso como uma potência de gk.
42.9 Para (Z, *) é um subgrupo, você deve 
fazer três coisas: (1) mostrar que 
para x, y ∈ Z nós também temos x * 
y ∈ Z; (2) mostrar que e ∈ Z; e (3) 
mostrar que se z ∈ Z então z–1 ∈ Z 
também.
Sua prova de (1) deve começar: 
“Sejam x, y ∈ Z. Para mostrar que x * y 
∈ Z, considere um elemento arbitrário 
g ∈ G”. E esta parte da sua prova deve 
terminar: “Como (x * y) * g = g * (x * 
y), nós temos que x * y ∈ Z”.
Para (3), aqui está o truque central: 
Dado que z ∈ Z, queremos mostrar que 
para todo g ∈ G que z–1 * g = g * z–1. 
Você não pode provar isto sabendo que 
z comuta com g, mas como z comuta 
com todos os elementos de G, sabemos 
que z comuta com g–1.
36 Matemática discreta
42.10 A classe de equivalência mais fácil de 
encontrar é [1] = [e] = h.
Para encontrar outras classes de 
equivalência, use a ideia da prova 
do Lema 42.7. Escolha um elemento 
g ∈ G e defina uma h ! [g] por f(h) = 
h * g. Para calcular [g], apenas calcule 
f(h) para todo h ∈ h.
Para este problema, [2] = {1, 6, 11, 
16, 21}. Há três outras classes de equi-
valência.
42.10 Veja a sugestão anterior.
42.11 Veja a Proposição 41.3.
42.12 Apenas uma delas é verdadeira.
42.15 Lembre-se que em um grupo geral, 
x  y (mod h) significa x * y–1 ∈ h. 
Neste problema, a operação * é adição 
normal dos números inteiros e o inver-
so de y ∈  é simplesmente –y.
42.16 Não use um grupo abeliano.
42.17 A parte mais difícil deste problema é 
assimilar a definição de g * h. Lem-
bre-se que g * h é um conjunto. Tam-
bém, x ∈ g * h significa que x = g * h 
para algum h ∈ h. (Da mesma forma, x 
∈ h * g significa que existe um h ∈ h 
de modo que x = h * g.)
Para a parte (b), comece provando 
que g * h = h ⇐⇒ g ∈ h. A direção 
(⇒) adiante não é difícil [use a parte 
(a)]. Para a direção (⇐) inversa, você 
precisa mostrar que dois conjuntos 
(g * h e h) são iguais, assim use o Mo-
delo de Prova 5.
Para a parte (d), consulte sua res-
posta para o exercício anterior.
43.1 Eu recomendo usar uma calculadora 
ou um computador. Você deve desco-
brir que a13 = a para todo a ∈ 13.
43.3 Como 101 é primo, você pode avaliar 
3101 mod 101 usando o Pequeno Teore-
ma de Fermat. Agora, basta multiplicar 
esse resultado por mais um fator de 3.
43.5 Aqui está uma solução completa. Que 
x é o restante quando x é dividido 
por p – 1 pode ser expresso como x = 
q(p – 1) + x em que 0 [S] x ≤ p – 1 e 
q é algum número inteiro. Trabalhando 
o módulo p temos
ax D aq.p 1/Cx0 D ap 1
q
ax
0
1q ax
0
ax
0
por que ap–1  1.
43.6 Imite a solução do Exercício 43.5, mas 
use o Teorema de Euler, em vez do Pe-
queno Teorema de Fermat.
43.7 Use o Exercício 43.6 para substituir o 
enorme expoente g por um expoente g 
muito mais razoável.
Computar ab mod c leva cerca de 
log2b etapas básicas.
A resposta é 664.
43.9 Note que ap–1 = 1 em p. Agora encon-
tre um expoente positivo de modo que 
a? · a = 1.
43.11 Se você fizer a divisão de teste, vai de-
morar dezenas de milhares de divisões 
para encontrar os fatores primos do 
número composto. Compute 2n mod n 
para ambos os valores de n e veja o que 
você obtém.
Há uma dificuldade técnica em 
trabalhar com estes grandes inteiros. 
Expressos em binário, eles têm cerca 
de 30 dígitos binários de comprimen-
to; esses números podem se encaixar 
muito bem em seu computador. No en-
tanto, a multiplicação de dois números 
de 30 dígitos binários dá um produto 
de 60 dígitos binários; pode ser difícil 
— usando uma linguagem de progra-
mação de computador comum — para 
você lidar com números deste porte.
43.12 Você precisará escrever um programa 
de computador para resolver este pro-
blema. A menor resposta para este pro-
blema está abaixo de 1.000.
37Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
44.1 Muitas linguagens de computador têm 
funções incorporadas para conversão 
de texto de e para ascii.
44.3 (a) 2/(N – 2).
(b) Seja d = gcd(k, N). Note que os 
únicos divisores de N são 1, p, q e N. 
Por projeto, k < N assim gcd(k, N) ¤ 
N. Portanto, se gcd(k, N) ¤ 1, então os 
únicos valores possíveis que ele pode 
atingir são p e q.
(c) (p + q)/(pq – 2) que é, aproximada-
mente (p + q)/(pq) = 1p C
1
q
.
44.4 Note que na sua resposta para (c), você 
pode assumir que Alice nunca revela-
ria sua função DA que permitiria que 
Eve lesse todas as mensagens privadas 
que ela recebeu.
45.2 Tente usar esta fórmula para um primo 
p ¥ 3 (mod 4), tal como p = 17. O que 
deu errado?
45.3 Para você mesmo verificar, as respos-
tas são 33, 157, 556 e 432.
45.4 Há oito respostas. Note que 34751 = 19 
× 31 × 59 e 19  31  59  3 (mod 4).
45.5 Para (a), os resíduos quadráticos em 
17 são 0, 1, 2, 4, 8, 9, 13, 15 e 16. A 
resposta para (b) é “não”. Escolha um 
resíduo quadrático e veja se há algum 
expoente que funcione.
45.6 Fatorando n em números primos resul-
ta n = 45343 × 7243. Note que ambos 
os números primos são congruentes 
para 3 módulo 4. Seja M = 249500293.
Em 45343 temos
249500293(45343+1)/4 = 12690.
Assim, em 45343, 
p
M = ±12690 = 
12690 ou 32653.
Em 7243 temos
249500293(7243+1)/4 = 2663
assim em 7243 temos 
p
M = ±2663 = 
2663 ou 4580.
Nós resolvemos os quatro proble-
mas seguintes usando o Teorema Chi-
nês do Restante.
x  12690 (mod 45343) 
x  2663 (mod 7243)
x  32653 (mod 45343) 
x  2663 (mod 7243)
x  12690 (mod 45343) 
x  4580 (mod 7243)
x  32653 (mod 45343) 
x  4580 (mod 7243)
As soluções para esses quatro proble-
mas são x  111103040, x  7151504, 
x  321267845 e x  217316309 (to-
dos mod n). O segundo dá 07 15 15 04, 
que significa BOM
45.7 Para (a) envie mais de uma mensagem. 
A preocupação para (b) é que M 2 mod 
n = M 2 (não existe um “invólucro” do 
módulo n, e assim Eve pode encontrar 
M com uma raiz quadrada comum). 
Descubra estratégias para lidar com 
isso.
45.8 gcd(75406 – 68918, 171121) = gcd 
(6488, 171121) = 811.
45.10 A resposta para a segunda pergunta é 
e = 11. Você pode demonstrar isso por 
17 cálculos (um para cada a ∈ 17) mas 
há uma prova algébrica: Mostre que 
elevando a11 ao cubo dá a.
A primeira parte do exercício pode 
ser verificada por meio da elevação ao 
cubo de cada elemento de 17 e anotan-
do que cada elemento de 17 aparece 
como um resultado. No entanto, pela 
segunda parte deste problema sabemos 
que, se a ∈ p, então b = ae é uma raiz 
cúbica de a. E isso implica que a = b3, 
assim, a é um cubo perfeito.
45.11 Você vai querer mostrar que e = 
(2p – 1)/3 funciona. Certifique-se de 
verificar que e é um inteiro.
38 Matemática discreta
45.12 a3 – b3 = (a – b)(a2 + ab + b2).
45.13 (a) Sugestão: fórmula quadrática. (b) 
Resposta: 281
46.1 Resposta: D(N) = N377 mod 589.
46.2 Lembre-se: d = e–1 em *
(n).
46.3 A resposta é M = 100.
46.5 O expoente de criptografia é d = e–1 
(mod (n)). A resposta para (a) é pigs.
47.1 Resposta para (a): ({1, 2, 3, 4, 5, 6}, 
{{1,2}, {1,4}, {2,3}, {2,5}, {3,6}, 
{4,5}, {5,6} .
47.2 Resposta para (a):
a
bc d
e
47.3 Para provar que o mapa não pode ser 
colorido com menos de quatro cores, 
comece (por uma questão de contradi-
ção), assumindo que ele pode ser ade-
quadamente colorido com apenas três. 
Em seguida, considere a região trian-
gular e as regiões limítrofes.
47.5 Se você está tendo problemas com isto, 
recomendo que faça uma pausa e peça 
uma pizza. Antes de comer, dê uma 
boa olhada nas fatias.
47.12 Há uma solução com apenas um aluno.
47.13 Você acha que estes são impossíveis? 
Garantopara você que não são. O que 
está errado com a seguinte “prova” é 
que em nenhum gráfico a relação é-
-adjacente-a é antissimétrica?
Seja G um grafo. Seja uv uma borda 
de G. Então u ~ v e v ~ u, mas u ¤ v. 
Portanto ~ não é antissimétrica. Assim, 
em nenhum gráfico ~ é antissimétrico.
Leia esta “prova” com cuidado. 
Quando você enxergar o erro, saberá 
como responder este problema.
47.15 Use o Teorema 47.5.
47.16 Use a prova por contradição. Se os vér-
tices todos têm diferentes graus, o que 
eles devem ser?
47.18 Use o problema anterior.
47.19 Veja a Seção 17.
47.20 Note que os seguintes são dois gráficos 
diferentes:
G1 = ({1, 2, 3, 4}, {12, 13, 14}) e
G2 = ({1, 2, 3, 4}, {12, 23, 24})
mesmo que seus desenhos pareçam 
muito os mesmos. (Eles têm os mes-
mos conjuntos de vértices, mas dife-
rentes conjuntos de borda).
Eu recomendei que você começasse 
com os casos especiais n = 0, n = 1, n = 
2, n = 3 e n = 4 antes de ir para o caso 
geral. Tente escrever todas as possibi-
lidades. Note, no entanto, que para n = 
4, você deve encontrar 64 gráficos di-
ferentes, assim terá que ser organizado.
47.21 Para (a), use a Proposição 24.25.
Aqui está uma resposta completa 
para (b): Seja v ∈ V(G). Note que u é 
adjacente a v se e somente se f(u) é ad-
jacente a f(v). Como f é uma bijeção, 
isso dá uma correspondência de um-
-para-um entre os vizinhos de v e os 
vizinhos de f(v). Por conseguinte, v e 
f(v) têm o mesmo grau (nos seus res-
pectivos gráficos).
48.1 Os gráficos para (a), (d) e (g), respecti-
vamente, são mostrados aqui:
2
3
4
5 6
1
2
3
4
5 6
1
2
3
4
48.2 Aqui está uma prova completa de que 
é-um-subgráfico-de é antissimétrico.
39Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
Suponha que G seja um subgráfico 
de h e que h é um subgráfico de G. 
O primeiro implica que V(G) ⊆ V(h) 
e E(G) ⊆ E(h) e o segundo implica 
as contenções reversas. Assim V(G) = 
V(h) e E(G) = E(h), e, por conseguin-
te, G = h. Assim é-um-subgráfico-de é 
antissimétrico.
48.4 Por exemplo, o gráfico K2 tem dois 
subgráficos abrangentes e 4 subgráfi-
cos induzidos. Nós enumeramos todos 
eles aqui. Sejam a e b vértices de K2.
Os subgráficos abrangentes de K2 
são os seguintes dois gráficos:
({a, b}, {ab}) e {a, b}, ;).
Os subgráficos induzidos de K2 são 
os seguintes quatro gráficos:
({a, b}, {ab}) {a}, ;)
{b}; ;) ;; ;).
Se você pensou que havia apenas 
três subgráficos induzidos de K2, sua 
resposta seria errada, mas não terrível. 
Os gráficos ({a}; ;) e ({b}; ;) têm exa-
tamente o mesmo desenho (apenas um 
ponto), mas estes não são exatamente 
os mesmos gráficos. (Em um caso, o 
único vértice é a, e no outro caso, o 
único vértice é b). Isso na verdade tor-
na este problema mais fácil de resol-
ver. Há um sentido de que os gráficos 
({a}, ;) e ({b}, ;) são “os mesmos”; 
veja o Exercício 47.21.
Para K3, existem oito subgráficos 
de abrangência e oito subgráficos in-
duzidos.
48.5 a(G) = 3, !(G) = 2.
48.7 Exatamente uma dessas afirmações é 
verdadeira. Prove a afirmação verda-
deira e encontre contraexemplos para 
as outras três.
48.8 Você deve encontrar o seguinte núme-
ro de conjuntos para cada parte deste 
problema: (a) 2, (b) 1, (c) 15 e (d) 15.
48.10 Para (a), note que cada borda de G apa-
rece em exatamente quatro das figuras. 
Assim, contando todas as bordas em 
todas as seis figuras contaremos cada 
uma quatro vezes.
48.11 Para (b), veja a figura a seguir.
Para (c), note que se G é auto-com-
plementar, então sabemos que G e G 
devem ter o mesmo número de arestas.
48.14 (d) Seja G qualquer gráfico em n vérti-
ces. Note que G também é um gráfico 
no vértice n. Como n ! (a, b), sabe-
mos que a(G) ≥ a ou !(h) > b. Pela 
Proposição 48.12,
a(G) = !(G) > a, ou 
G(G) = a(G) > b.
(e) Pela Proposição 48.13, se n ≥ 6, en-
tão n ! (3, 3). Pelo Exercício 48.12, 
5 !/ (3, 3), então pela parte (c) nós 
teríamos 5 ! (3, 3). ⇒⇐ Portanto 6 
é o mínimo inteiro positivo n tal que 
n ! 3,3
(f) Seja G um gráfico com dez vértices. 
Seja v qualquer vértice de G.
Se d(v) ≥ 6, então, entre seis v (ou 
mais) vizinhos podemos encontrar (a) 
um grupo de tamanho 3 ou (b) um con-
junto independente de tamanho 3 (pela 
Proposição 48.13). !(G) ≥ 4 porque v, 
juntamente com os seus três vizinhos 
40 Matemática discreta
adjacentes pares, formam um campo 
de tamanho 4. No segundo caso (b), 
temos claramente a(G) ≥ 3.
De outra forma (d(v)  6), temos 
d(v) ≤ 5. Isto significa que existem 
(pelo menos) quatro vértices w, x, y, z 
para os quais v não é adjacente. Se eles 
formam um grupo, temos !(G) ≥ 4. 
Mas por outro lado, alguns pares deles 
não são adjacentes e (em conjunto com 
v) formam um conjunto independente 
de tamanho 3, assim a(G) ≥ 3.
Em todos os casos, a(G) ≥ 3 ou 
!(G) ≥ 4. Portanto, 10 ! (3, 4).
(g) Sugestão: Considere um vértice ar-
bitrário v. Ou d(v) ≥ m ou v tem, pelo 
menos, n vértices para as quais ele não 
é adjacente.
49.4 A resposta para (a) é n
2
. Para (b), note 
que todos os vértices têm algum grau.
Para (c), para provar que um Gn está 
conectado, escolha quaisquer dois vér-
tices arbitrários e prove que existe um 
caminho que os conecta.
49.5 ∀∃ não é o mesmo que ∃∀.
49.6 Aqui vai uma sugestão:
49.7 A resposta depende se considerarmos 
os caminhos como sequências ou como 
subgráficos. Se considerarmos um ca-
minho como uma sequência, então 
existem n! caminhos Hamiltonianos. 
Mas se considerarmos um caminho 
como um subgrafo, então existem n!/2 
caminhos Hamiltonianos.
49.10 Aqui está um esboço detalhado de uma 
prova. Preencha os espaços em branco.
Suponha que G seja desconectado. 
Devemos mostrar que G está conecta-
do.
Porque G está desconectado, exis-
tem vértices x e y em diferentes com-
ponentes de G.
Agora, considere quaisquer dois 
vértices a e b em G. Considera-
mos casos, dependendo de qual(ais) 
componente(s) de G contém a e b.
– a e b estão ambos no componente 
x de G.
... portanto, existe um caminho (a, 
b) em G.
– Um de a ou b está no componente 
x, e o outro não.
... portanto, existe um caminho (a, 
b) em G.
– Nem a nem b estão no componen-
te x.
... portanto, existe um caminho (a, 
b) em G.
Em todos os casos, existe um cami-
nho (a, b) em G. Como a e b foram 
vértices arbitrariamente escolhidos, G 
está conectado.
49.11 Comece sua prova assim: Suponha, 
por uma questão de contradição que, G 
não esteja conectado. Seja h um com-
ponente de G com o menor número de 
vértices.
49.14 Use a indução para k. A entrada i, j de 
At+1 pode ser expressa como
nX
kD1
ŒAt i;kAk;j :
50.3 Você deve descobrir que há 16 árvores 
distintas. Em geral, o Teorema de Cay-
ley nos diz que o número de árvores 
distintas com conjunto de vértices {1, 
2, 3,..., n} é nn–2.
41Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
50.4 Como este problema lhe pede para 
provar uma afirmação se-e-apenas-se, 
você tem dois trabalhos. Primeiro, su-
ponha que d1, ... , dn são os graus dos 
vértices de alguma árvore T. Você deve 
mostrar que d1 + ... + dn = 2n – 2; isto 
é bastante fácil. . . + dn = 2n – 2; isso é 
muito fácil.
Sua segunda e mais desafiadora ta-
refa é a seguinte: Suponha que lhe são 
dados inteiros positivos d1, ... , dn para 
os quais d1 + ... + dn = 2n – 2. Você 
deve provar que existe uma árvore em 
n vértices cujos graus são precisamente 
d1, ... , dn. Para isso, recomendamos a 
indução. Comece mostrando que pelo 
menos um dos d1 é igual a 1.
50.6 Aqui está um esboço para a sua prova.
Seja G um grafo no qual cada par de 
vértices esteja conectado por um ca-
minho único. Queremos mostrar que 
G é uma árvore. Pela Definição 50.3, 
devemos mostrar que G está conec-
tado e é acíclico.
— Reivindicação: G está conec-
tado. Prove que G está conectado 
por prova direta.
— Reivindicação: G é acíclico. 
Prove que G é acíclico por con-
tradição.
Portanto G é uma árvore.
50.7 Este problema é o melhor realizado 
como uma prova por contra positivo 
(Modelo de Prova 11):
Suponha que v não seja uma folha. 
... Portanto T – v nãoé uma árvore.
50.8 A resposta para (d) é (n – 1)!. Prove 
isso por indução.
50.9 A fórmula é n – c.
50.10 Use o Exercício 50.5.
50.11 Para (a), você também deve usar o 
Teorema 49.12.
50.12 Use o Teorema 50.4.
50.13 Use os Teoremas 50.9 e 50.11 e o pro-
blema anterior.
50.14 Para (c), use o Exercício 50.13.
50.15 Esta é uma declaração se-e-apenas-se, 
por isso não deixe de fazer em ambas as 
direções. Aqui está metade da prova.
(⇒) Seja e = xy uma borda de corte 
de G. Suponha, por contradição, que e 
está contido em um ciclo C. Como e é 
uma borda de corte de G, deve haver 
vértices a e b, que estão conectados em 
G, mas não em G – e. Seja P um cami-
nho (a, b) em G. Necessariamente, P 
contém a aresta e. Sem perda de gene-
ralidade, o vértice x precede o vértice y 
conforme percorremos P de a a b.
Note que em G – e existe um ca-
minho (a, b): Inicie em a, cruze P até 
x, cruze C – e até b, e depois cruze P 
até y. Pelo Lema 49.7, deve haver um 
caminho (a, b) em G – e. [S]Portanto, 
e não está contido em qualquer ciclo 
de G.
50.17 Prove que no passo (4), o gráfico T está 
conectado e acíclico.
50.18 Assim como para o problema anterior, 
prove que o gráfico de saída (o T final) 
está conectado e acíclico. O Exercício 
50.15 auxiliará.
50.19 Resposta para (a): (n – 1)2.
51.3 Kn tem um curso Euleriano?
51.4 Adicione bordas a partir deste novo 
vértice de uma forma que mude todos 
os vértices para grau par. Em seguida, 
verifique se o novo gráfico que você 
criou está conectado.
51.5 Esta questão não é tão simples.
52.5 A condição de que G é colorível 3 sig-
nifica que G pode ser adequadamente 
colorido usando no máximo três cores. 
Nós não somos obrigados a usar todos 
os três.
42 Matemática discreta
52.6 Veja a Seção 48.
52.7 Se G tem n vértices e não está com-
pleto, então n > 1. Além disso, G deve 
conter dois vértices, que não são adja-
centes um ao outro.
52.10 Dada uma coloração adequada de G 
com a cores e um coloração adequada 
de G com b cores, mostre como cons-
truir uma coloração adequada de Kn 
com cores ab.
52.11 Primeiro mostre que G é propriamente 
colorível 4 (isto é fácil). Depois, supo-
nha que G seja colorível 3 e argumente 
para uma contradição. Dê uma cor ao 
vértice 1 e, em seguida, discuta as co-
res dos
52.14 Faça a coloração do vértice de maior 
grau primeiro.
52.15 Prove isso por indução sobre o número 
de vértices em G.
52.16 Para (a), faça a coloração dos vértices 
com quatro cores.
Para (b), por favor note que você 
precisa provar que o gráfico não é colo-
rível 3. Para fazer isso, você deve usar 
a prova por contradição. É também útil 
dar nomes sensatos aos vértices. Cha-
me o vértice no centro da imagem de u. 
Chame os seus cinco vizinhos a1 até a5 
e os cinco vértices correspondente na 
borda externa da figura b1 até b5.
Para (c), embora este gráfico tenha 
muitas arestas, você deve usar a sime-
tria para reduzir esse problema para 
apenas alguns casos. Faça a coloração 
desses gráficos com apenas três cores.
52.18 Para (a), note que podemos colorir as 
bordas verticais com as cores 1 e 2, 
alternadamente em cada coluna e as 
cores 3 e 4 em cada linha, de forma 
alternada. Isto dá uma adequada co-
loração de 4 bordas. Quatro cores são 
necessárias porque há vértices de grau 
4 e as bordas incidentes neles devem 
ter cores diferentes.
53.1 Há 1-mente muitas respostas.
53.3 Você pode usar a fórmula de Euler 
(Teorema 53.3) e/ou imitar sua prova.
53.4 Se G não contém K3 como um subgra-
fo, então cada face deve ter um grau de 
pelo menos 4.
53.5 Conte as bordas (use o Corolário 53.5).
53.8 Embora o gráfico pareça um pouco 
com K5, ele não contém uma subdi-
visão de K5 como um subgráfico. (Se 
ele tivesse, teria um vértice de grau de 
pelo menos 4). Encontre uma subdivi-
são de K3,3 como um subgráfico.
53.10 Para (a), imite a prova do Corolário 
53.5.
Para (c), use a indução.
53.11 Aqui está um argumento completo para 
(a): Primeiro suponha que G seja planar. 
Incorpore G no plano. Agora apague o 
vértice v e observe que todos os vértices 
de G – v são incidentes com a região 
(face) onde v utiliza para residir.
Por outro lado, suponha que G – v 
seja periplanar. Embuta G – v no pla-
no, assim todos os vértices de G – v 
são incidentes com uma face comum. 
Coloque o vértice v nesta face e junte v 
em todos os outros vértices por curvas 
que emanam de v. Uma vez que todos 
os vértices estão na face onde justa-
mente colocamos v, podemos fazer 
isso sem cruzar quaisquer arestas.
Para (b), note que se K4 for peripla-
nar, então use (a) para concluir que K5 
é planar.
Para (d), use a parte (a) e o Corolá-
rio 53.5.
Para (e), use a parte (a) e o Teorema 
das Quatro Cores.
53.12 A parte (a) já foi provada no texto. 
A quantidade vr é a soma dos graus e 
43Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
igual a 2e. A quantidade fs é a soma dos 
graus das faces e também é igual a 2e.
Para as partes (b) e (c), use a fórmu-
la de Euler (Teorema 53.3).
Para a parte (d), note que e deve ser 
um inteiro positivo.
A parte (e) é um pouco mais com-
plicada. O caso (3, 3) foi feito na par-
te (b). Os casos (3, 4) e (4, 3) não são 
muito ruins. Tente o (3, 5) seguinte; 
lembre, a face ilimitada também tem 
grau 5. Você deve ser capaz de cal-
cular quantas faces de grau 5 precisa 
(resposta: 12). Finalmente, o caso (5, 
3) é o mais complicado. Você precisa 
encaixar 20 triângulos (faces de grau 
3), juntamente com 5 triângulos se en-
contrando em cada vértice. Boa sorte!
53.13 Desenhe um gráfico sobre a superfície 
da bola de futebol. Coloque um vértice 
em cada polígono e junte os vértices 
por uma borda se seus polígonos se so-
brepõe. Observe que este é um gráfico 
planar em que cada face é um ciclo 3 e 
todos os vértices têm grau 5 ou 6.
Suponha que existem vértices a de 
grau 5 e vértices b de grau 6. Conte o 
número de arestas de duas maneiras 
para derivar a = 12.
54.1 (a) a e b são incomparáveis. (e) c < i.
54.2 Para (a), a altura é 4 e existem várias 
cadeias contendo quatro elementos, in-
cluindo {b, d, f, i} e {a, c, f, j}.
Para (c), note que {a, c, i} é uma 
cadeia que contém três elementos, mas 
ela pode ser estendida para {a, c, f, i}. 
Portanto, {a, c, i} não é um resposta 
correta para (c).
54.5 Prove que R–1 é reflexivo, antissimétri-
co e transitivo.
54.7 A resposta para a primeira pergunta é n.
54.8 Aqui está a prova completa. Suponha, 
pela contradição, que existem dois ele-
mentos x e y com x < y e x > y. Desven-
dando estas definições, temos (1) x ≤ y, 
(2) y ≤ x e (3) x ¤ y. Contudo, x ≤ y e y 
≤ x implica (por antissimetria) que x = 
y, contradizendo (3). ¤ Portanto, não 
podemos ter ambos x < y e x > y. ⇒⇐ 
Portanto, não podemos ter x < y e x > y.
54.12 Aqui está uma boa definição para 
P – x. Seja P = (X, ≤). Seja P – x o pos-
tulado com o conjunto de X – {x} e a 
relação ≤ em que a ≤ b se e apenas se 
a ≤ b para todos a, b ∈ X – {x}.
55.1 Não há elementos mínimos ou máxi-
mos. Existem três mais completos e 
três menos completos.
55.2 Resposta para (b): 1 é mínimo e menos 
completo. 3, 4, e 5 são mais completos. 
Não há máximo.
55.5 (a) O elemento máximo é {1,2, ..., n} e 
o elemento mínimo é ∅.
(b) Os máximos são todos os subcon-
juntos de {1, 2, ..., n} que têm exata-
mente n – 1 elementos e os mínimos 
são todos os subconjuntos que têm 
exatamente 1 elemento.
55.7 A declaração (d) é falsa.
A declaração (g) é verdadeira. Aqui 
está uma prova completa:
Suponha que x e y sejam elementos 
máximos distintos. Suponha, por causa 
da contradição, que eles não sejam in-
comparáveis. Então, ou x < y ou y < x. 
Se x < y, então x não é mais completo 
e se y < x, então y não é máximo. ⇒⇐ 
Portanto, x e y são incomparáveis.
56.2  Para (a), note que 1 < 2 < 3 e 1 < 3 < 2 
são ordens lineares diferentes para {1, 
2, 3}, mas são isomorfos.
56.3 Aqui está um modelo para a sua prova:
Seja a um elemento mínimo de uma 
ordem total, P. Seja x qualquer outro 
elemento de P... Portanto, a < x, e por-tanto, a é um elemento mínimo.
44 Matemática discreta
56.5 Aqui está metade da prova de (a):
(⇒) Suponha que x seja mínimo 
em P. Para mostrar que f(x) é mínimo 
em Q, precisamos mostrar que, se b é 
qualquer elemento de Q, então f(x) ≤ b 
em Q. Como f é sobre, há um a em P 
com f(a) = b. Como x é mínimo em P, 
a ≥ x. Assim, b = f(a) ≥ f(x) (uma vez 
que f é de preservação de ordem). Por 
conseguinte, f(x) é mínimo em Q.
56.6 Use a parte (a) do problema anterior.
56.7 Para mostrar que  é uma ordem total 
para X × X, você precisa verificar qua-
tro coisas:
– Reflexiva: ∀(x, y) ∈ X × X, temos (x, 
y)  (x, y).
– Antissimétrico: ∀(x1, y1), (x2, y2) ∈ 
X × X, se (x1, y1)  (x2, y2) e (x2, y2)  
(x1, y1) então (x1, y1) = (x2, y2) .
– Transitiva: ∀(x1, y1), (x2, y2), (x3, y3) 
∈ X × X, se (x1, y1)  (x2, y2) e (x2, y2)  
(x3, y3), então (x1, y1)  (x3, y3).
– Total: ∀((x1, y1), (x2, y2) ∈ X × X, te-
mos (x1, y1)  (x2, y2) ou (x2, y2)  (x1, y1).
57.2 As respostas são (a) 4, (b) 14.400 e (c) 
252. Você deve fornecer as explica-
ções.
57.4 Pelo problema anterior, se (x, y) não é 
um par crítico, então ≤ não é transiti-
vo. Isso acontece porque há um a ≤ x e 
um b ≥ y (outro que a = x e b = y) com 
a — b.
Denote u(a) o número de elementos 
estritamente acima de a e denote (a) 
o número de elementos estritamente 
abaixo de a.
Prove que um par incomparável 
(x, y) com (x) + u(y) tão pequeno 
quanto possível é crítico.
57.5 Note que (c, g) não é um par crítico 
porque a < c mas a – g. Também (g, c) 
não é um par crítico porque c < f mas 
g – f.
No entanto, (a, g) é um par crítico, 
porque qualquer x  <  a está também 
abaixo de g (vagamente) e qualquer 
y > g (nomeadamente, y = j) também 
está acima de a.
57.6 Este problema não é tão assustador 
como toda a notação faz parecer. O nú-
cleo da sua prova é este: Quando sabe-
mos que (x1, y1) ≤ (x2, y2) então temos 
que provar que (x1, y1)  (x2, y2).
58.1 A dimensão é 2, mas encontrar um rea-
lizador exige algum trabalho.
58.2 Use o Teorema 57.3.
58.4 Aqui está uma prova completa.
Suponha que P seja um subcon-
junto de Q. Escolha um realizador R 
= {L1, L2, ... , Lt} de Q de dimensão 
mínima. (Assim t = dim Q).
Seja Li a subordem de L; restrita aos 
elementos de P. Note que para todos os 
elementos x e y de P temos x ≤ y (em P) 
sse x ≤ y (em Q) sse x ≤ y (em Li para 
todo i) sse x ≤i y (em Li para todo i). Por-
tanto, R = {L1, L2..., Lt} é um realiza-
dor para P, e assim dim P ≤ t = dim Q.
58.5 Este é um problema difícil. A primei-
ra parte é encontrar um realizador que 
consiste de três extensões lineares. 
Existem onze pares incomparáveis de 
elementos (tal como d, e) e suas três 
extensões lineares devem ter, digamos, 
d < e em um e e < d no outro.
Eu sugiro que você encontre um rea-
lizador para este postulado usando duas 
extensões lineares que não usam o ele-
mento c. Em seguida, adicione mais uma 
extensão linear que maneje c. Esta é a so-
lução que eu encontrei (tente não olhar):
L1 W a <1 b <1 e <1 c <1 d <1 f <1 g
L2 W a <2 d <2 g <2 c <2 b <2 f <2 e
L3 W c <3 a <3 b <3 d <3 e <3 f <3 g
A segunda parte deste problema é 
mostrar que o postulado não tem dimen-
45Apêndice A Muitas Sugestões e Comentários; Algumas Respostas
são dois; ou seja, supor que {L1, L2} seja 
um realizador é impossível. Assim, na-
turalmente, suponha que existe tal reali-
zador e trabalhe firme. Como {b, c, d} 
é uma anticadeia, estes três elementos 
aparecem nas duas extensões lineares 
em ordens opostas. Ou seja, podemos 
ter b < c < d em um e d < c < b em outro. 
Ou podemos ter b < d < c e c < d < b nas 
duas extensões ou podemos ter d < b < c 
e c < b < d. Mas observe que estes dois 
últimos casos são (graças a simetria do 
postulado) equivalentes.
Assim, podemos dividir a prova em 
dois casos. No primeiro caso, temos 
b <1 c <1 d e d <2 c <2 b e, no segundo 
caso, temos b <1 d <1 c e c <2 d <2 b.
Para o primeiro caso, a consideração 
do elemento a (onde a deve aparecer 
nestas duas extensões lineares?) con-
duz a uma contradição simples resul-
tante da incomparabilidade de a e c.
O segundo caso é muito mais tra-
balhoso. Começando com b <1 d <1 c e 
c <2 d <2 b descubra onde cada um dos 
outros quatro elementos do postulado 
deve se situar nas extensões lineares 
e então encontre uma contradição. Na 
minha prova, eu considerei os restan-
tes dos elementos, nesta ordem: f, a, e, 
em seguida, g.
58.7 Este é um problema difícil. Primeiro 
mostre que dim P ≤ 3 construindo um 
realizador usando 3 extensões lineares. 
Ajuda a trabalhar os casos especiais 
n = 3 e n = 4 primeiro e depois olhar 
para um padrão geral.
Para mostrar que dim P > 2 é com-
plicado. Aqui está uma técnica que 
utiliza a contagem: Mostre que exis-
tem n(n – 2) pares incomparáveis da 
forma ai -bj. Em seguida, mostre que 
uma extensão linear pode ter ai > bj por 
no máximo n 12 vezes. Assim, se dim 
P ≤ 2, podemos precisar ter n(n – 2) 
≤ 2 n 12 , e isso leva a uma contradição.
59.1 (b) d. (d) i.(e) a.
59.3 Prove a parte ⇒ observando que para 
qualquer x, y em uma ordem linear, te-
mos um dos x < y, x = y, ou x > y. Para 
a direção ⇐, use a contradição e consi-
dere um par incomparável x, y.
59.4 Note que este resultado exige que to-
dos os números envolvidos sejam in-
teiros positivos. Portanto, x|y ⇒ x ≤ y.
59.5 O postulado (, ≤) é uma estrutura sem 
nenhum elemento máximo ou mínimo. 
O postulado (, |) é uma estrutura sem 
qualquer elemento máximo (mas tem 
um elemento mínimo, 1).
Para tornar a sentença verdadeira, 
insira a palavra finito.
59.7 Mostre que o seguinte não é distributivo.
a
b c d
e
59.8 Resposta para (a): (1,2) ∧ (4, 0) = (1,0) 
e (1,2) ∨ (4, 0) = 4,2).
59.9 Comece com o encontro e a junção de 
dois pontos distintos. Seu encontro é o 
conjunto vazio, e a sua junção é a linha 
única que contém os dois. Agora conti-
nue a considerar o encontro e a junção 
de duas linhas ou de um ponto e uma 
linha.