Apêndices
A Muitas dicas e comentários; algumas respostas
1.1
2.1
2.2
2.3
2.4
2.5
Apendice-3.indd 1
Não existe dica para este problema;
isso anula completamente o propósito!
Confie em você mesmo e pense continuamente a respeito disso.Você obterá
sucesso e, quando tiver a resposta, terá
plenacertezadequeacertou–nãoprecisarádofinaldolivroparalhedizerisso!
Paradeterminarsea|b éverdadeiro,verifiqueseexisteuminteirox demodo
queax =b.
Noexercícioanterior,existeminteiros
a eb comb|averdadeiromas nãoé
uminteiro.
Leia cuidadosamente a Definição 2.6.
Verifiquecadanúmeroparaversesatisfazascondiçõescolocadasnadefinição.
Sua definição para ≤ (menor que ou
iguala)deveseassemelharaisto:
Sejamxeyinteiros.Dizemosquexé
menor que ou igual ay(escritox≤y),
contantoque
....
em que ... representa uma condição
queenvolvex,yeosnúmerosnaturais.
Aodefinir≤,vocêpodeutilizaresse
conceitoparaestabelecer<,>e≥.
Fazem-senecessáriasduascoisas:
(1) Explicar por que os inteiros são
números racionais. Você deve explicar
porque,sex éuminteiro,sepodemachar
inteirosa eb demodoquex = .Osinteirosa eb dependemdex,epodemser
encontrados valores simples para eles.
Cuidadoparanãoescolherb =0.
2.6
2.7
2.8
2.9
(2)Explicarporquealgunsnúmerosracionaisnãosãointeiros.Tudoo
queseexigeéquesemostreumracionalquenãoéinteiro.
O número 169 é quadrado. Como se
podeconvenceralguémdequeissoé
verdade?Vocêvaiprecisarfalardonúmero13.
Eisarespostacompleta.
Um inteiro x é denominado um
quadrado perfeito, contanto que haja
uminteiroy,deformaquex=y2.
Use a notação d(A, B) para denotar a
distânciaentreospontosA eB.Determineumarelaçãoentred(A,B),d(B,C)
ed(A,C)quepermitaverificarseC está
entreA eB.
Para números pequenos, o mais fácil
ésimplesmentelistartodasaspossibilidades. Para números grandes, tente
desenvolver um método mais eficaz.
Experimentefatorarosnúmerosemprimos. Fatoração e números primos são
discutidosnaSeção38.
Arespostade(a)éfacilmenteencontrada começando com 2 e checando
cadanúmero.
Vocêdeveencontrararespostarapidamente.Apartemaisdifícilpara(b)é
escrever uma sub-rotina que verifique
se,dadosdoisinteirosa eb,a|b éverdadeiro.Umamaneiradesefazerissoé
calculara/b earredondarparaointeiro
maispróximo,c.Emseguida,verificar
09/04/2010 19:14:03
2
3.1
3.2
3.3
3.6
3.7
3.8
3.9
Matemática Discreta
seac =b.Tenhaemmentequeessaideia
funciona bem se a e b são positivos e
que isso é suficiente para o problema
presente.Noentanto,sevocêpretende
usaressasub-rotinaemoutrosprojetos,
valeapenaotrabalhodeescreveruma
sub-rotina que funcione para qualquer
pardeinteirosa eb.
Umarespostapara(a)é:sex éuminteiroímparey éuminteiropar,então
xy éuminteiropar.
Notequeaafirmativa(d)éfalsa.
Hámuitasrespostascorretaspossíveis.
Porexemplo,aafirmativa“Se(A)um
animaléumgato,então(B)éummamífero”éverdadeira,mas“Se(B)um
animaléummamífero,então(A)éum
gatoӎfalsa.
Crieagoraseupróprioexemplo.
Aafirmativa“SeA,entãoB”éverdadeira,amenosqueA sejaverdadeirae
B sejafalsa.
Umaafirmativadotipo“ou”éverdadeira,amenosqueambasascondiçõessejamfalsas.Issonosdizquando
“(nãoA)ouB”éverdadeiroequando
éfalso.Comparecom“SeA,entãoB”.
AquetipodetriângulosseaplicaoteoremadePitágoras?
AquetipodetriângulosseaplicaoteoremadePitágoras?
Umadistânciarepresentaumnúmeroe
linhassãoinfinitas.Aoreescrever,utilizeotermosegmento de linha.
Verifique a anatomia dos porquinhos
daÍndia.
©2010Photos.com,divisãodaGettyImages.Direitosreservados
Apendice-3.indd 2
3.10 Lemmaséum,eexisteoutro.
4.1 Eisumarespostacompleta:
Transformadoparaaformase-então,
oproblemapedequeseprove:sex ey
sãointeirosímpares,entãox +y épar.
Prova. Sejam x e y inteiros ímpares.
Por definição de ímpar, existe um inteiro a de modo que x = 2a + 1. Do
mesmo modo, existe um inteiro b de
modoquey =2b +1.Portanto,
4.2
4.3
Como a e b são inteiros, também o é
a + b + 1. Logo, por definição de divisível, x + y é divisível por 2 e, por
definiçãodepar,x +y épar.
A primeira linha da prova é: sejam x
uminteiroímparey uminteiropar.
Aúltimalinhadaprovaé:portanto,
x +y éímpar.
Umalinha,nomeiodaprova,é
xy =(2a)(2b)=4ab =2(2ab)
4.5
4.6
(2a +1)(2b +1)=2(2ab +a +b)+1
Podesermaistrabalhoso,massefizer
o Exercício 4.8 primeiro poderá concluiressecomocorolário.
4.7 Versugestãoanterior.
4.8 Sevocêjáfezosdoisexercíciosanteriores,podeusá-lospararesolvereste.
4.10 (⇒)Suponhaquex sejaímpar....Portanto,x +1épar.
(⇐)Suponhaquex +1sejapar....
Portanto,x éímpar.
Truques algébricos: 2b – 1 =
2(b – 1)+1
4.12 O menor inteiropositivo é 1, ea < b
implicab –a >0.Certifique-sedeque
provouasduaspartesdessaafirmativa
seesomentese.
09/04/2010 19:14:04
Apêndices
4.13 2a +1=(a)+(a +1)
4.14 Construaumaafirmativadaforma:“Se
A ou B, então C” que seja falsa, mas
“SeA,entãoC”sejaverdadeira.
4.15 Tem certeza de que sempre que A é
verdadeiro, B também o é, e de que
semprequeB éverdadeiro,A também
oé?
5.1 Inteirosnegativos.
5.3 Nãoescolhaa umnúmeroprimo.
5.5 Nãohávalormuitopequenoden para
oqualn2+n +41nãosejaprimo.Você
deverá considerar valores de n razoavelmentegrandes.Seescolherovalor
corretoden,nãoprecisaráfazermuitoscálculosparaverquen2+n +41é
composto.
6.1 (b)VERDADEIRO.(c)FALSO.
6.3 Façaumatabela-verdadepara(x Ùy)
Ú(x Ù ¬y)everifiquequeelaempata
comacolunaparaxexatamenteigual
àcolunapara(x Ùy)Ú (x Ù ¬y)
6.4 Façaumatabela-verdadeparaambose
verifiquequesãoamesma.
6.9 Maisde1.000.Tente,primeiro,alguns
exemplosmenores.
6.10 Respostade(b):Façax =FALSOey =
VERDADEIRO.Então,x →y calcula
VERDADEIRO,enquantox ↔y calculaFALSO.
6.11 Paramostrarque(a)éumatautologia,
construímos a seguinte tabela-ver-
dade.
x
y
xÚy
x Ú¬y
(x Ú y)Ú
(x Ú ¬y)
V
V
V
V
V
V
F
V
V
V
F
V
V
F
V
V
F
F
V
V
6.12 Eis uma tabela-verdade para a parte
(a):
Apendice-3.indd 3
3
(x Úy)Ù
x
y
(x Ú
y)
x Ú
¬y
¬x
(x Ú¬y)Ù
¬x
V
V
V
V
F
F
V
F
V
V
F
F
F
V
V
F
V
F
F
F
F
V
V
F
6.13 (⇒) Suponha que A seja logicamente
equivalenteaB....Portanto,A ↔B é
umatautologia.
(⇐)SuponhaqueA ↔B sejauma
tautologia.
... Portanto, A é logicamente equivalenteaB.
6.15 Para(c),mostramosquexÚy=(x Úy)
Ù(¬(x Ùy))pormeiodaseguintetabelaverdade:
(x Ú y)Ù
x
y
xÚy
xÚy
¬(x Ùy)
V
V
F
V
F
F
V
F
V
V
V
V
F
V
V
V
V
V
F
F
F
F
V
F
(¬(x Ùy))
6.17 Se necessário, você pode escrever todas as tabelas possíveis e encontrar
maneiras de expressar cada uma. No
entanto,háumamaneiramecânicade
transformar uma operação booleana
bináriausandoÚ,¬e¬.
7.1 2k.
7.6 Tente,primeiro,umaversãomaissimplesdesseproblema(istoé,mostreque
há36maneirasdecolocartorresaospares,semestarememposiçãodeataque
umaàoutra,emumtabuleirodexadrez
3 ´ 3).
7.9 (a)109.(c)59.(e)99.
7.10 Decomponhaesseproblemaemoitocasos,deacordocomotamanhodonome,
ecompletesuaresposta.
09/04/2010 19:14:04
4
Matemática Discreta
7.13 Arespostaé:20 ´ 19 ´ 18 ´ ... ´ 2 ´ 1
7.14 Arespostanãoé(10 ´ 9 ´ ... ´ 2 ´ 1)2
8.1 Eisumarespostaaumaperguntaque
nãofizemos:Há6! ´ 8! ´ 5!maneiras
decolocaroslivrosnaprateleira,seos
livrosfrancesesdevemficaràesquerda,osrussos,nomeio,eosespanhóis,
àdireita.
8.2 Opontoemdiscussãoéqueoproduto
deumalistaquecontémapenasumnúmerodeveseressenúmerodalista.Na
verdade,nãoserealizaqualquermultiplicação.
para
8.3 Tenteusarafórmula
calcular(3)6.
8.5 2100=(24)25=1625.
8.6 Oerroaproximadoécalculadocomo
8.7
8.8
8.9
(a)945;(b)0.
Arespostanãoé20.
Osdoisúltimosvaloresdalistasãoligeiramentediferentesdosdemais.
8.10 n!=n ´ (n –1)!
9.1 (a){0,3,6,9}
(f) {–10, 10, –20, 20, –50, 50, –100,
100}
9.2 (a)21
9.3 (a)2Î{1,2,3}
(b){2}Í{1,2,3}
(c){2} Î{{1},{2},{3}}
9.7 Sejax ÎC ={x ÎZ:x|12},demodo
quex éumdivisorde12,istoé,12=xa
para algum inteiro a. Multiplique ambososmembrospor3eobtenha36=
3xa =(3a)x.Portanto,x éumdivisorde
36e,assim,x ÎD.Logo,C ÍD.
9.10 Você precisa encontrar um triplo (a,
b,c)queestejaemumdosconjuntos,
masnãoestejanooutro.ComoT Í P,
você deve tentar encontrar um triplo
Apendice-3.indd 4
pitagórico(a,b, c)ÎP,paraoqual(a,
b, c)ÏT.
Umadicaadicional:oquepodemos
dizerarespeitodotermointermediário
dostriplos(p, q, r)ÎT?
10.1 (a)∀x ÎZ,x éprimo.
(g)∀x ÎZ,$y ÎZ,xy =1
10.2 (a)$x ÎZ,x nãoéprimo.“Existeum
inteiroquenãoéprimo”.
(g)$x Î Z,∀y ÎZ,xy ≠1.“Existeum
inteirox demodoque,nãoimportando
ointeiropeloqualomultipliquemos,a
respostanuncaé1”.
10.4 (a)FALSO.(g)VERDADEIRO.
10.5 (a) $x Î Z, x ≮ 0. Existe um inteiro
quenãoénegativo.
(g)$x ÎZ,∀x ÎZ,x +y ≠0.Existe
uminteiroxcomapropriedadedeque,
paraqualquerinteiroy,asomadex e
y nãoézero.
11.1 (b){4,5}.(c){1,2,3}.(e){1,2,3,
6,7}
11.5 Issoéfalso.Acheumcontraexemplo.
11.7 Isso é verdadeiro. Eis um esboço da
prova:
(⇒)SuponhaA ÈB =A ÇB.QueremosmostrarqueA =B.
Sejax ÎA. ...Portanto,x ÎB.
Sejax ÎB....Portanto,x ÎA.
Logo,A =B.
(⇐)SuponhaA =B....Portanto,
A ÈB =A ÇB.
11.12 (⇐)SeA – B =Ø,então,sex ÎA,então x deve estar também em B (caso
contrário, A – B não seria vazio), de
modoqueA ÍB.
(⇒)Poroutrolado,seA ÍB,éclaroquenãoháelementosemA quenão
estejam também em B, de modo que
A – B =Ø.
11.15UsealeideDeMorgandaálgebrade
Boole.
09/04/2010 19:14:04
Apêndices
11.16Amaioriadesseséfalsa.Osdiagramas
deVennpoderãoajudá-loadistinguir
quaissãoverdadeirosequaissãofalsos.Construa,então,pequenoscontraexemplos(paraosfalsos).
11.18 Uma maneira de fazer isso é: comece com um diagrama deVenn padrão
comtrêscírculos(paraosconjuntosA,
B eC)eacrescente,então,umaforma
complicadaparaD.
Note que deve haver, no mínimo,
16regiõesnafigurafinal.
11.19 SejaX =A ÈB.Apliqueaequação(4)
a|X ÈC|.Obtenha,então,|A È B È C|
=|X ÈC|=|X|+|C|–|X ÇC|.
Use o que você sabe para achar |X| e
|X ÇC|esubstituanaequaçãoanterior
parafinalizaraprova.
11.20 Certifique-sedequevocêfezoExercício6.15.
11.21 União(È)écomutativa.
11.22Certifique-sedequevocêfezoExercício11.20euseaspropriedadesdas
ideiascorrespondentesdaálgebrabooleana.
11.24 Useoprincípiomultiplicativo(Teorema7.2).
11.25Eisumesboçoparaumaprovadaparte(a).
Paramostrarquedoisconjuntossão
iguais,usamosoEsquemadeprova5.
Suponha,inicialmente,quex ÎA ´
(BÈC).
...Portanto,xÎ(A ´ B)È(A ´ C).
Suponha,emsegundolugar,quexÎ
(A ´ B)È(A ´ C)...Portanto,xÎ
A ´ (BÈ C).
PortantoA ´ (BÈC)=(A ´ B)È
(A ´ C).

Apendice-3.indd 5
5
Expandimosumpoucoesseesboçocomo
segue.
Suponha,inicialmente,quex ÎA ´
(BÈC).
Issosignificaque x =(a,z),emquea
ÎAeZÎBÈC...
Portanto,xÎ(A´B)È(A´C).
Suponha,emsegundolugar,que
xÎ(A ´ B)È(A ´ C).Dessemodo,
tantoxÎAxBcomoxÎA ´ C...
Portanto,xÎA ´ (B È C).
PortantoA ´ (BÈC)=(A ´ B)È
(A ´ C).

Podemos estender ainda um pouco mais
esseesboço,obtendoaseguinteestrutura,que
vocêdeverácompletar.
Suponha,inicialmente,quex ÎA ´
(BÈC).
Issosignificaquex =(a,z),emque
aÎAezÎBÈC.
Temosdoiscasos:
–Se z Î B,então...
–Sez Î C,então...
...Portanto,xÎ(A ´ B)È(A ´ C).
Suponha,emsegundolugar,quexÎ
(A ´ B)È(A ´ C).
Dessemodo,tantoxÎA ´ Bcomo
xÎA ´ C.
Temosdoiscasos:
–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).

12.1 Utilize a seguinte pergunta: quantas listas de comprimento n podemos
09/04/2010 19:14:04
6
Matemática Discreta
formar utilizando os elementos 0 e 1
(repetição permitida) em que os elementosnãosãotodosnulos?
12.2 Paraaprimeiraparte,aexpressãodeve
sersimplificadaparaxn–1.
Paraasegundaparte,sejax=2.
12.3 Paraaprimeiraparte,utilizeapergunta: “Quantas listas de comprimento n
podemos formar utilizando elementos
em{1,2,3}emqueoselementosnão
sãotodos3?”.
Para a segunda parte, observe que
99+1=100.999+1=1.000 eassim
pordiante.
12.4 Criedoismodelosdepontos.Noprimeiro modelo, os pontos são dispostos em
umagraderetangulardea – blinhase
a + bcolunas.Naturalmente,essemodelopossui(a – b)(a + b)pontos.Encontre
agoraumareorganizaçãodospontosque
tem,evidentemente,a 2–b 2pontos.
12.5Nãoutilizeaálgebra!Dêduasrespostas
diferentes para a pergunta “Quantas
listasdecomprimento2podemosformarapartirdenelementos?”.
13.1 (a)reflexiva,simétrica,antissimétrica,
transitiva
(b)antirreflexiva,antissimétrica
13.2 (d)éverdadeira.Eisumaprova:Suponhaquex R y.Então,|x – y|≤2.Note
que|x – y|=|y – x|,demodoque|y – x|
≤2.Portanto,y R x.
(f) é falsa. Devem-se encontrar três
númerosa,b ec coma R b,b R c mas
a c.
13.3 (a)R–1={(2,1),(3,2),(4,3)}
(c)R–1={(x,y):x,y ÎZ,x –y =–1}
ouR–1={(x,y):x,y ÎZ,y –x =1}
13.4 Lembre-se de que R, S, R–1 e S–1 são
conjuntos.
Para provar que dois conjuntos são
iguais,utilizeoEsquemadeprova5.
Apendice-3.indd 6
13.5 Isso é falso.Ache um contraexemplo
comA ={1,2}.
13.6 As provas e os contraexemplos para
esseproblemasãotodosmuitocurtos.
Porexemplo,eisumaprovadequea
relaçãoR “temomesmotamanhoque”
étransitiva.
SejamA,B eC conjuntosfinitosde
inteirosesuponhaqueA R B eB R C.
Isso significa que |A| = |B| e |B| = |C|.
Portanto,|A|=|C|e,assim,A R C.Logo,
R étransitiva.
13.7 OExercício9.4éútilparaumaparte
desseproblema.
13.9 Para a parte (b): Isso parece impossível?Nãoé.
Talvezvocêtenhapensadocomosegue:
Sejax ÎA.ParaR serreflexiva,devemosterx R x.ParaR serantirreflexiva,
devemos ter x x. Não podemos ter
osdois–oux estáounão estárelacionadocomelepróprio.
Oerrodesseraciocínioestánaprimeirafrase.
13.10Eis um esquema de prova para esse
problema.
(⇒) Suponha que R seja simétrica.
ParamostrarqueR=R –1,devemos
provarqueessesdoisconjuntos,Re
R –1,sãoomesmo.UsamosoEsquemadeprova5.
Suponha(x,y)ÎR....(x,y)ÎR –1.
Suponha(x,y)ÎR –1....(x,y)Î
R.Portanto,R=R –1.
(⇐) Suponha R = R –1. Devemos
provarqueRésimétrica.Suponhax
Ry.
. . . Portanto, y R x, de modo que R
seja simétrica.

09/04/2010 19:14:05
Apêndices
14.1 (a)Sim.(f)Não.(g)Sim.
14.2 Eisaprovaparaaprimeiraafirmativa:
Suponha que x e y sejam ambos
ímpares.Pordefinição,podemosachar
inteirosa eb taisquex =2a +1ey =
2b +1.Masx –y =(2a +1)–(2b +1)
=2a –2b =2(a –b),demodoque2|(x
–y).Assim,x ≡y (mod2).
14.3 Oqueéa –(–a)?
14.4 Certifique-sedequefezoExercício4.6.
14.5 (a)[1]={1,2}
(e)[você]éoconjuntoquecontémtodasaspessoasnascidasnomesmodia
emquevocênasceu.
14.6 VocêpodeutilizaroEsquemadeprova
5(amaneira-padrãoparaprovarqueos
conjuntos são iguais), mas será mais
fácilseaplicaraProposição14.12.
14.10Eisumanotaçãoútilparaesseproblema.Denotepor[a]R aclassedeequivalênciaemrelaçãoaR, edenotepor[a]S
aclassedeequivalênciaemrelaçãoaS.
Istoé,
[a]R ={x ÎA :x R a}
[a]S ={x ÎA :x S a}
14.13É trabalhoso escrever uma relação de
equivalênciacomoumconjuntocompleto de pares ordenados. Por exemplo,considereaseguinterelação:
R ={(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),
(4,3),(4,4)}
Émaissimplesescreverapenasasclasses de equivalência: {1, 2} e {3, 4}.
Umaabreviaturaconvenienteparaisso
é12/34.
15.1 Useanotação1/23paraindicarapartição{(1),(2,3)}etc.
Aspartiçõesde{1,2,3}são1/2/3,
1/23,2/13,3/12e123.
Há15partiçõesde{1,2,3,4}.
Apendice-3.indd 7
7
.
15.2 Respostade(d):
15.5 Eisumesboçoparaessaprova.
Parte (1): Seja [a] uma classe de
equivalência de . Prove que existe
umaparteP ÎP talque[a]=P.(Você
vaiprecisarprovarqueosdoisconjuntosaquisãoiguais.)
Parte (2): Seja P uma parte de P,
istoé,P ÎP.Provequeexisteumelementoa ÎA demodoque[a]=P.
Você mostrou que toda classe de
equivalênciade éumapartedeP e,
reciprocamente,quetodapartedeP é
umaclassedeequivalênciade .
15.7 Imagineque12pessoasestejamdispostasaoredordafacedeumrelógio.De
quantasmaneiraspodemseraícolocadas? (Resposta: 12!) Naturalmente, se
todossemovemumaposiçãonosentidohorário,oarranjoéequivalente.
Descrevaumarelaçãodeequivalência
no conjunto dos arranjos e tente imaginar o tamanho das classes de equivalência.
15.8 Cuidado. É fácil errar por um fator 2
nesseproblema.
15.9 Éfácilerrarporumfator2nesseproblema,também.
15.10 29260083694424883200000,masestaé
umamaneirahorríveldedararesposta.
15.11Imagine,primeiro,asvintepessoasem
fila.Dequantasmaneirasissopodeser
feito?(Resposta:20!)Asdezprimeiras
dafilaformamumtimeeasdezúltimas formam o outro. Considere duas
filas equivalentes se elas resultam na
formaçãodosmesmostimes.Calculeo
tamanhodasclassesdeequivalênciae
acheonúmerodelas.Noteque,sepermutamos todos os jogadores em cada
umdosdoistimes,nãoalteramoscoisa
alguma,narealidade.
09/04/2010 19:14:05
8
Matemática Discreta
Verifiquesuaresposta,considerandoonúmerodemaneirasdedividirseis
pessoas em dois times de três.A resposta deve ser 10: 123/456, 124/356,
125/346, 126/345, 134/256, 135/246,
136/245,145/236,146/235e156/234.
15.16Sim.AcheoconjuntoA.
16.1 A segunda resposta é o dobro da primeira.
16.4 Arespostade(b)é .
16.5 Ográficoseafiguraassim:
{1,2,3} ↔ {4,5,6,7}
...
{5,6,7} ↔ {1,2,3,4}
16.6 Para(b),considereoscasoscomzero,
umedoisduplosseparadamente.
16.7 Cuidado: Há uma armadilha esperandoporvocê.Nãopisenela!
emtermos
16.9Façaaexpansãode e
defatoriaiseuse,então,aálgebrapara
mostrarquesãoiguais.
16.10Aquestãoé:quantossubconjuntospossuiumconjuntoden elementos?
16.11 Façaaexpansãode(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 subconjuntos com um número ímpar de
elementos.
16.15Considereumconjuntode2n +2pessoascomdoiselementosestranhos.
nn
16.16A fórmula de Stirling é n! ≈
e–n.
Paraasegundaparte,noteque4n =22n.
16.17Ponhatudosobreumdenominadorcomumenãopercaacoragem.
16.18Aquestãoé:quantossubconjuntosde
trêselementostemoconjunto{1,2,3,
...n}?
Apendice-3.indd 8
Econsidere:quantosdessessubconjuntos de três elementos têm 3 como
maiorelemento?
Maiorelemento4?...Maiorelementon?
16.21Penseemumasaladeaulacomn meninasen meninos.
16.23A resposta é . Podemos considerar
esseprocessoderotulaçãocomouma
seleçãodek elementosdeA,querecebemorótulo“bom”(eosdemaissão
rotulados como “maus”). Assim, há
uma correspondência um a um entre
rotulaçãoeseleçãodesubconjuntosde
k elementosdeA.
16.24(a)Seestiveremdúvida,escrevatodas
aspossibilidades.Nãosãomuitas.
(b)Noteque1+2+5≠10,demodo
que não há rótulos suficientes.A resposta desse problema é um número e
nãoapalavraimpossível.
(d)ComonãohárótulosdoTipo3dis-
poníveis, este se reduz ao problema
anterior; a resposta é um coeficiente
binomial.
(e)Mudaronomedosrótulosnãoaltera
onúmerodemaneirasdedistribuí-los.
16.25Para(a),pensenoprocessoderotulação
emdoisestágios.Primeiro,associamos
osrótulosdoTipo1(dequantasmaneiras?)e,então,associamososrótulosdo
Tipo2(dequantasmaneiras?).
Para (b), você usar (a) e expandir
oscoeficientesbinomiaisemfatoriais,
mas há uma prova combinatória. Coloque os n elementos em uma lista
semrepetição(dequantasmaneiras?).
Dê, então, aos a primeiros elementos
dalistaorótuloTipo1,aosb elementos seguintes o rótuloTipo 2, e aos c
elementos restantes, o rótulo Tipo 3.
Defina:duaslistassãoequivalentesse
09/04/2010 19:14:05
Apêndices
resultamnamesmadistribuiçãoderótulos.Conteasclassesdeequivalência.
16.26AprovaéanálogaàdoTeorema16.8.
16.27Resposta .
16.28(a)13 ´ 48.(d)13 ´ ´ 12 ´ .
16.30Escrevaasprimeirasseisousetelinhas
dotriângulodePascal.Emcordiferente,assinale,juntamenteacadaentrada,
quantas adições foram necessárias
paracalcularaquelevalor.Notequeos
1 nos extremos de cada linha exigem
zeroadições.
Agora,paracalcularumvalorinte(queexige
rior,como ,calcule
(que
certonúmerodeadições)e
exige certo número de adições). Por
fim, para calcular , faz-se mais um
cálculo.
Consegueverumpadrão?Issolhe
.
daráumamaneiradecalcular
:Listamostodososseismul17.1 Para
ticonjuntosdedoiselementosquepodemos formar com os elementos em
{1,2,3}.Sãoeles:〈1,1〉,〈1,2〉,〈1,3〉,
〈2,2〉,〈2,3〉,〈3,3〉.
=
=
OTeorema17.8dá
=6.
Dê uma resposta semelhante para
.
:**||,*|*|,*||*,|**|,|*|*,e
17.2 Para
||**.
17.3 Vocêpodeverificarsuarespostausandoográfico.Oponto,nesseproblema,
éverificaraprimeiralinhaeaprimeira
colunadográfico.
17.4 〈1,4,4,4〉.
17.5 Convertaparaumcoeficientebinomial.
17.6 Pode-se reordenar os fatoriais, se necessário.Eisumaideiamelhor:*↔|.
17.8 Isso pede uma prova combinatória.A
questãoé:quantosmulticonjuntosdek
elementospodemosformarusandoos
Apendice-3.indd 9
9
inteirosde1an?Aprimeirarespostaé
.Asegundadependedamultiplicidadedoelementon nomulticonjunto.
Esseproblemapodetambémserresolvido pela conversão para coeficientes
binomiais.
17.9 Esteproblemaexigeumaprovacombinatória.Você deve encontrar uma pergunta que seja respondida tanto pelo
ladodireitocomopeloladoesquerdoda
equação.Aperguntadeveser:“Quantos
multiconjuntos de k elementos podem
ser formados utilizando-se inteiros escolhidosde{1,2,...,n}?”.
Oladoesquerdodaequaçãoéclaramenteumarespostadessetipo.Tente
descobrircomooladodireitotambém
é uma resposta. E, para ajudá-lo com
isso,respondaàperguntaaseguir:
Quantos multiconjuntos são de tamanho10,comelementosquesãoescolhidosapartirde{1,2,...,99}cujo
.
maiorelementoé23?Responda
18.1 Designe por A1, A2, A3 e A4 os quatro
grupos de pessoas. O problema lhe
dáostamanhosdessesconjuntosede
suas várias intersecções.Você precisa
encontrar|A1ÈA2ÈA3ÈA4|.
18.2 Isso é verdadeiro, portanto, não tente
acharcontraexemplo.Comecepor
ecancele|A ÈB ÈC|=|A|+|B|+|C|.
18.3 Primeiro, conte as palavras “más” e
subtraia265.
Seja B1 o conjunto das palavras
cujasprimeirasduasletrassãoiguais.
Seja B2 o conjunto das palavras cujas
segundasduasletrassãoiguaiseassim
pordiante.
09/04/2010 19:14:06
10
Matemática Discreta
Calculeostamanhosdasváriasintersecçõeseapliqueinclusão-exclusão.
18.4 Para(a),escreva9n =[10+(–1)]n.
Para (b), a prova combinatória,
você precisa da pergunta certa. Eis
umaboamaneiradecomeçarsuapergunta:quantaslistasdecomprimenton
podemserformadasusandoosdígitos
de0a9nasquais...?
19.1 (a) Se x2 não é ímpar, então x não é
ímpar.
(d)Seumparalelogramonãoéumlosango, então suas diagonais não são
perpendiculares.
19.2 Lembre:¬ ¬B =B.
19.3 (b)Sejama eb inteirosnegativos.Suponha,porcontradição,quea +b seja
nãonegativo.
(d) Sejam p e q primos para os quais
p + q é também primo. Suponha, por
contradição, que nem p nem q sejam
iguaisa2.
19.5 Suaprovadevecomeçarassim:
Sejamx ex +1inteirosconsecutivos.Suponha,porcontradição,quex e
x +1sejamambospares...
19.8 Suponha que (A – B) Ç (B – A) ≠ Ø.
Issosignificaqueexisteumelementox
tantoemA –B quantoemB – A.Argumente,apartirdaí,parachegarauma
contradição.
19.9 Esteéumteoremadotiposeesomente
se;certifique-sedeprovarasduaspartes. Ambas podem ser provadas pela
contrapositiva.
19.10Aqui, é possível uma prova direta. O
ponto desse problema é introduzir o
termorecíproca.
19.11 Respostapara(a):dizemosquex éomenor elementodeA desdeque(1)x ÎA
e(2)sey ÎA,entãox ≤y.
Apendice-3.indd 10
Primeira sentença para (b): Suponha, por contradição, que E contenha
ummenorelementox.
Comentáriopara(c):Issoébastante
óbvio, mas escreva uma prova cuidadosaporcontradiçãousandooEsquemadeprova14.Eisumbomcomeço
parasuaprova:“sejamA eB subconjuntosdosinteiroscomummenorelemento.Suponha,porcontradição,que
A contenha dois menores elementos
distintosa eb...”
20.1 Nãoexistetalcoisa.
20.5 Érecomendávelousodeumcomputador para calcular vários primeiros
númerosdeFibonaccieosvaloresde
1,6n, embora uma calculadoramanual
sejasuficiente.
Você deve encontrar que a desigualdadevaleparatodon ≥29.
20.6 Eisumatabelaparacomeç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
Compareosnúmerosdaterceiracolunacomosdasegunda.
20.8 Expresso como um teorema, é necessário mostrar: para todo n Î N, a nésimalinhadotriângulodePascalé
09/04/2010 19:14:06
Apêndices
21.3 Eisumarespostacompletapara(a):
Prova. (porinduçãosobren):
Caso básico: n =1.Ambososmembrosdaequaçãovalem1,demodoque
ocasobásicoseverifica.
Hipótese de indução: Suponha o
resultadoverdadeiroparan =k.
Assim,temos
11
Para provar: an =2n+1–1.
Caso básico: Quando n = 0, precisamosapenasnotarquea0=1=20+1–1
=2–1,comoqueríamos.
Hipótese de indução:Suponhaak =2k+1
–1.
Precisamos mostrar que ak+1 = 2(k+1)+1
–1.
Noteque
Desejamosmostrarque
Adicione3(k +1)–2=3k +1aambos
osmembrosde(*)eobtenha
Para (c), observe que isso é uma
generalização do fato de que 999 =
1000–1.
21.5 Esse fato é bastante óbvio. O ponto
aquiéapráticadaescritadeprovaspor
indução. Seja n o número de pessoas
nafila.Nocasobásico,n =2.
21.6 Aprovasefazporinduçãosobreonúmerodediscos.
21.8 Estaéumarespostacompletapara(a):
Os próximos quatro termos da sequênciasãoa4=31,a5=63,a6=127.
Apendice-3.indd 11
comoqueríamos.
21.9 Seja an o número de soluções possíveis. Encontre uma relação de recorrênciaparaan.
21.10Utilize uma indução forte. Se n é um
númerodeFibonacci,nãohánadaase
provar. Se n não é um número de Fibonacci, seja Fk o maior número de
Fibonacci,menorquen.Vocêdevedemonstrarquen – Fk < Fk.
21.11 Usamos indução sobre n = lastfirst.
Ocasobásicoocorrequandon =0.
Nessecaso,first éigualalast,de
modoqueoprogramaretornaarray
[first],queéoúnicovaloremconsideração.
Hipótese de indução: Suponha o resultadoverdadeiroparatodososvaloresdelast-first quesãomenores
quen.
Suponhaqueoprogramatenhadesignado n = last-first. Note que
midestáentrefirstelast,equetemosmid < last,demodoque,por
indução,alinha
a = findMax (array, first,
mid);
09/04/2010 19:14:06
12
Matemática Discreta
dáàvariávelaomaiorvalordatabela, do índice first ao índice last.
Além disso, mid+1 é maior que
first, de modo que, por indução, a
linha
b = findMax (array, mid+1,
last);
dáabomaiorvalornatabela,doíndice
mid+1aoíndicelast.
Por fim, as últimas duas linhas do
programa retornam o maior entre a
e b, o que deve ser o maior valor na
tabela entre o índice first ao índice
last.
21.13A questão deste problema é que você
nãoserácapazdefazeresteproblema!
Arespostacompletaecorretaparaele
é:desisto!
Naprovadestelivro,usamosaseguintehipótesedeindução:
Hipótese de indução 1:Todopolígonotrianguladocom,nomáximo,klados, tem, no mínimo, dois triângulos
exteriores.
Suatarefaétentartrabalharapartir
daseguintehipótesedeindução:
Hipótese de indução 2:Todopolígono
trianguladocom,nomáximo,klados,
tem,nomínimo,umtriânguloexterior.
Ahipótese1émaisfácildeserusada
porqueelaproporcionamaisbase.Isso
éconhecidocomocargadeindução.
21.14A prova é semelhante à do Teorema
21.2.
21.15Eisasprimeiraslinhasdeumaprova,
paravocêcomeçar.
O caso básico aqui é zero. Nesse
caso, podemos escrever 0 como uma
somavazia.
Sejan uminteiropositivoesuponha
que o resultado tenha sido m
ostrado
Apendice-3.indd 12
paratodososnúmerosnaturaismenoresquen.Sejak omaiornúmeronaturaldemodoque2k ≤n.(Háapenasum
númerofinitodenúmerosnaturais≤n
e20≤n;logo,k existe.)
21.16Eisumaafirmaçãoquevocêdeveprovar:seA éumsubconjuntonãovazio
de N, então A contém um menor elemento.
Paraprovarissoporindução,considereaseguintealternativa.SejaA ÍN.
Sen éumnúmeronaturalemA,então
A contémummenorelemento.
Faça,agora,induçãosobren.Recomendamosinduçãoforte.
22.1 Eisumasoluçãocompletapara(a):
Paraaspartes,eisa5:(b)20,(c)11,
(d)0,(e)15e(f)16.
22.2
22.3Eisumasoluçãocompletapara(b).Escrevemos as sentenças an, ∆an ∆2an, e
assimpordiante,atéchegarmosauma
sequêncianãonula:
09/04/2010 19:14:06
Apêndices
Utilizamos,então,osprimeirostermos
de cada linha e aplicamos o Teorema
22.17paraobter
22.4 Aplica-se o operador de diferença
às sequências, não a membros individuais. A notação (∆a)n significa o
n-ésimo termo da sequência ∆a; este
éosignificadopretendido.Anotação
∆(an)nãoédefinida,desdequeanseja
umnúmeroequenãotenhamosdesignadoumsignificadopara∆aplicadoa
umúniconúmero.
22.5 Seja k um inteiro positivo e seja an =
. Sabemos que ∆an = ∆ =
.
j
Aorepetirisso,constatamosque∆ an=
.Portanto,temos
mas Ak–1 a0
1
22.6 Podemosexpressarannaforma
,emquer1,r2sãoasraízesdeuma
equação quadrática. Encontre r1, r2
primeiro.Então,crieduasequaçõese
duasincógnitasparaencontrarc1,c2.
22.8 Sejaan=1t+2t+...+nt.Observeque
∆an=(n+1)t.Aplique∆maist+1vezes.Oqueseobtém?UtilizeoTeorema
22.17paraconcluirquean possaserescritocomoumaexpressãopolinomial.
Apendice-3.indd 13
13
22.10Por exemplo, quando s = 3, precisamos solucionar an = 3∆an. Lembre-se
deque∆an=an+1–an,portanto,oque
realmenteprecisamossolucionaréan =
3(an +1 – an), o que pode ser reorganizadoparaan +1= an.Essarecorrência
nãoseencontraexatamentenaformapadrão,masequivaleaan= an –1.
22.11 ∆2an=an +2=2an +1+an
22.13(a)Arespostaéan=3n–2n+1
(d)A forma da resposta é an = c15n +
c2+c3n.
(e)A forma da resposta é an = c13n +
c2n3n+c3.
(f) an é fornecido por um polinômio
quadrático.
22.14Eisumasoluçãocompletapara(a).A
partir da relação de recorrência an =
4an–1–an–2–6an,formamosaequação
cúbicaassociadax3–4x2+x+6=0.
Issoéfatoradopara(x–2)(x–3)(x+1)
= 0; desse modo, as raízes são 2, 3 e
–1.Portanto,esperamosqueansejada
formac12n+c23n+c3(–1)n.
Agora, utilizamos os valores para
a0,a1ea2parasolucionarc1,c2,c3:
Issoresultaemc1=1,c2=2ec3=5.
Portanto,
an=2n+2 ´ 3n+5(–1)n
22.15 Implemente esse programa em sua
linguagemfavorita.Noiníciodoprocedimento, encontre um comando de
depuraçãoquereproduzaoargumento.
Algodotipo:
print ‘Calling get_term
with argument ‘ n
09/04/2010 19:14:07
14
Matemática Discreta
Agorachameget_term(10)eveja
oqueacontece.
Observe que, para calcular a0, a1,
apenasumachamadaparaget_term
égerada.Paracalculara2,trêschamadas são geradas (a chamada original
get_term(2),alémdeduaschamadasintegradas.
Paracalculara3,get_terméchamado cinco vezes: uma vez, para a
chamada original get_term(3) e,
em seguida, chama get_term(2)
(trêschamadasparafazerisso)eget_
term(1) (uma chamada para isso).
Osprimeirospoucosvaloresdebnsão
1,1,3,5,9,15,25.
22.16Para(a),utilizearecorrênciaparagerar os valores a1, a2, a3, a4, mas não
façaasmultiplicaçõesatuais.
.
Arespostapara(b)é
Para (c), escreva os primeiros vários valores. Você notará que an não
seencaixaexatamentenomodeloque
deve observar. Não há problemas em
relatarsuarespostanaforma
A parte (d) também apresenta a dificuldade de que a0 não se encaixa no
modelodostermossubsequentes.Tente
encontrar uma recorrência de segunda
ordemdaformaan=s1an–1+s2an–2que
funcione,umavezquen≥3,eresolva-a.
A parte (e) corresponde a um problemanãosolucionado.Osvaloresan
são denominados caóticos, e não se
pode esperar que exista uma fórmula
razoável.
23.1 Umarespostacompletapara(a):f éuma
função,domf ={1,3}eimf ={2,4}.
f éumaumef –1={(2,1),(4,3)}.
Apendice-3.indd 14
23.2 Há23detaisfunções,enenhumadelas
éumaum.
Uma dessas funções é {(1, 4),
(2,4),(3,4)};elanãoénemumaum
nemsobre.
23.3 Há32detaisfunções,enenhumadelas
ésobreB.
Uma dessas funções é {(1, 3),
(2,3)};elanãoénemumaumnem
sobreB.
23.4 Eisumarespostacompleta.
Função
Um a 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
23.7Em(a),nãoháconjunto,B explícitoao
qualseapliqueadefinição.Emparticular,todafunçãof ésobreseencaramosB comooconjuntoimagemdef.
Em(b),anotaçãof :A →B estabeleceumcontextoparaafrase“f ésobre”.Nessecontexto,aquestãoé:Imf
éigualaB?
23.9Eisumarespostacompletapara(a).
Primeiramente,f éumaum.Prova:
Precisamosmostrarque,sef (a)=f (b),
então a = b. Suponha que tenhamos
inteirosa,b comf (a)= f (b).Pordefiniçãodef,temosque2a =2b.Dividindoambososmembrospor2,dáa =b.
Portanto,f éumaum.
Em segundo lugar, f não é sobre.
Prova:Afirmamosque1ÎZ,masnão
háx ÎZcomf (x)=1.Suponhamos,
porcontradição,queexistauminteiro
x demodoquef (x)=1.Então,2x =1,
e,daí,x = .Noentanto, nãoéinteiro,
demodoquenãoháinteirox comf (x)
=1.Logo,f nãoésobre.
09/04/2010 19:14:07
Apêndices
23.11Esseproblemaexigequeseescrevam
trêsprovas:
1.Se(a)e(b),então(c).
2.Se(a)e(c),então(b).
3.Se(b)e(c),então(a).
Paraisso,aProposição23.24(PrincípiodaCasadoPombo)ébastanteútil.
23.14QuantossubconjuntosdeA têmexatamentek elementos?
23.15VerExercícios16.24e16.25.
24.1 Quantospadrõesdiferentesdos<edos
>sãopossíveisemumasequênciade
cincointeirosdistintos?
24.3 Crieseiscategoriasdeinteirosbaseadas
emseusdígitosdasunidades.Comohá
seteinteirosnoconjunto,doisdessesnúmerosdevemestarnamesmacategoria.
24.4 ApliqueoPrincípiodaCasadoPombo,
fazendocasasdepombonoquadrado.
24.5 Considereaparidadedascoordenadas.
24.6 Onúmero9deveapareceremsuaproposição.
24.7 Eisumasequênciadetamanho9sem
qualquer subsequência monótona de
tamanho4.
321654987
TentegeneralizarissoeuseoPrincípiodaCasadoPomboemsuaprova
dequeasequêncianãocontémsubsequênciamonótonadetamanhon +1.
24.8 Se a sequência tem tamanho n, então
elatem2n subsequências.Mesmopara
valores moderados de n, é altamente
ineficientetentarexaminartodaselas.
Emvezdisso,useoesquemaderotulaçãodaprovadoTeorema24.3.
25.1 (a)g df ={(1,1),(2,1),(3,1)}e
f dg ={(2,2),(3,2),(4,2)};g df ≠
f dg.
(c)g df ={(1,1),(2,5),(3,3)}masf dg
énãodefinido.
Apendice-3.indd 15
15
(h)(g df)(x)=x +1e(f dg)(x)=
x –1;g df ≠ f dg
25.8 Quaissãoodomínioeaimagemdef d
f –1?
25.11 Arespostaparaambososcasosésim,
se o conjunto, A, for finito. Contudo,
....
25.12A parte (a) já foi trabalhada no Exercício25.9.Aparte(b)éfalsa;acheum
contraexemplo.Aparte(c)éverdadeira;useoExercício25.7.
26.2 Arespostapara(a)é(1,2,4)(3,6,5).
26.3 Paran =3arespostaédois:(1,2,3)e
(1,3,2).Paran =4,arespostaéseis.
26.4 Esteéumproblemadedesordenação.
26.5 Arespostapara(a)é(1,4,7,6,9,3,2,
5,8),earespostapara(b)édiferente.
A resposta para (d) é (1)(2, 5, 4, 3)(6,
9,8,7),emboraissopossaserescrito,
também,como(1)(5,4,3,2)(9,8,7,6).
26.6 Issoéfalso.
26.8 Issofoitrabalhadoemumproblemada
Seção25.
26.11 Note que, para qualquer transposição
t,temostdt=i.Logo,t–1=t.
Para provar que duas permutações
são inversas uma da outra, faça sua
composiçãoemostrequeseobtémτ.
26.14Temosquepds=s.Compondoàdireitacoms–1,obtemos
π
π
π
π
π
26.16 Arespostade(a)é:p=(1,2)(2,3)(3,4)
(4,5);possuiquatroinversõeseépar.
26.17Umagrandesugestão:traceumafigura
desetas,daesquerdaparaadireita,da
permutaçãoedesuainversaeconteos
cruzamentos.
09/04/2010 19:14:07
16
Matemática Discreta
26.20Imaginequeoespaçoembranco“contenha”onúmero16.Então,váriosmo-
vimentos do quebra-cabeça resultam
em uma permutação dos números 1 a
16.Emparticular,umúnicomovimento
doJogodosQuinzeéumatransposição.
27.1 Noteque
R90 = (1,2,3,4),
FH = (1,2)(3,4), e
F\ = (1)(2,4)(3).
27.2
27.4
27.5
27.7
27.8
27.9
28.1
Agora,calcule(1,2)(3,4)d(1,2,3,4).
Vocêdeveacharassimetriasdeumretângulo.
Háseissimetriasdeumtriânguloequilátero.
Háduassimetrias.
Hádezsimetrias:umaidentidade,quatrorotaçõesecincoflips.
Resposta de (c):A diferença é que as
primeiras24simetriassãorotaçõesdo
cubo.Asoutras24sãoasimagensespelhadasdas24primeiras.
Umarotaçãoporumânguloθ podeser
.
representadapelamatriz
n
Para(b),façaaexpansãode1,1 usandooteoremabinomial:
|f (n)|≤A|g(n)|
Analogamente,comog(n)éO (h(n)),
existeumnúmeropositivoB demodo
que,com,nomáximo,umnúmerofinitodeexceções,
|g(n)|≤B|h(n)|
Combinando essas duas desigualdades, temos, com, no máximo, um
númerofinitodeexceções,
|f (n)|≤A|g(n)|≤AB|h(n)|
demodoquef (n)éO (h(n))
28.5 Useaidentidade:
loga n =(logb a)(loga n)
28.7 Arespostaéou
.
28.8 Arespostadesseproblemaseriamuito
simplessevocêpudesseusarafunção
mod;elaserian mod10.
29.1 x =0,6.
29.3 Umresultadodesseexperimentopode
serregistradocomo(a,b),emquea é
ou K ou C (o resultado da jogada da
moeda)eb éuminteirocom1≤b ≤6
(afacesuperiordodado).Assim,
,
,
,
eignoreostermosdequevocênãoprecisa.
28.2 (c)éfalsa.Porexemplo,ë0,7+0,8û=
ë1,5û=1,masë0,7û+ë0,8û=0+0=0
28.3 Eisumaprovacompleta.
Comof(n)éO (g(n)),existeumnúmeropositivoA talque,com,nomáximo,umnúmerofinitodeexceções,
Apendice-3.indd 16
Todosesses2 ´ 6=12resultadossão
igualmente prováveis, de modo que
P : S → R é dada por P(s) = para
todos ÎS.
29.4 Para(a):oespaçoamostralé(S,P)em
queS ={1,2,3,4}eP(s)= paratodo
s ÎS.
29.5 Uma resposta completa para (b):
o conjunto S consiste em todos os
subconjuntos de cinco elementos do
09/04/2010 19:14:07
Apêndices
conjunto{1,2,...,20}.Assim,|S|=
.Todosessesresultadossãoigualmenteprováveis,demodoqueP(s)=
1/ paratodos ÎS.
29.6 Eisumarespostaparaaregião3:P(3)
= .
Explicação:aáreatotaldoalvo(todasasquatroregiõesjuntas)é16p.A
áreadaregião3é9p–4p=5p.Assim,
aregião3cobre daáreatotal.
29.7 SejaS ={1,2,3}esejaP(1)=1,P(2)
=0eP(3)=0.
29.8 SejaS ={1}esejaP(1)=1.
Note que, se um espaço amostral
(S,P)tem2(oumais)elementos,não
podemosterP(s)=1paratodos ÎS;
se|S|>1,então
oquenãoépermitido.
29.9 Verdiscussão“Muitaconfusãoemtornode0!”,naSeção8.
30.1 Eisumarespostaparak =4.TemosA4
={(1,3),(2,2),(3,1)}eP(A4)= .
30.2 A ={KKCC,KCKC,KCCK,CKKC,
CKCK,CCKK}eP(A)= = .
Noteque|A|= =6.
30.5 (a)A ={KCKCKCKCKC,CKCKCK
CKCK}.
(b)P(A)=2/210=2–9=1/512.
30.6 A ={(2,6),(3,5),(4,4),(5,3),(6,2)}.
30.9 OconjuntoA contém1+2+3+4+5
resultados.
30.10 Chameascaixasde1,2,3,...,10.
OespaçoamostralS contémtodasas
listas de caixas, de comprimento 2 e
semrepetição.Assim,|S|=(10)2=90.
Suponhaqueacaixa1sejaademenor
valor,atéacaixa10,demaiorvalor.
Agora, é exatamente como o problemaanterior.
Apendice-3.indd 17
17
30.11 Paracompararosdados1e2,façauma
tabela.Aslinhasdatabelasãoindexadas
pelosnúmerosdodado1,eascolunas,
pelos números do dado 2. Colocamos
um⋆paracadacombinaçãoemqueo
dado1bateodado2.
5
6
7
8
9
18
2
3
4
⋆
⋆
⋆
⋆
⋆
⋆
⋆
⋆
⋆
⋆
⋆
⋆
⋆
⋆
15
16
17
⋆
⋆
⋆
⋆
⋆
⋆
⋆
Observequehá21maneirasdeodado
1baterodado2,demodoqueaprobabilidadedeodado1baterodado2é = ≈58,33%.
30.12Eisumarespostacompletapara(b).Há
13escolhasparaqualvalorseráusado
natriplae,paracadaumdeles,há =
4escolhasdequecartasserãousadas
para aquela tripla. Feita a escolha da
tripla, há 12 escolhas para qual valor
será usado o par. Dado esse valor, há
=6escolhasparaquaiscartasserão
usadasnopar.Assim,há13 ´ 4 ´ 12
´ 6=3.744diferentesfull-houses.Assim,aprobabilidadedeseescolherum
full-house é
,
Aaproximaçãonuméricaresponde
àsdemaispartes:
(a)2,11%,(c)42,26%,(d)4,75%e
(e)0,198%.
30.13Por convenção, uma soma vazia tem
valor0,demodoqueP(Ø)=0.
OfatodequeP(S)=1decorreda
definiçãodeespaçoamostral.
09/04/2010 19:14:08
18
Matemática Discreta
SeA ÇB =Ø,entãoP(A ÈB)=P(A)
+P(B)– P(A ÇB)=P(A)+P(B)–P(Ø)
=P(A)+P(B).
30.14(a) /210= ≈24,61%.
(b)27/210=2–3= =12,5%.
(c) /210= ≈2,05%.
(d)PelaProposição30.7,aprobabilidadeé
,
30.15Esse problema pode se tornar confuso,demodoqueérecomendáveluma
boanotação.SejaA oeventodevermosaomenosum1,esejaB oevento
devermosaomenosum2.Aspartes
desse problema exigem (e apontam
comoencontrar):
(a)P( ).
(b)P(A)=1–P( ).
(c)P(B),queéomesmoqueP(A).
(d)P( Ç ). Notequeissoéomesmo
).
queP(
).
(e)P(A ÈB)=1–P(
(f)P (A ÇB)=P(A)+P(B)–P(A ÈB).
30.16Noteque(A ÇB)Ç(A Ç )=Ø.Note,
também,que(A ÇB)È(A Ç )=A.
Assim,
Ø
30.17Eisumaprova.Observeque
e
ComoA ÍB,todosostermosdaprimeirasomaestãotambémcontidosna
segunda soma. Como as probabilidadessãonãonegativas,issoimplicaque
asegundasomaé,nomínimo,igualà
primeira,istoé,P(B)≥P(A).
Apendice-3.indd 18
30.18Useaprovaporcontradição.
30.19UseaProposição30.8eindução.
30.20P (A Ç ) = P(Ø) = 0. Interpretação:
éimpossívelumeventoocorrerenão
ocorreraomesmotempo.
30.21k =57.
31.1 Resposta completa de (a): P(A|B) =
P(A ÇB)/P(B)=P({2,3})/P({2,3,4})
=0,3/0,5=3/5=60%.
31.2 Eis uma resposta completa. Seja A
o evento de que nenhum dado exibe
um2,esejaB oeventodequeasoma
dosdoissão7.NotequeP(B)= = .
Alémdisso,A ÇB ={(1,6),(3,4),(4,
3),(6,1)},demodoqueP(A ÇB)= = .Assim,
31.3 Esseproblemanãoéigualaoanterior,
e tem uma resposta diferente. Nele,
você precisa achar P(B|A), enquanto
noanterior,vocêencontrouP(A|B).A
respostaéP(B|A)= .
31.5 Normalmente,vocêprecisaprovar(1)
⇔ (2),(1)⇔ (3)e(2)⇔(3).Noentanto,bastaprovarque(1)⇒ (2)⇒ (3)
⇒(1).Ou,simplesmente,prove(1)⇔
(3),pois(2)⇔(3)temprovaanáloga.
Essasduasimplicam(1)⇔(2).
31.6 Eventos disjuntos não são, em geral,
independentes. Por exemplo, considere a jogada de um dado. Seja A o
evento “aparece um número par” e
sejaB oevento“apareceumnúmero
ímpar”. Então P(A Ç B) = 0 ≠ P(A)
P(B)= .
31.9 Duas sugestões: Primeira, A Ç B e
A Ç sãoeventosdisjuntos,demodo
queP(A ÇB)+P(A Ç )=P[(A ÇB)
È(A Ç )].Segunda,(A ÇB)È(A Ç )
=A Ç(B Ç )pelapropriedadedistributiva.
31.10A resposta é sim em ambos os casos.
Use as fórmulas P(A|B) = P(A Ç B)/
09/04/2010 19:14:09
Apêndices
P(B) e P(B|A) = P(A Ç B)/P(A) para
mostrarporquê.
31.11 Sim.SuponhaP(A|B)>0.Issodizque
P(A Ç B)/P(B) > 0, de modo que P(A
ÇB)>0.ComoA ÇB ÍA,temos(ver
Exercício30.17)P(A)≥P(A ÇB)>0.
31.12Paraqueaequaçãotenhasentido,precisamos de P(A) ≠ 0; caso contrário,
P(B|A)nãoestarádefinido.Issodecorre do Exercício 30.17, pois A Í A Ç
B,demodoqueP(A)≥P(A ÇB)>0.
Agora,useadefiniçãodeprobabilidadecondicional.
31.13(a)P(A)= =
(b)P(B)= =
(c)P(A ÇB)=
(d)Sim,porqueP(A ÇB)=P(A)P(B).
31.14É necessário calcular P(A), P(B) e
P(A Ç B) e verificar se P(A)P(B) =
P(A ÇB).Deve-seencontrarP(A ÇB)
= .
31.15Emprincípio,vocêdevecalcularP(A),
P(B) e P(A Ç B) e verificar se P(A)
P(B)=P(A ÇB).Noentanto,paraesse
problema,notequeP(A ÇB)=0,mas
P(A)P(B)≠0.Portanto,oseventosnão
sãoindependentes.
31.17Ambasasafirmativassãoverdadeiras.
Para (a), use o Exercício 30.16. Para
(b),use(a).
31.19Todasastrêssãofalsas!Eisumcontraexemplopara(a).Suponhaqueoespaçoamostralsejaodopardedadosdo
Exemplo29.4.Sejamostrêseventos:
–A,osdadostêm2porsoma,istoé,
A ={(1,1)}.
–B,osdadostêm17porsoma,istoé,
B =Ø,e
–C,osdadostêm12porsoma,istoé,
C ={(6,6)}.
ObservequeA eB sãoindependentes,
pois P(B) = 0 – ver Exercício 31.18,
Apendice-3.indd 19
19
e B e C são independentes, de novo,
porqueP(B)=0.Noentanto,A eC não
sãoindependentes,pois
31.20S 2={(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)}.
Suasprobabilidadessãoasseguintes:
31.21SejaA oevento“osdoisponteirossomam6”.Comoconjunto,A ={(2,4),
(3,3),(4,2)}.Portanto,
31.23(a)A ={KKCCC,KCKCC,KCCKC,
KCCCK,CKKCC,CKCKC,CKCCK,
CCKKC,CCKCK,CCCKK}.
(b)P(A)=10p2(1–p)3.
31.24O conjunto A contém sequências,
todascomamesmaprobabilidade.
31.25Respostade(a):p(1–p).
Para(c),lembre-sedequeP(A|A ÈB)
=
31.26Olívia.
09/04/2010 19:14:09
20
Matemática Discreta
31.27(a)a0=0ea2n=1.
(b)ak–pak+1+qak–1(emqueq=1–p).
(c)Háumafórmulaparaak,daforma
ak=c1+c2sk,emquec1,c2essãonúmerosespecíficoses ≠1.
Utilize a parte (b) para encontrar s
e utilize a parte (a) para encontrar
c 1,c2.
32.1 Respostacompletapara(a):“X >3”é
oconjunto
32.9 Sim.Sejaa umvalorarbitrárionoconjunto
{2,3,4,5,6,7,8,9,10,J,Q,K,A}
esejab umvalorarbitrárionoconjunto
{♣,♦,♥,♠}.ObservequeP(X =a)=
eP(Y =b)= .Porfim,
{s ÎS :X(s)>3}={c,d}
32.2
32.3
32.4
32.6
32.7
32.8
Apendice-3.indd 20
eP(X >3)=0,7
Orientaçãopara(c):Oevento“X >Y”
é o conjunto {s Î S : X(s) > Y (s)}.
Quais, entre a, b, c e d, estão nesse
conjunto?
Pista para(f):ÉverdadequeP(X =
m ÙY =n)=P(X =m)P(Y =n)para
todososinteirosm en?
Eisumasoluçãocompleta.
(a) Seja (S, P) o espaço amostral do
ponteiro,demodoqueS ={1,2,3,4}.
Então,X :S→ZédefinidaporX(1)=
10,X(2)=20, X(3)=10eX(4)=20.
(b) O evento “X = 10” é o conjunto
{1,3}.
(c)P(X =10)= + = eP(X =20)=
.Paratodososoutrosinteirosa (isto
é,a ≠10ea≠20),temosP(X =a)=0.
Arespostade(c)é = .
Arespostade(a)é3.
P(X =1)= = .P(X =–2)=0.
Sea <0oua >10,entãoP(X =a)é
zero. Em outros casos, isso é como
uma variável aleatória binomial em
queaprobabilidadedesucessoé .
Não.NotequeP(XH =1)=P(XT =1)>
0,masP(XT =1ÙXH =1)=0≠P(XH =
1)P(XH =1).
CalculeP(X1=5),P(X2=5)eP(X1=5
eX2=5).
Portanto,X eY sãovariáveisaleatórias
independentes.
32.10CalculeP(X =2),P(Y =2)eP(X =Y
=2).
33.1 E(X)=1 ´ 0,1+3 ´ 0,2+5 ´ 0,3+8
´ 0,4=5,4.
33.2 E(X)= ,E(Y)=0eE(Z)=13/3.
33.4 Seja (S, P) o espaço amostral de um
únicodado,istoé,S ={1,2,3,4,5,6}.
SejaX(s)=s2.AcheE(X).
33.5 SejamX1onúmeronaprimeirafichae
X2onúmeronasegunda.Assim,X =X1
+X2.NotequeE(X1)=E(X2)=(1+2
+...+100)/100=50,5,demodoque
E(X)=101.
33.6 Respostade(d):Porsimetria,sim.
Respostade(e):Como100=E(Z)
=E(XH +XT)=E(XH)+E(XT)ecomo
E(XH)=E(XT),temosE(XH)=E(XT)=
50.
33.7 SejaX umavariávelaleatóriazero-um.
Então,E(X)=0.P(X =0)+1.P(X =1)
=P(X =1).
33.8 Noteque12=1e02=0.
33.9 ExpresseX comoumasomaden variáveis aleatórias indicadoras zero-um e
apliquealinearidadedaesperança.
33.11 ApliqueaProposição33.4.
33.13Antes,mostramosqueE(X)=5,4.Podemoscalcular
09/04/2010 19:14:10
Apêndices
′
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
′
,
,
Alternativamente,podemosusarafórmulaVar(X)=E(X2)–E(X)2.Temos
,
,
,
,
e,assim,Var(X)=E(X2)–E(X)2=35
–5,42=5,84
33.15UseafórmulaVar(Z)=E(Z 2)–E(Z)2.
Para a segunda parte, ver o Exercício
33.13.
33.16UseoExercício33.15.
33.17UseadesigualdadedeMarkov(Exercício33.12).
34.1 Arespostade(b)éq =–34er =2.
34.2 Arespostade(b)é–100div3=–34e
–100mod3=2.
34.4 Leia atentamente a primeira sentença
daDefinição34.6.
34.5 Estaéametademaisdifícildaprova.
(⇒) Suponha a ≡ b(n). Isso significa
que n|(a – b) ou, equivalentemente,
a –b =kn paraalguminteirok. Sedividirmosa eb porn,obtemos
′
′
com0≤r,r′ <n.Notequer =a mod
n er′ =b modn.
Sesubtrairmosessasequações,Obteremos
′
′
ecomoa –b =kn,podemosreescrever
essaexpressãocomo
Apendice-3.indd 21
21
′
′
demodoquer – r′ éummúltiplode
n. Mas r e r′ estão entre 0 e n – 1.
Assim,devemosterr –r′ =0,istoé,
r =r′ .Comor =a modn er′ =b mod
n,temos
a modn =b modn
34.6 Má ideia:Chameostrêsinteirosconsecutivosdea,b ec.
Boa ideia: Chame os três inteiros
consecutivosa,a +1ea +2.
34.9 Eisumaboadefiniçãoparaaparte(a):
Sejamp eq polinômios.Dizemosque
p divideq (eescrevemosp|q)seexiste
umpolinômior talqueq =pr.
35.1 Arespostade(d)émdc(–89,–98)=1.
35.2 A reposta de (d) é (–89)(11) + (–98)
(–10)=1.
35.4 Tentealgunsexemplos.
35.5 UseoEsquemadeprova14.
35.6 Sim,elasaindasãocorretas.Explique
aigualdademdc(a,b)=mdc(b,c)nessecaso.
35.7 É suficiente provar que se a ≥ b > 0,
entãob ≥a modb.
35.9 (a)Umarespostacompleta:Omáximo
divisorcomumdetrêsnúmerosa,b e
c éuminteirod comasduasseguintes
propriedades:
(1)d|a,d|b ed|c e(2)see|a,e|b ee|c,
entãoe ≤d.
(b)A frase a, b e c são relativamente
primos dois a dois significaquemdc(a,
b)=mdc(a,c)=mdc(b,c)=1.
35.10UseoCorolário35.9.
35.11 TenteacharinteirosX eY demodoque
X(2a +1)+Y(4a2+1)=1;osinteiros
X eY dependemdea.
35.12Useaprovaporcontradição.
09/04/2010 19:14:10
22
Matemática Discreta
35.13Useofatodequepodemosencontrar
inteirosx ey demodoqueax +by =1.
Portanto,c =cax +cby.
35.14UseoCorolário35.9.
35.15UseoCorolário35.9.
35.16Invertaospapéisdea,b ex,y.
35.17Expliqueporquepodemostomarb >0
e,então,escolhab tãopequenoquanto
possível (invocando, assim, o princípiodaboaordenação).
35.18Numereascriançasde0an –1eimaginequeaprofessoracomeceporafagaracriança0primeiro.
Noteque,sek =4en =10,aprofessora nunca afagará a cabeça das
criançasdenúmerosímpares.
Noentanto,sek =3en =10,então
ascriançasserãoafagadasnaseguinte
ordem: 0, 3, 6, 9, 2, 5, 8, 1, 4 e 7 e,
assim,todasserãoafagadas.
35.195 ´ 13–8 ´ 8=1
36.1 Algumasrespostas:(a)6.(g)6.(n)7.
36.2 Aordemdeoperaçõesdaaritméticamo-
dular é a mesma que a da aritmética
comum,demodoquefazemos⊗e⊘
antesde⊕e⊖.
Enquanto as três primeiras podem
ser feitas pelo método de tentativa e
erro,aquartanãoéreceptivaataltipo
de abordagem. Em cada caso, você
precisarácalcularumrecíprocoemZn.
IssopodeserfeitopormeiodaextensãodoalgoritmodeEuclides.
36.3 Como o coeficiente de x em cada um
desses problemas é não invertível, o
método normal de solução para essas
equações não funcionará. Recomendamos que você recorra ao método
detentativaeerro.Épossívelquenão
hajasoluções.
36.4 Usetentativaeerro.Arespostade(d)é
2,7,8e13.
Apendice-3.indd 22
36.6 Useosfatosdeque
a ⊕b =(a +b)modn e
a ⊖b =(a –b)modn
OprimeirodecorredaDefinição36.1e
osegundo,daProposição36.7.
36.7 UseoTeorema34.1.
36.9 Suponhaquea ⊖b =(a –b)modn e
provequeb ⊕(a ⊖b)=a.
36.10Arespostaé:
a ⊗b =0⇔a =0oub =0
éumteoremaseesomentesen forprimo.
A estrutura da prova é um pouco
complicada.
Suponha, inicialmente, que n seja
primoeproveque
a ⊗b =0⇔a =0oub =0
Emseguida,suponhaquen nãoseja
primoeproveque
a ⊗b =0⇔a =0oub =0
éfalsa.
36.11 Esteéumproblemafácil.Vocêprecisa
provar que o inverso de a–1 é a. Leia
aDefinição36.9devagarecuidadosamente.
36.12Eis uma resposta completa para (a).
Falso.Contraexemplo:NotequeemZ5
tanto2como3sãoinvertíveis(2–1=3
e3–1=2);noentanto,2⊕3=0nãoé
invertível.
36.14Para calcular 332, calcule primeiro 316
e,então,faça332=316⊗316.
37.3 Eisumasoluçãocompletapara(a):
Sabemosque x ≡4(5).Issosignificaquepodemosescrever
x =4+5k
09/04/2010 19:14:10
Apêndices
emquek éuminteiro.Levandoissona
segundaequaçãox ≡7(11),obtemos
4+5k ≡7(11) ⇒ 5k ≡3(11)
Para resolver 5k ≡ 3 (11), multiplicamosambososmembrospor5–1emZ11.
Usando o método estendido de mdc,
temos 5–1 = 9. Multiplicamos, então,
ambososmembrospor9:
38.1
9 ⊗5⊗k =9 ⊗3=5
demodoquek ≡5(11).Issosignifica
quepodemosescreverk como
k =5+11j
38.2
38.3
paraalguminteiroj.Levandoissoem
x =4+5k,obtemos
x =4+5k =4+5(5+11j)=29+55j
evemos,então,quex ≡29(55).
Para(c),resolvaasduasprimeiras
equivalênciasparaobterumaresposta
intermediáriadaformax ≡?(28)e,então,resolvaosistema
x ≡?(28)ex ≡8(25)
pelométodousual.
Para (d), simplifique de início as
duasprimeirasequivalênciasdemaneira
queambassetornemdaformax ≡?(?).
37.7 Eisumasoluçãocompletapara(a).
Sejab1=8–1=12emZ19.Sejab2=
19–1=3–1=3emZ8.Assim,
Observeque363mod8=3e363mod
19=2,comopedido.
Como8 ´ 19=152,podemosreduzirx0módulo152,obtendo363mod
Apendice-3.indd 23
38.5
38.8
23
152=59.Noteque59mod8=3e59
mod19=2.
Uma resposta completa para esse
problemaéx =59+152k,emquek ÎZ.
Podemos, no entanto, escrever também
x =363+152k,emque k ÎZ.Estaé
exatamente a mesma resposta expressa
demaneiradiferente.
Eis uma boa maneira de começar sua
prova:“Suponha,porcontradição,que
exista um inteiro composto n cujos
fatores (diferentes de 1) sejam todos
maioresque ....”
Respostade(b):4.200=23.3.52.7.
Ageneralizaçãoé:Sejamp eq primos
distintos.Entãop|x eq|x seesomente
se(pq)|x.
Comecefatorandoa eb emprimos(de
maneiraúnica).
Noteque,paradoisnúmerosquaisquer
s et,temos
s +t =mín[s,t]+máx[s,t]
38.11 Chameosquadradosperfeitosconsecutivosdea2e(a +1)2(emquea éum
inteiro)esuponha(porcontradição)que
existaumprimop quedivideambos.
38.12Observeque18=21 ´ 32,demodoque
tododivisorpositivode18sejadaforma2a3b,emque0≤a≤1e0≤b≤2.
Dessemodo,há2escolhasparaae3
escolhasparab,resultandoem2´3=6
divisorespositivos.
38.13Os divisores de n são 2k e 2k(2a – 1)
paratodo0≤k <a.
38.14Émaisfácilprocurarquantosnúmeros
entre1en nãosãorelativamenteprimoscomn.
A resposta de (f) é φ(5.041) =
4.970. Para ver por que, note que os
únicosnúmerosentre1e712quenão
09/04/2010 19:14:11
24
Matemática Discreta
sãorelativamenteprimoscom712são
osmúltiplosde71:71,2 ´ 71,3 ´ 71,
..., 71 ´ 71.Assim,há5.041–71=
4.970inteirosde1a712quesãorelativamenteprimoscom712.
38.16Useinclusão-exclusão.SejaAi oconjuntodosmúltiplosdepi entre1en.
38.18Asentençaseguinteéútil:Sen nãoé
umquadradoperfeito,devehaverum
primop queapareceumnúmeroímpar
devezesnafatoraçãoden emprimos.
38.20Sejax =log23.Issosignificaque2x =
3.Suponhax = paraalgunsinteirosa
eb ecaminheparaumacontradição.
38.22 Eisumarespostacompletapara(c).
].IssosigniSuponhaw,z ÎZ[
ez =c+d[
],
ficaquew =a +b
emquea,b,c ed ÎZ.Observeque
ecomoac –3bd ead +bc sãointeiros,
].
temoswz ÎZ[
Eisumapistapara(d).Sew=a +
,então
b
Tentededuzir:Paraquaisinteirosa eb
esão
tambéminteiros?
são
ez =c +
38.23Para(a),sejamw =a +b
.ParamostrarqueN(wz)=N(w)
d
N(z),façaaexpansãoemtermosdea,
b,c ed,etenhacuidadocomaálgebra.
Eisumarespostaparcialpara(b).
] com N(w) =
Não há w Î Z[
) =
2. Prova: Suponha N(a + b
a2+3b2=2.Seb ≠0,temosN(w)≥3,
demodoqueb =0.Issonosdeixacom
a2=2,oqueéimpossível,poisa ÎZ.
Há exatamente seis valores possíveisdew paraosquaisN(w)=4.
Apendice-3.indd 24
38.24Primeiro, prove o seguinte lema: Se
N(w)é primo, entãow é irredutível.
38.25Seaafirmativafossefalsa,poderíamos
encontrar um contraexemplo w com
N(w)tãopequenoquantopossível.
38.26Queremosescrever4=ab coma,b ≠
±2,±1.Tomandonormasemambosos
membrosde4=ab,obtemos16=N(4)
=N(ab)=N(a)N(b).Nãopodemoster
N(a)N(b) = 2 ´ 8 porque não existe
elemento com norma 2.Assim, devemosterN(a)=N(b)=4.
39.3 RespostadeÙ:AoperaçãoÙéfechada,comutativa,associativa,eVERDADEIRO é o elemento identidade. No
entanto, FALSO não tem um inverso.
Logo, ({VERDADEIRO, FALSO}, Ù)
nãoéumgrupo.
39.4 Calculea *b *c.
39.5 Para mostrar que X e Y são inversos,
vocêdevedemonstrarqueX *Y =Y *
X =e.Paraesseproblema,vocêprecisa
mostrarqueoinversodeg –1ég.Sua
respostadeveserbemcurta.
39.8 Pegueseulivrodeálgebralineareleia
omaterialreferenteadeterminantede
umamatriz.
39.9 Lembre-se de que 2A é o conjunto de
todos os subconjuntos de A, e D é a
operaçãodediferençasimétrica.
Paraprovarque(2A,D)éumgrupo,
provequatropropriedades:fechamento,
associatividade, identidade e inversos.
Nota:Umadessasjáfoiprovada.
39.10Isso significa que você deve provar
quef : G → G éumaumesobre.Eis
umesboçodaprova.
Primeiro, prove f que é um a um.
Suponhaf (g)=f (k)parag,k ÎG....
Portanto,g =k e,assim,f umaum.
Em seguida, prove que f é sobre.
Seja b Î G. Seja x Î G definido por
09/04/2010 19:14:11
Apêndices
....Portanto,f(x)=b e,assim,f ésobre.
Assim,f éumapermutação.
39.11 VersugestãoparaoExercício39.10.
39.12OExercício39.10éútilaqui.Noteque
a linha da tabela de * correspondente
ao elemento a contém todos os elementosdaformaa *g,emqueg éum
elementoarbitráriodeG.
39.13Lembre-se:ParaprovarqueX eY são
inversos,mostrequeX *Y =Y *X =e.
39.15 Verifiquese⋆satisfazasquatropropriedadesexigidas.Notequeaidentidadee
inversospara*e⋆sãoosmesmos.
39.16Use a prova por contradição. Seja G
umgrupocomumnúmeropardeelementos e suponha que e seja o único
elementoqueéseupróprioinverso...
39.17EsseexercícioésemelhanteaoExercício39.12.
39.18Arespostade(c)é15:eisporquê.A
expressãoqueprecisamosavaliaré1,
2,+,3,4,´,+.Aspartes1,2,+dão3
easpartes3,4, ´ dão12.Aexpressão
sereduziua3,12,+,quedão15.
39.19Arespostade(a)é2,3,+,4,5,+,´.
39.20Eisumteoremaquedeveserprovado:
Sejaℓ umalistadenúmeroseoperações. Afirmamos que ℓ é uma expressãoNPRválidaseesomentesese
verificamasseguintescondições:(1)o
númerodeoperaçõesemℓéumamenosqueonúmerodenúmerose(2)as
sublistasdeℓ,começandonoiníciode
ℓeincluindotodososelementosdeℓ
atécertopontodalista,devemconter
maisnúmerosqueoperações.
Prove ambas as implicações desse
teoremaporindução.
40.1 Você precisa achar uma função um a
umesobre
f :{0,1,2,...,9}→{1,2,3,...,11}
Apendice-3.indd 25
25
comapropriedadedeque
Comececomf(1)=2.Apartirdaí,faça
f (1+1)etc.
40.2 Sejaf ([1,1]=1.
40.3 Umdosgruposécíclico;ooutro,não.
40.4 Consideref (e *e).
40.5 Para provar que f (g) e f (g –1) são inversos,façaaoperação⋆delesetorça
parachegarnaidentidade.
40.7 Eisumesboçodaprova.Completeas
lacunas.
Sejaf :G →H umisomorfismo.
(⇒) Suponha (G, *) abeliano. Sejamx,y ÎH arbitrários....Portanto,x
⋆y =y ⋆x e,assim,(H,⋆)éabeliano.
(⇐) Suponha (H, ⋆) abeliano. ...
Portanto,(G,*)éabeliano.
40.9 Sejaogrupo-4deKleindefinidonaseção39.
Eletem4elementos:(0,0),(0,1),
(1, 0) e (1, 1). Lembre-se de que o
conjunto 2{1, 2} é o conjunto de todos
ossubconjuntosde{1,2}equeDéa
diferençasimétrica.
40.10DefinaumaaplicaçãoF :G →H por
F(a)=fa.ProvequeF éumabijeçãoe
queF(a *b)=F(a)dF(b).
40.11 Os geradores de (Z10, ⊕) são 1, 3, 7
e9.Notequeessessãoexatamenteos
elementosdeZ10quesãorelativamenteprimoscom10.
Sevocêpuderprovarsuaresposta,
oprofessororecompensará.
40.13Eisumarespostapara .Em ,note
que 21 = 2, 22 = 4, 23 = 3 e 24 = 1.
Portanto,2éumageradorde .
41.1 Ossubgruposde(Z6,⊕)são{0},{0,3},
{0,2,4}e{0,1,2,3,4,5}.
41.2 Hátrêssubgrupos.
09/04/2010 19:14:11
26
Matemática Discreta
41.3 Hácincosubgrupos.
41.4 Nãoesqueçaumahipótese-chave:H ≠Ø.
Sãodados:
(1)H éfechadosob*.
(2)H ≠Ø.
(3)Paratodog ÎH,g –1ÎH.
Vocêdevemostrar:
(a)H éfechadosob*.
(b)e ÎH.
(c)Paratodog ÎH,g–1ÎH.
Asprovasde(a)e(c)sãotriviais.Assim,vocêprecisamostrarcomo(b)decorrede(1),(2)e(3).
41.5 Sãodados:(a)H ≠Øe(b)paratodosg,
h ÎH,g *h–1ÎH.
Vocêdeveprovar:(1)H éfechado
sob*,(2)e ÎH e(3)seg ÎH,então
g–1ÎH.
Provenaordem:(2),(3)e,então,(1).
41.6 SejaH umsubgrupode(Z,+).Pense
no menor elemento positivo de H (se
existir).
41.8 Aclassedeequivalênciamaisfácilde
seencontraré[1]=[e]=H.
Paraacharoutrasclassesdeequivalência,useasideiasdaprovadoLema
41.7.Escolhaumelementog ÎG edefinaumafunçãof :H →[g]porf (h)=
h * g. Para calcular [g], calcule f (h)
paratodoh ÎH.
Paraesseproblema,[2]={1,6,11,
16,21}.Háoutrasclassesdeequivalência.
41.9 Versugestãoanterior.
41.10VerProposição40.3.
41.11 Apenasumadessaséverdadeira.
41.12 Lembre-sedeque,emumgrupogeral,
x ≡y (modH)significaquex *y–1ÎH.
Nesseproblema,aoperação*éaadiçãocomumdeinteiroseoinversodey
ÎZésimplesmente–y.
41.13Nãouseumgrupoabeliano.
Apendice-3.indd 26
41.14A parte mais difícil desse problema é
aceitaradefiniçãodeg *H.Lembre-se
dequeg *H éumconjunto.Também,
x Îg *H significaquex =g *h para
algum h Î H. (Analogamente, x Î H
* g significa que existe um h Î H de
modoquex =h *g.)
Para a parte (b), comece provando
queg *H =H ⇔g ÎH.Adireção(⇒)
nãoédifícil[useaparte(a)].Paraadireçãooposta(⇐),énecessáriomostrarque
doisconjuntos(g *H eH)sãoiguais;
assim,useoEsquemadeprova5.
Paraaparte(d),versuarespostado
exercícioanterior.
42.1 Recomendoousodeumacalculadora
oudeumcomputador.Vocêdeveachar
a13=a paratodoa ÎZ13.
42.5 Sevocêusardivisãoportentativa,serão feitas dezenas de milhares de divisõesparaseacharosfatoresprimos
donúmerocomposto.Calcule2n mod
n paraambososvaloresden evejao
queobtém.
Háumadificuldadetécnicaaotrabalhar com esses números grandes.
Expressosembinário,elestêmcerca
de30bitsdetamanho;essesnúmeros
devemcaberemseucomputador.No
entanto, a multiplicação de dois númerosde30bitscadaproduzumnúmerode60bits;serádifícil,comuma
linguagemcomumdeprogramaçãode
computador, lidar com números tão
grandes.
42.6 Você precisará escrever um programa
decomputadorpararesolveresseproblema.Suamenorrespostaestáabaixo
de1.000.
43.1 Muitaslinguagensdecomputadortêm
funçõesembutidasparaaconversãode
textosparaedeASCII.
09/04/2010 19:14:12
Apêndices
44.2 Tenteusaressafórmulaparaumprimo
p ≢3(mod4),porexemplo,p =17.O
queacontecedeerrado?
44.3 Para você verificar, as respostas são
33,157,556e432.
44.4 Há oito respostas. Note que 34.751
=19 ´ 31 ´ 59e19≡31≡59a3
(mod4).
44.5 Fatorando n em primos, obtemos n =
45343 ´ 7243. Note que esses dois
primossãocongruentescom3módulo
4.SejaM =249500293.
EmZ45343,temos
249500293(45343+1)/4=12690
Assim,emZ45343,
12690ou32653.
EmZ7243,temos
=±12690=
249500293(7243+1)/4=2663
de modo que, em Z7243, temos
=
±2663=2663ou4580.
Resolvemos os quatro problemas
seguintes usando o teorema do resto
chinês.
As soluções desses quatro problemas
sãox ≡111103040,x ≡7151504,x ≡
321267845 e x ≡ 217316309 (todos
modn).Osegundodá07 15 15 04,
quedáGOOD.
Apendice-3.indd 27
27
44.6 Para (a), envie mais de uma mensagem.Apreocupaçãoem(b)équeM 2
modn ≡M 2(nãohá“despiste”módulon, demodoqueIvepossaencontrar
M extraindoaraizquadrada).Imagine
estratégiasparalidarcomisso.
44.7 mdc (75406, 68918, 171121) = mdc
(6488,171121)=811.
44.9 (a) Sugestão: fórmula quadrática. (b)
Resposta:281.
45.1 Resposta:D(N)≡N377mod589.
.
45.2 Lembre-se:d =e–1em
45.3 ArespostaéM =100.
45.4 Oexpoentedadecriptografiaéd =e–1
(modφ(n)).Arespostade(a)éPIGS.
46.1 Resposta de (a): ({1, 2, 3, 4, 5, 6},
{{1,2},{1,4},{2,3},{2,5},{3,6},
{4,5},{5,6}}).
46.2 Respostapara(a):
e
a
c
d
b
46.4 Se você está tendo problemas com
esseexercício,recomendoquedescanse,epeçaumapizza.Antesdecomer,
observebemasfatias.
46.9 Háumasoluçãocomapenasumestudante.
46.10Você acha que são impossíveis?Afirmo que não. Mas o que há de errado
comaseguinte“prova”dequeemnenhumgrafoarelação“éadjacentea”é
antissimétrica?
Seja G um grafo. Seja uʋ uma
arestadeG.Então,u ~ʋ eʋ ~u,mas
u ≠ ʋ. Portanto, ~ não é antissimétrica.
Leia essa “prova” atentamente.
Quando descobrir o erro, você saberá
responderaesseproblema.
46.12UseoTeorema46.5.
09/04/2010 19:14:12
28
Matemática Discreta
46.13Useaprovaporcontradição.Setodos
osvérticestêmgrausdiferentes,oque
elesdevemser?
46.15Useoproblemaanterior.
46.16VerSeção16.
46.17Notequeosseguintessãodoisgrafos
diferentes:
G1=({1,2,3,4},{12,13,14}) e
G2=({1,2,3,4},{12,23,24})
embora seus desenhos se pareçam
muito.(Elestêmomesmoconjuntode
vértices, mas diferentes conjuntos
dearestas.)
Recomendocomeçarcomoscasos
especiais n = 0, n = 1, n = 3 e n = 4
antesdeatacarocasogeral.Tenteescrevertodas as possibilidades.Observe, no entanto, que, para n = 4, você
deveencontrar64grafosdiferentes,de
modoqueprecisaserorganizado.
46.18Para(a),useaProposição23.25.
Eisumarespostacompletapara(b):
Sejaʋ ÎV(G).Notequeu éadjacenteaʋ seesomentesef (u)éadjacente
af (ʋ).Comof éumabijeção,issodá
uma correspondência um a um entre
osvizinhosdeʋ eosvizinhosdef (ʋ).
Portanto, ʋ e f (ʋ) têm o mesmo grau
(emseusrespectivosgrafos).
47.1 Osgrafospara(a),(d)e(g)são
2
4
3
5
2
1
3
5
2
1
Apendice-3.indd 28
6
4
4
3
6
47.2 Eisumaprovacompletadeque“éum
subgrafode”éantissimétrica.
SuponhaG subgrafodeH eH subgrafo de G. O primeiro implica que
V(G) Í V(H) e E(G) Í E(H), e o segundoimplicaoinverso.Assim,V(G)=
V(H)eE(G)=E(H)e,portanto,G =H.
Assim,“ésubgrafode”éantissimétrica.
47.3 Porexemplo,ografoK2temdoissubgrafos geradores e quatro subgrafos
induzidos.Vamoslistá-lostodosaqui.
Sejama eb osvérticesdeK2.
Os subgrafos geradores de K2 são
osdoisgrafosseguintes:
({a,b},{ab}) e ({a,b},Ø)
Os subgrafos induzidos de K2 são
osquatrografosseguintes:
Ø
Ø
ØØ
Se você pensou que eram apenas
trêsossubgrafosinduzidosdeK2,sua
resposta está errada, mas não é terrível.Osgrafos({a},Ø)e({b},Ø)têm
exatamenteomesmodesenho(apenas
umponto),masnãosãoexatamenteo
mesmo grafo. (Em um caso, o único
vérticeéa,e,nooutro,oúnicovértice
éb.)Essaconfusão,naverdade,ajuda
a resolver facilmente o problema. Há
uma sensação de que os grafos ({a},
Ø) e ({b}, Ø) são “os mesmos” (veja
Exercício46.18).
ParaK3, háoitosubgrafos geradoreseoitoinduzidos.
47.4 a(G)=3,ω(G)=2.
47.6 Exatamenteumadessasafirmativasé
verdadeira.Proveaverdadeiraeache
contraexemplosparaasoutrastrês.
47.7 Para(b),verfiguraseguinte:
09/04/2010 19:14:12
Apêndices
“Oh! Você parece
bem, hoje!”
Grafo autocomplementar - Cortesia de Laura Tateosian
Para(c),noteque,seG éautocomplementar,entãosabemosqueG e devemteromesmonúmerodearestas.
47.10(d) Seja G um grafo arbitrário com n
vértices.Observeque étambémum
grafocomn vértices.Comon →(a,b),
sabemosquea( )≥ a ouω( ) ≥ b.
Pelaproposição47.12,
a(G)=ω(G)≥a ou
ω(G)=a(G)≥b
(e) Pela Proposição 47.13, se n ≥ 6,
entãon →(3,3).PeloExercício47.8,
5↛(3,3).Sen <5en ↛(3,3),então,pelaparte(c),deveríamoster5→
(3,3)⇒⇐.Portanto,6éomenorinteiron possíveldemodoquen →(3,3).
(f) Seja G um grafo de dez vértices.
Sejaʋ umvérticequalquerdeG.
Sed(ʋ)≥6,então,entreosseis(ou
mais)vizinhosdosʋ,podemosencontrar ou (a) uma panela de tamanho 3
ou(b)umconjuntoindependenteetamanho3(pelaProposição47.13).No
primeiro caso, (a), ω(G) ≥ 4, porque
ʋ, juntamente com seus três vizinhos
adjacentesaospares,formaumapaneladetamanho4.Nosegundocaso,(b),
temosclaramentea(G)≥3.
Por outro lado (d(ʋ) ≱ 6), temos
d(ʋ) ≤ 5. Isso significa que há (pelo
Apendice-3.indd 29
29
menos) quatro vértices w, x, y, z aos
quais ʋ não é adjacente. Se eles formam uma panela, temos ω(G) ≥ 4.
Mas, caso contrário, algum par deles
nãosejaadjacentee(juntamentecom
ʋ)formeumconjuntoindependentede
tamanho3,demodoquea(G)≥3.
Em todos os casos, a(G) ≥ 3 ou
ω(G)≥4.Portanto,10→(3,4).
(g) Sugestão: Considere um vértice
arbitrário ʋ. Ou d(ʋ) ≥ m ou existem,
pelomenos,n vérticesaosquaisʋ não
éadjacente.
48.4 Arespostade(a)é .Para(b),noteque
todososvérticestêmomesmograu.
Em (c), para provar que Gn é conexo,escolhadoisvérticesarbitrários
e prove que existe um caminho que
osliga.
48.5 ∀$nãoéomesmoque$∀.
48.6 Eisumsugestão:
48.9 Eis um esboço detalhado da prova.
Completeaslacunas.
Suponha que G seja não-conexo.
Devemosmostrarque sejaconexo.
Como G é não-conexo, existem
vérticesx ey emcomponentesdiferentesdeG.
Considere, agora, quaisquer dois
vérticesa eb em .Vamosconsiderar
casos, dependendo de qual(is) componente(s)deG contém(contêm)a eb.
09/04/2010 19:14:12
30
Matemática Discreta
– a e b estão, ambos, na mesma
componente de x de G... Portanto,existeumcaminho(a,b)em .
–Um dos dois, a ou b, está na mesma
componente de x, e o outro não está.
... Portanto,existeumcaminho(a, b)
em .
–Nenhum dos dois, a e b, está na mesma componente que x.
... Portanto,existeumcaminho(a, b)
em .
Emtodososcasos,existeumcaminho(a,b)em .Comoosvérticesa e
b foramescolhidosarbitrariamente, éconexo.
48.10Comece,assim,asuaprova:Suponha,
porcontradição,queG nãosejaconexo.SejaH umacomponentedeG com
omenornúmerodevértices.
48.12Useinduçãosobrek.Aentradai, j de
At +1podeexpressar-secomo
49.3 Como esse problema pede que se demonstre uma afirmativa do tipo se e
somentese,vocêtemduastarefas.Primeiro,suponhaqued1,...,dn sejam
osgrausdosvérticesdealgumaárvore
T.Vocêdevemostrarqued1+...+dn
=2n –2;issoébastantesimples.
Sua segunda e mais desafiadora
tarefa é a seguinte. Suponha que sejamdadosinteirospositivosd1,...,
dn paraosquaissetenhad1+...+dn
=2n –2.Vocêdeveprovarqueexiste
umaárvoreemn vérticescujosgraus
são,exatamente,d1,...,dn.Paraisso,
recomendo indução. Comece mostrandoqueaomenosumdosgrausdi
éiguala1.
49.5 Eisumesboçoparasuaprova.
Apendice-3.indd 30
SejaG umgrafonoqualtodoparde
vértices é unido por um único caminho.QueremosmostrarqueG éuma
árvore.PelaDefinição49.3,devemos
mostrarqueG éconexo eacíclico.
–Afirmativa:G éconexo.Prove
que G é conexo por prova direta.
–Afirmativa:G éacíclico.Prove
que G é acíclico por contradição.
Portanto,G éumaárvore.

49.6 Sua prova deve usar a expressão por
vacuidade.
49.7 Esseproblemaserámaisbemresolvido por uma prova pela contrapositiva
(Esquemadeprova11):
Suponhaqueʋ nãosejaumafolha.
...Portanto,T –ʋ nãoéumaárvore.
49.8 Arespostade(d)é(n –1)!.Proveisso
porindução.
49.9 Afórmulaén –c.
49.10UseoExercício49.4.
49.11 Para (a), você deve usar, também, o
Teorema48.12.
49.12UseoTeorema49.4.
49.13UseosTeoremas49.9e49.11eoproblemaanterior.
49.14Para(c),useoExercício49.13.
49.15Essaéumaafirmativadotiposeesomentese,portanto,certifique-sedeque
fezasduasimplicações.Eisumametadedaprova.
(⇒)Sejae =xy umaarestadecorte
de G. Suponha, por contradição, que e
esteja contida em um ciclo C. Como e
éumaarestadecortedeG,devemexistirvérticesa eb quesãoconexosemG,
masnãosãoconexosemG –e.SejaP
um caminho (a, b) em G. Necessariamente,P contémaarestae.Semperdade
09/04/2010 19:14:13
Apêndices
g eneralidade,ovérticex precedeovértice
y àmedidaquepercorremosP dea atéb.
NotequeemG –e existeumpasseio (a, b): comece em a, percorra P
atéx,percorraC –e atéb e,então,percorraP atéy.PeloLema48.7,devehaverumcaminho(a,b)emG –e.⇒⇐.
Portanto, e não está contida em qualquerciclodeG.
49.17Proveque,nopasso(4),ografoT éconexoeacíclico.
49.18Comonoproblemaanterior,proveque
ograforesultante(oT final)éconexoe
acíclico.OExercício49.15oajudará.
50.2 Kn possuiumtour euleriano?
50.3 Apartirdessenovovértice,acrescentearestasdemodoquemudetodosos
graus dos vértices para número par.
Verifique,então,queonovografocriadoéconexo.
50.4 Essaquestãonãoétãosimples.
51.2 AcondiçãodequeG seja3-colorável
significaqueG podeserpropriamente
colorido com, no máximo, três cores.
Vocênãotemdeusartodasastrês.
51.3 VerSeção47.
51.4 SeG temn vérticesenãoécompleto,
entãon >1.Alémdisso,G deveconter
doisvérticesquenãosãomutuamente
adjacentes.
51.7 DadaumacoloraçãoprópriadeG com
a coreseumacoloraçãoprópriade
Gcomb cores,mostrecomoobteruma
coloraçãoprópriadeKn comab cores.
51.8 Primeiro,mostrequeG épropriamente
4-colorável (isso é fácil). Em seguida,
suponhaque G seja3-coloráveleargumenteatéumacontradição.Dêumacor
ao vértice 1 e, então, discuta as cores
dosoutrosvérticesemordemnumérica.
51.11 Colorir primeiro o vértice de maior
grau.
Apendice-3.indd 31
31
51.12Proveissoporinduçãosobreonúmero
devérticesemG.
51.13Para(a),colorirosvérticescomquatro
cores.
Para(b),notequevocêprecisaprovarqueografonãoé3-colorável.Para
isso, você deve usar uma prova por
contradição. É útil, também, dar nomesapropriadosaosvértices.Chameo
vérticequeestánocentrodafigurade
u. Chame seus quatro vizinhos a1 até
a5eoscincovérticescorrespondentes
nabordaexternadafiguradeb1atéb5.
Para(c),emboraografotenhamuitas arestas, você deve usar simetria
para reduzir esse problema a alguns
poucoscasos.Precisacolorircadaum
dessesgrafoscomtrêscores.
52.1 Háinfinitasrespostas.
52.3 Você pode usar a fórmula de Euler
(Teoema52.3)e/ouimitarsuademonstração.
52.4 Se G não contém K3 como subgrafo,
entãotodafacedevetergrau,nomínimo,4.
52.5 Conteasarestas(usooCorolário52.5).
52.8 Embora o grafo se pareça um pouco
comK5,elenãocontémumasubdivisãodeK5comosubgrafo.(Setivesse,
teria um vértice de grau, pelo menos,
4.)AcheumasubdivisãodeK3,3como
subgrafo.
52.9 Para (a), imite a prova do Corolário
52.5.
Para(c),useindução.
52.10Aparte(a)jáfoiprovadanotexto.A
quantidadeʋr éasomadosgrauseé
igual a 2e.A quantidade f s é a soma
dosgrausdasfaceseé,também,igual
a2e.
Paraaspartes(b)e(c),useafórmuladeEuler(Teorema52.3).
09/04/2010 19:14:13
32
Matemática Discreta
Paraaparte(d),notequee deveser
uminteiropositivo.
A parte (e) é um pouco mais capciosa.Ocaso(3,3)jáfoifeitonaparte
(b).Oscasos(3,4)e(4,3)nãosãotão
difíceis.Tente(3,5)emseguida;lembre-se,afacenãolimitadatemtambém
grau5.Vocêdevesercapazdecalcular
quantasfacesdegrau5dequeprecisa (resposta: 12). Por último, o caso
(5,3)éomaiscomplicado.Vocêprecisaajustar20triângulos(facesdegrau
3)juntamentecom5triângulosquese
encontram em todos os vértices. Boa
sorte!
52.11 Desenhe um grafo na superfície da
bola de futebol norte-americano. Coloque um vértice em cada polígono e
unaosvérticesporumaarestaseseus
polígonos têm uma aresta comum.
Observequeesseéumgrafoplanarno
qualtodafaceéum3-cicloetodosos
vérticespossuemgrau5ou6.
Suponhaquehajaa vérticesdegrau
5 e b vértices de grau 6. Conte o númerodearestasdeduasmaneiraspara
deduzirquea =12.
53.1 (a)a eb sãonãocomparáveis.(c)c <i.
53.2 Para(a),aalturaé4eháváriascadeias
quecontêmquatroelementos,inclusive{b,d,f,i}e{a,c,f,j}.
Para (c), note que {a, c, i} é uma
cadeiaquecontémtrêselementos,mas
elapodeserestendidaa{a,c,f,i}.Assim,{a,c,i}nãoéarespostacorreta
para(c).
53.5 ProvequeR–1éreflexiva,antissimétricaetransitiva.
53.7 Eisumaprovacompleta.Suponha,por
contradição, que haja dois elementos
x ey,comx <y ex >y.Desenredando
essas definições, temos (1) x ≤ y, (2)
Apendice-3.indd 32
y ≤x e(3)x ≠y.Noentanto,x ≤y e
y ≤x implicam(pelaantissimetria)que
x =y,contradizendo(3).⇒⇐Portanto,
nãopodemosterambosx <y ex >y.
53.11 EisumaboadefiniçãoparaP –x.Seja
P =(X,≤).SejaP –x oconjuntoPO
com conjunto fundamental X – {x} e
relação≤′,emquea ≤′b seesomente
sea ≤b paratodososa,b ÎX –{x}.
54.1 Nãoháelementosmáximooumínimo.
Hátrêsmaximaisetrêsminimais.
54.2 Respostade(b):1émínimoeminimal.
3,4e5sãomaximais.Nãohámáximo.
54.4 Aafirmativa(d)éfalsa.
A afirmativa (g) é verdadeira. Eis
umaprovacompleta:
Suponhaquex ey sejamelementos
maximaisdistintos.Suponha,porcontradição,queelesnãosejamnãocomparáveis.Então,oux <y ouy <x.Se
x <y,entãox nãoémaximalesey <x,
entãoy nãoémaximal.⇒⇐Portanto,x
ey sãonãocomparáveis.
55.2 Para(a),noteque1<2<3e1<3<2
sãoordenslinearesdiferentesem{1,2,
3},massãoisomorfas.
55.3 Eisumesquemaparasuaprova.
Sejaa oelementominimaldeuma
ordemtotal,P.Sejax outroelemento
qualquer de P. . . . Portanto, a < x e,
assim,a éumelementomínimo.
55.5 Eismetadedaprovapara(a):
(⇒)Suponhaquex sejaumelementomínimoemP.Paramostrarquef (x)
é mínimo em Q, precisamos mostrar
que,seb éumelementoqualquerem
Q,entãof (x)≤b emQ.Comof ésobre,
háuma emP comf (a)=b.Comox é
mínimoemP,a ≥x.Assim,b =f (a)≥
f (x)(poisf preservaaordem).Portanto,f (x)émínimoemQ.
55.6 Useaparte(a)doexercícioanterior.
09/04/2010 19:14:13
Apêndices
56.2 Asrespostassão:(a)4,(b)14.400e(c)
252.Vocêdevedarasexplicações.
56.4 Peloexercícioanterior,se(x,y)nãoé
umparcrítico,então≤′nãoétransitiva. Isso aconteceporque há um elementoa ≤x eumb ≥y (diferentesde
a =x eb =y)coma /≤b.
Sejamu(a)onúmerodeelementos
estritamenteacimadea eℓ(a)onúmero
deelementosestritamenteabaixodea.
Mostrequeexisteumparnãocomparável(x,y)comℓ(x)+u(y)tãopequeno quanto possível. Prove que (x,
y)écrítico.
56.5 Note que (c, g) não é um par crítico
porquea <c masa ≮g.Também(g,c)
nãoéumparcríticoporquec <f mas
g ≮f.Noentanto,(a,g)éumparcríticoporquequalquerx <a estátambém
abaixodeg (porvacuidade)equalquer
y >g (especificamente,y =j)estátambémacimadea.
57.1 Adimensãoé2,masacharumrealizadordáalgumtrabalho.
57.2 UseoTeorema56.3
57.4 Eisumaprovacompleta.
SuponhaP umsubconjuntoPOde
Q.EscolhaumrealizadorR ={L1,L2,.
..,Lt}deQ detamanhomínimo.(Assim,t =dimQ.)
Seja ′ umasubordemdeLi restrita
aoselementosdeP.Notequeparatodososelementosx ey deP, temosx ≤y
(emQ)seesomentesex ≤i y (emLi,
paratodoi)seesomentesex ≤i y (em
′ paratodoi).Assim,R′ ={ , ,...,
}éumrealizadorparP e,portanto,
dimP ≤t =dimQ.
57.5 Este é um problema difícil. Primeiro,
mostrequedimP ≤3,construindoum
realizadorcomtrêsextensõeslineares.
Apendice-3.indd 33
58.1
58.3
58.4
58.5
58.7
33
Éútiltrabalharoscasosn =3en =4
primeiroe,então,procurarporumpadrãogeral.
ParamostrarquedimP >2écapcioso.Eisumatécnicaqueusacontagem.
Mostrequehán(n –2)paresnãocomparáveis da forma ai-bj. Então, mostre
queumaextensãolinearpodeterai >bj
no máximo,
vezes. Assim, se
dimP ≤2,precisaríamostern(n –2)≤
,eissolevaaumacontradição.
2
(b)d.(d)i.(e)a.
Proveaparte⇒observandoque,para
quaisquerx ey emumaordemlinear,
temosoux <y,oux =y,oux >y.Para
aparte⇐,usecontradiçãoeconsidere
umparnãocomparávelx ey.
Notequeesseresultadorequerquetodososnúmerosenvolvidosestejamem
N, isto é, não são permitidos inteiros
negativos.Portanto,x|y ⇒x ≤y.
OconjuntoPO(Z,≤)éumreticulado
sem elemento máximo ou mínimo. O
conjuntoPO(N,|)éumreticuladosem
elemento máximo (mas ele tem elementomínimo,1).
Para tornar a sentença verdadeira,
insiraapalavrafinito.
Mostrequeoseguintegrafonãoédistributivo.
e
b
d
c
a
58.8 Comececomoinfeosupdedoispontosdistintos.Seuinféoconjuntovazio
eseusupéaúnicaretaquecontémambos.Prossiga,agora,paraconsideraro
infeosupdeduasretasoudeumpontoeumareta.
09/04/2010 19:14:14
34
Matemática Discreta
B Soluções para as Autoavaliações Capítulo 1
Capítulo 1
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Apendice-3.indd 34
Falso.Ointeiropositivo1nãoéprimo
nemcomposto.
x|(x +2)paraxéiguala–2,–1,1e2.
A notação | significa que o número à
esquerdadivideonúmeroàdireita.A
expressão (ab) + 1 é absurda, porque
a|béumaafirmaçãoe1éumnúmero;
não é possível somar uma afirmação
comuminteiro!
“Seuminteiroéperfeito,entãoépar”
ou“sexéuminteiroperfeito,entãoxé
par”.
“Sevocêmeama,casacomigo.”
(a) falsa, (b) falsa, (c) verdadeira, (d)
falsa, (e) verdadeira e (f) verdadeira
(vagamente).
Primeira linha: “Suponhamos que M
sejaumamatroidegráfica”.
Últimalinha:“Portanto,Mérepresentável”.
(a)Hámuitoscontraexemplospossíveis,incluindox=3,y=2ez=–6.
Observe que x > y, mas xz = –18 <
–12=yz.
(b) Se exigirmos que z seja positivo,
segueaconclusão.Aafirmaçãoeditada
deveserlida,“Sex,yezsãointeiros,
x>yez>0,entãoxz>yz”.
(a) Isso é falso. Por exemplo, 2|10 e
5|10,mas7=2+5nãodivide10.
(b) Isso é verdadeiro; eis uma prova.
Suponhaquea|b.Então,existeuminteiro x, de forma que ax = b.A multiplicação de ambos os lados dessa
equaçãoporcresultaemaxc = bc,o
quepodeserreescrito(ac)x = bc.Portanto,ac|bc.
Amaioriadosnúmerosdedoisdígitos
sãocontraexemplosparaaproposição.
11.
Por exemplo, 152 = 225, mas 512 =
2.601≠522.Portanto,aproposiçãoé
falsa.
Oerronaprovaéquenegligenciamosoefeitodeintroduziraaritmética.
Éverdadeque(10a+b)2=(a2)´100
+(2ab)´10+(b2)´1,masissonão
significa que os dígitos de (10a + b)2
sejama2,2ab,b2.Porexemplo,seb>3,
entãob2>10e,dessemodo,osdígitos
unsde(10a+b)nãopodemserb2.
A prova está incorreta, porque supõe o que desejamos provar e, então,
trabalhaparaumfatoconhecidoóbvio
(porexemplo,0=0).Aabordagemdeveriaserooposto.
Eisaqui,essencialmente,amesmaprovautilizadaparademonstrarquea = b
paraquaisquerdoisnúmerosaeb.
Prova.Comececom
a=b
apartirdoquetambémobtemos
b=a
A multiplicação simultânea dessas
equaçõesresultaem
ab=ab
e, em seguida, o cancelamento de ab
deambososladosresultaem
0=0
12.
oqueestácorreto.
A partir dessa “prova” segue-se o
resultadodeque3=4.Evidentemente,
issoestáincorreto.
As duas expressões não são logicamenteequivalentes.Considereatabela
daverdade,aseguir:
09/04/2010 19:14:14
Apêndices
13.
y
x→¬y
¬(x→ y)
V
F
F
V
F
V
V
F
V
V
F
F
F
V
F
Comoascolunasx→¬ye¬(x→ y)não
sãoidênticas,asduasexpressõesnãosão
logicamenteequivalentes.
Aexpressão(x→y)Ú(x→¬y)éuma
tautologia. Considere a tabela da verdade,aseguir:
x
y
x→y
V
V
F
F
V
V
V
V
F
F
V
V
V
15.
16.
17.
V
F
18.
19.
x→ ¬y (x→y)¬(x → ¬y)
V
14.
Apendice-3.indd 35
x
V
F
V
V
V
ComoafórmulaéavaliadaparaTpara
todososvalorespossíveisesuasvariáveis,elaéumatautologia.
Sejaa +1ea +2trêsinteirosconsecutivos.Suasomaa +(a +1)+(a +2)=
3a+6.Observeque3a+6=3(a+2).
Como a + 2 é um inteiro, 3|(3a + 6).
Dessemodo,asomadequaisquerinteirosconsecutivosédivisívelpor3.
Sejaauminteiropositivo.Asomadea
inteirosconsecutivosédivisívelpora,
seesomenteseaforímpar.
Seja a ≥ 3 um inteiro.A multiplicaçãodeambososladosdea resultaem
a2≥3a.Observeque3a=2a+a>2a
+1,porquea>1.Destemodo,a2≥3a
>2a+1.
Suponhaqueasejaumquadradoperfeitoea≥9.Comoaéumquadrado
perfeito, existe um inteiro b com a =
b2.Podemossuporqueb>0.Paraque
a ≥9,devemoster b≥3.Observeque
a–1=b2–1=(b–1)(b+1).Como
b ≥ 3, sabemos que b – 1 ≥ 2 > 1 e
20.
35
b+1≥4>1,e,portanto,essesfatores
dea–1sãoambosmaioresque1;então,a–1éumcomposto.
Adefiniçãodeparesquadradosaplica-seapenasainteirospositivos.Embora
10 + (–1) seja um quadrado perfeito,
–1 não é positivo. Portanto, 10 e –1
nãosãoparesquadrados.
Sejax uminteiropositivo.Sejay =x2
+x+1;evidentemente,y>x,porque
somamos uma quantidade positiva
(x2+1)ax.
Observequex+y=x(x2+x+1)=
x2+2x+1=(x+1)2.Comox+1éum
inteiro, x + y é um quadrado perfeito
e,portanto,xeysãoparesquadrados.
Parax=5,6,7,8,9éfácilencontrar
paresquadradosmenoresquex,asaber:
(5,4),(6,3),(7,2),(8,1)e(9,7)
Comisso,ésuficienteprovaroresultadoparax>9.
Comopermiteoenunciadodoproblema, escolha um inteiro positivo a,
demodoquea2≤x<(a+1)2.Como
x>9,evidentementea≥3.
Sejay =(a+1)2–x.Obviamente,x + y
éumquadradoperfeitoey>0,porque
(a+1)2>x.Dessemodo,xey sãoparesperfeitos.Restamostrarquey<x.
Paraessefim,calculamos
por Problema
Capítulo 2
1.
Há 2 ´ 26 ´ 26 = 1.352 maneiras
de formar um indicativo de chamada
09/04/2010 19:14:14
36
2.
3.
Matemática Discreta
de3letrase2´26´26´26=35.152
maneiras de formar um indicativo de
chamada de 4 letras. Ao somar isso,
obtemos 36.504 possíveis indicativos
dechamada.
Observe que podemos escolher a e b
arbitrariamente e, então, escolher c
cuidadosamenteafimdequea + b + c
seja par. Mais especificamente, há 10
escolhas para a e, para cada escolha
dessetipo,10escolhasparabe,então,
umavezqueaebtenhamsidoescolhidos,exatamente5escolhasparac.Isso
resultaem10´10´5=500possíveisescolhas.
Deformaalternativa,semarestriçãosobreasoma,há103=1.000escolhasparaa,b,c,eexatamentemetade
delas apresenta soma par, resultando
em1.000÷2=500escolhas.
Há 103 maneiras de escolher a, b, c,
independentemente de seu produto.
Afimdequeabcsejaímpar,todosos
três,a,b, c,devemserímpares.Há53
=125maneirasdequeissopossaacontecer.Portanto,há1.000–125=875
maneirasdeescolhera, b, c,deforma
queabcsejapar.
6.
7.
8.
9.
10.
4.
5.
Apendice-3.indd 36
Há13!maneirasdeorganizarascartas
dentrodedeterminadonaipe,demodo
que 13!4 formas possíveis de ordenar
as cartas com os naipes. Então, existem 4! maneiras de organizar os naipes.Noconjunto,issoresultaem4!´
13!4possíveisorganizações.
Nãohánecessidadedecalcularmais
isso, mas, caso você tenha calculado,
deveráobteroseguinteresultado.
11.
12.
13.
36085481721713375974666734560
870400000000
Os dez casais podem aparecem em
10!ordens.Paracadaumadessasordens,há2escolhasporcasal,dependendoseumaesposaestáàfrentede
seumaridoouvice-versa.Issoresulta
emumtotalde10!210possíveisorganizações.
Arespostaé0,vistoqueoprimeirotermonoprodutoé =0.
PodemosescreverAcomo{–9,–8,...,
8,9}e,portanto,|A|=19.
(a) é VERDADEIRA e (b)-(e) são
FALSAS.
(a) VERDADEIRA. Prova: Suponha
queXÎ2AÇB.Então,X ÍA ÇB,e,desse
modo,XÍAeXÍB.Portanto,X Î2A
eX Î2B,demodoqueX Î2AÇB.
Por outro lado, suponha que X Î
AÇB
2 .Então,X ÍAÇB,e,assim,XÍA
eXÍB.Portanto,X Î2AÇ2B.
ComodemonstramosqueX Î2AÇB
⇔XÎ2A Ç2B,temos2AÇB=2AÇ2B.
(b)FALSA.Contraexemplo: SejaA =
{1,2}eB ={3,4}.Observeque2AÈB
=2{1,2,3,4}contém16elementos,
2A È 2B contém 4 + 4 = 8 elementos.
Portanto,2AUB≠2AU2B.
(c)FALSA.Contraexemplo: SejamA e
B quaisquerconjuntos.SabemosqueØ
Î2A∆B.Entretanto,comoØÎ2AeØÎ
2B,constatamosqueØÎ2A∆B.
(a) FALSA, (b) VERDADEIRA, (c)
VERDADEIRA,e(d)FALSA.
(a)FALSA,(b)FALSA,(c)VERDADEIRA,e(d)VERDADEIRA.
Aafirmação(a)nãoénecessariamente
verdadeira;porexemplo,sep(x, y)for
sempreverdadeira,issoseriafalso.
Aafirmação(b)deveserverdadeira
combasenasregrasparaanegaçãode
afirmaçõesquantificadas(eofatodeque
09/04/2010 19:14:14
Apêndices
¬[¬p(x, y)]élogicamenteequivalente
ap(x, y)).
A afirmação (c) também deve ser
verdadeira. Se a afirmação ∃y, p(x, y)
éverdadeiroparatodososinteirospossíveisx,então,certamenteéverdadeiro
paraalguminteirox.
DadoqueA´B={(1,2),(1,3),(2,2),
(2,3)},deveserocasodequeA={1,2}
eB={2,3}.Então,AÈB={1,2,3},
AÇB={2}eA–B={1}.
Aseguintefiguraapresentaumdiagrama de Venn de (A – C) È (B – C) =
(AÈB)–C.Observeque,secombinarmosasáreashachuradasA – C(parte
superior,àesquerda)comB – C(parte
superior,àdireita),obtemosaáreahachurada(AÈB)–C(parteinferior).
14.
15.
A
A
B
B
A–C
B–C
C
C
A
B
(A ∪ B) – C
C
Agora,paraumaprova-padrão.
SuponhaquexÎ(A – C)È(B – C).
IssosignificaquexÎA – CouxÎB
– C.SexÎA – C,entãoxÎAexÏ
C.ComoxÎA,certamentetemosxÎ
AÈB,e,comoxÏC,podemosconcluirquexÎ(AÈB)–C.Domesmo
modo, se x Î B – C, concluímos que
xÎ(A È B)–C.Dessemodo,sexÎ
(A–C)È(B–C),entãoxÎ(AÈB)–C.
Apendice-3.indd 37
16.
17.
18.
37
Por outro lado, suponha que x Î
(AÈB)–C.IssosignificaquexÎAÈB
exÏC.ComoxÎAÈB,sabemosque
xÎAouxÎB.CasoxÎA,desdeque
x Ï C, concluímos que x Î A – C e,
portanto, x Î (A – C) È (B – C). Do
mesmo modo, se x Î B, concluímos
quexÎ(A – C)È(B – C).Portanto,
sexÎ(AÈB)–C,entãoxÎ(A – C)
È(B – C).
ComoxÎ(A – C)È(B – C),sexÎ
(AÈB)–C,constatamosque(A – C)
È (B – C)=(AÈB)–C.
Apartirde|A|+|B|=|A ÈB|+|AÇB|,
obtemosaequação10+|B|=15+3,
deemque|B|=8.
((AÈB)–(A – B))–(B – A).
Perguntamos: Quantas listas de comprimento 3 podem ser formadas utilizando-senelementos?
Deumlado,hán3listasdessetipo.
Poroutro,ostrêselementosnalista
deveriam ser (a) todos diferentes, (b)
doisdomesmotipoeumdiferenteou
(c) todos os mesmos. No caso (a), há
(n)3=n(n–1)(n–2)listasdessetipo.
Nocaso(b),hánescolhasparaoelemento repetido, (n – 1) escolhas para
o elemento não repetido e 3 escolhas
paraaposiçãoqueoelementonãorepetido pode ocupar, para um total de
3n(n – 1) listas. Por fim, há n listas
em que todos os três elementos são
os mesmos.Ao somar isso, descobrimos que a resposta para a pergunta é
n(n–1)(n–2)+3n(n–1)+n.
Comoessasduassãorespostascorretasparaamesmapergunta,devemos
obter
n3=n(n–1)(n–2)+3n(n–1)+n
09/04/2010 19:14:14
38
Matemática Discreta
Capítulo 3
1.
2.
3.
4.
5.
Apendice-3.indd 38
(a) Este é o conjunto contendo seus
filhos.
(b) Este é o conjunto contendo seus
pais.
(c) R é irreflexiva (nenhum deles são
seuspais)eantissimétrica(vagamente,
desdequex R yey R xnãopossamser
mantidosparaqualquerx, y).Asoutras
propriedades (reflexiva, simétrica e
transitiva)nãosãomantidas.
(d)R –1relaçãoé o filho de.
As relações em (a) e (b) são relação
deequivalência;éfácilverificarsesão
transitivas,simétricasereflexivas.
Arelaçãoem(c)nãoéumarelação
deequivalência.Emborasejareflexiva
esimétrica,nãoétransitiva.Porexemplo,suponhaqueAliceeBobtêmum
filho, George (g), Bob e Cindy têm
um filho, Harry (h), e Cindy e Dave
têmumafilhaInga(i).Então,g R h eh
R i sãomantidas,mash R i éfalsa.
ArelaçãoRsobreAéumsubconjunto
deA´A.Emoutraspalavras,R Ì A ´
Aou,deformaequivalente,RÎ2A´A.
Como|A´ A|=4·4=16,acardinalidadede2A´Aé216,eeisnossaresposta.
Há216relaçõesdefinidasemA.
Não. Por exemplo, adote x = 2 e y =
112. Então, x ≡ y tanto em mod 10
comoemmod11.
(a)Réreflexiva:sexforqualquerinteiro,então,evidentemente,|x|=|x|.R é
simétrica:sex R y,então|x|=|y|,desse
modo|y|=|x|e,portanto,y R x.R étransitiva:sex R y ey R z,então|x|=|y|e|y|
=|z|e,assim,|x|=|z|.Portanto,x R z.
Portanto, R é uma relação de equivalência.
(b)[5]={–5,5},[–2]={–2,2}e[0]
={0}.
6.
7.
8.
As classes de equivalência são [1] =
[2]=[3]={1,2,3}=Ae[4]=[5]=
{4,5}=B.
Há 6 classes de equivalência que dependem da cardinalidade dos conjuntos(de0a5).
Suponhaquexeysejaminteiros.Entãox yseesomentesexeytiverem
omesmosinal.
Observequeosinaldeuminteirox
éfrequentementedenotadoporsgnxe
definidopor
se
se
se
9.
10.
11.
A resposta é 10!210/20; eis o porquê.
Imaginequeoscasaisprimeiroformem
uma fila. Há 10!210 maneiras para que
elesfaçamisso,emqueosmaridoseas
esposaspermaneçampróximosaosseus
respectivoscônjuges.VeroProblema6
doAutoteste,noCapítulo2.
Umavezenfileirados,elessesentam
aoredordamesa(digamos,emsentido
horário). Duas dessas organizações de
assentos são equivalentes se um deles
for uma rotação do outro. Cada classe
de equivalência apresenta 20 modelos
deassentos,demodoquehaja10!210/20
classesdeequivalência.
Onúmerodeanagramascomunsdeda
palavrainglesaELECTRICITYé11!/
(23),porqueapalavrapossuionzeletraseincluidoisdecadaE,CeT.Para
cada anagrama desse tipo, há 10 maneirasdeinserirumespaçoparacriar
umanagramadeduaspalavras.Consequentemente,arespostaé10·11!/8.
Denominemosostrêstiposdequadradosemumquadrodejogodavelhade
canto, lateral e centro. Contamos as
09/04/2010 19:14:15
Apêndices
12.
13.
Apendice-3.indd 39
possibilidades dependendo do movimentodoprimeirojogador.
–OprimeirojogadormarcaumX
emumquadradodocanto.
Nessecaso,osegundojogadortem
cinco reações diferentes: canto próximo,cantodistante,lateralpróxima,lateraldistante,centro.
–OprimeirojogadormarcaumX
emumquadradolateral.
Nesse caso, novamente o segundo
jogador tem cinco reações diferentes:
canto próximo, canto distante, lateral
próxima,lateraldistante,centro.
– O primeiro jogador marca um
X no centro. Nesse caso, o segundo
jogador tem duas reações diferentes:
canto,lateral.
Portanto,há12paresdeaberturadiferentes(nãoequivalentes)demovimentosnojogodavelha.
Arespostaé21!/(210·10!);eisoporquê.
Imaginequeosalunosformemumafila
e, em seguida, o professor seleciona
os parceiros de laboratório escolhendo
dois alunos de cada vez da fila. O último aluno na fila trabalhará sozinho.
Duasorganizaçõesdafilaqueresultam
no mesmo pareamento são consideradasequivalentes.
Há21!maneirasdiferentesparaque
os alunos formem a fila. O tamanho
de todas as classes de equivalência é
10!·210porqueosprimeirosdezpares
podem ser reorganizados e os alunos
emumparpodemtrocardeposições.
Portanto, há 21!/(210 · 10!) maneirasnãoequivalentesparaqueosalunos
formemafila,eissoforneceonúmero
depareamentos.
Arespostaé porqueestamosescolhendoumsubconjuntode10elementosdeA′ ={1,3,5,...,99}e|A′ |=50.
14.
15.
39
Peloteoremabinomial,otermox17é
x17250–17,portantoarespostaé 233.
Oproblemapodeserreescrito
(n +0)+(n +1)+(n +2)+...+(n +n)
16.
17.
oqueseigualaan2+
.
Opcionalmente,issopodeserainda
maissimplificadopara(3n2+n)/2.
maOtimepodeserescolhidode
neiras, e para cada uma dessas escolhas, há maneiras para selecionar
oscocapitães,paraumtotalde
maneiras possíveis para selecionar o
timeeoscocapitães.
Prova combinatória: Seja N um conjunto finito, com |N| = n + 2 e suponhaqueosdoiselementosdeNsejam
considerados excêntricos. Quantos
subconjuntosdek +2elementosdeN
podemserformados?
Deumlado,arespostaésimplesmente
.
Dooutrolado,podemosconsiderar
quantosexcêntricosestãonoconjunto:
zero, um ou dois. Há maneiras de
escolherumsubconjuntodekelementosquecontenhaambososexcêntricos,
maneiras com um excêntrico e
2
maneirassemnenhumexcêntrico,
+
.
paraumtotalde +2
= +2
+
.
Portanto,
Prova pela identidade de Pascal:
Ao aplicar a identidade de Pascal a
, obtemos
=
+
.A
aplicação da identidade de Pascal a
cadaumdessesresultaem
e,então,asomadessasduasequações
= +2
+
.
resultaem
09/04/2010 19:14:15
40
18.
19.
20.
Matemática Discreta
Para (a) a resposta é e para (b) a
.
respostaé
n
A resposta é 4 .Cada elemento potencialj (com1≤j ≤n)podeaparecerno
multiconjunto0,1,2ou3vezes.Seja
mj amultiplicidadedoelementoj.Em
vezdecontarosmulticonjuntosdiretamente,podemoscontarlistasdaforma
(m1,m2,...,mn),emquecadamjÎ{0,
1, 2, 3}. Portanto, há 4 escolhas para
cada elemento da lista, para um total
de4nlistas.
Seja Aj o conjunto de colorações em
que a linha j é inteiramente de uma
cor.Oconjuntode“más”coloraçõesé
A1È...ÈA4.Onúmerode“boas”coloraçõesé216–|A1È...ÈA4|.
Avaliamosissodaseguintemaneira:
8
2.
3.
4.
5.
Issoéiguala 164(-2)0+ 163(–2)1
+ 162(–2)2+ 161(–2)3+ 160
(–2)4,quesesimplificapara(16–2)4
peloteoremabinomial.
Alternativamente,há16–2maneiras de colorir cada linha, portanto há
144possíveiscolorações.
Capítulo 4
1.
Apendice-3.indd 40
real,a.Comoaéumnúmeroreal,devemosterumadea<0,a=0oua>
0,mas,emcadacaso,a2≥0.Portanto,
a2≠–1,deformaquea2+1≠0.⇒⇐
Suponha, levando-se em conta a contradição,quehajaquatrointeirosconsecutivos,a,a+1,a+2,ea+3,cuja
somasejadivisívelpor4.Ouseja,a+
(a+1)+(a+2)+(a+3)+=4a+6é
divisívelpor4.Portanto,háuminteiro
b,deformaque4b=4a+6,resultando
emb – a= oub – a–1= .Observe
queb – a–1éuminteiro,mas nãoé.
⇒⇐
Sabemosquea|beb|a.Portanto,existemosinteirosxey,comax = b eby =
a.Amultiplicaçãodessesjuntosresultaemabxy=ab.Comoa, b>0,sabemosqueab≠0,portantoadivisãode
abresultaemxy=1.Osúnicospares
deinteirosquesemultiplicampararesultarem1são(x, y)=(1,1)e(x, y)
= (–1, –1). Este é impossível porque
se a = (–1)b, então a e b não podem
serambospositivos.Portanto,(x, y)=
(1,1)e,dessemodo,a = b.
Osconjuntos(b),(c),(d)e(f)sãobem
ordenadoseosoutrosnãoosão.
Aprovaéporinduçãoemn.Ocason =
1(casobásico)éóbvioporqueambos
osladossãoestimadospara1.
Suponha(hipótesedaindução)que
oresultadosejaverdadeiroquandon =
k;ouseja,
A soma de 3(k + 1) – 2 = 3k + 1 em
ambososladosresultaem
Suponha, levando-se em conta a contradição,quex2+1=0tenhaumaraiz
09/04/2010 19:14:16
Apêndices
Observeque
8.
9.
e,portanto,
6.
7.
conformeexigido.
A prova é por indução em n. O caso
básico,n =0,émantido,porqueambos
os lados da desigualdade são estimadospara1.
Suponha(hipótesedaindução)que
adesigualdadetenhasidoprovadapara
n = k;ouseja,0!+1!+...+k!≤(k +
1)!.Asomade(k +1)!emambos os
ladosresultaem0!+1!+...+k!≤(k +
1)!≤2·(k +1)!.
Observeque(k +2)!=(k +2)·(k +
1)! ≥ 2 · (k + 1)! (porque k + 2 ≥ 2,
vistoquek≥0).Portanto,0!+1!+...+
(k +1)!≤(k +2)!,conformeexigido.
A prova é por indução em n. O caso
básico,n =0,éverdadeiroporquea0=
1e(2·40+1)/3=3/3=1.
Suponha que o resultado seja provadoquandon=k(ouseja,ak =(2·
3k + 1)/3). Considere agora que ak+1.
Sabemosqueak+1=4ak–1e,portanto
conformeexigido.
Apendice-3.indd 41
41
A prova é por indução em n. O caso
básico,n =0,éverdadeiro,vistoque
0<20.
Suponhamos (hipótese da indução)
quek<2k.Devemosdemonstrarquek +
1<2k+1.Paraessafinalidade,somamos
1aambososladosdek<2kparaencontrark+1<2k+1≤2k+2k=2k+1.
Prova levando-se em conta a contradição: SuponhamosqueP sejaumconjunto finito de pontos em que quaisquertrêspontossejamcolineares,mas,
levando-seemcontaacontradição,os
pontos não estejam todos em uma linhacomum.EscolhaumalinhaLque
inclua dois pontos, por exemplo, x e
y,emP.ComoL nãocontémtodosos
pontos em P, há um terceiro ponto z
ÎPquenãoseencontraemL.Então,
entretanto,x,y,zsãotrêspontosdeP
que não são colineares.⇒⇐ Portanto,
todosospontosemPestãoemumalinhacomum.
Prova por indução: A prova é por
indução em uma série de pontos (ou
seja,|P|).Nocasoemqueoconjunto
apresentaapenas3pontos,oresultado
éóbvio.
Suponha que a proposição tenha
sidoprovadaparatodososconjuntosde
k pontos.SejaP umconjuntodek +1
pontosquesatisfazahipótesedaproposição. Seja a qualquer ponto em P
esejaP′=P –{a}. Então,P′ também
satisfaz a hipótese da proposição e,
portanto,porindução,ospontosemP′
estãoemumalinhacomumL.Sejamx
eydoispontosdistintos(excetoa)em
P; observe que x, y, a estão em uma
linha comum e, visto que L contémx
e y, os três estão em L. Desse modo,
todosospontosemP estãoemL.
09/04/2010 19:14:16
42
10.
Matemática Discreta
A prova é por indução em n. O caso
básico,n=1,éverdadeiroporqueambososladosdadesigualdadesãoestimadospara1.
Suponha(hipótesedaindução)que
oresultadosejaverdadeiroquandon =
k;ouseja,
O primeiro termo da segunda soma
é x0yk+1 e o último termo da primeira
soma é xk+1y0. Caso contrário, coletamososseguintestermosdasduassomas e observamos que os coeficiente
+ ,
dexjyk+1–j(com1≤j≤k)é
que,pelaidentidadedePascal(Teore.
ma16.10),éiguala
Portanto,
Afimdedemonstrarqueoresultadoé
verdadeiroquandon = k+1,somamos
a ambos os lados dessa desigualdadeparaobter
12.
Como
11.
<
+1,obtemos
e, portanto,
+
+ ... +
+
≤ (k + 1)
, conforme
exigido.
A prova é por indução em n. Para o
caso básico, n = 0, observamos que
(x + y)0 = 1 e também åj x j y n-j =
x0y0=1.
Suponhamos(hipótesedaindução)
que o resultado tenha sido provado
para n = k. Buscamos provar o caso
n = k + 1. Observe que (x + y)k+ 1 =
(x + y)(x + y)k e podemos expandir
este,obtendo
conformenecessário.
Aprovaéporinduçãoemn.Cason=
1,alinhaúnicadivideoplanoemduas
regiõese + + =1+1+0=2,
confirmandoocasobásico.
Suponhamos(hipótesedaindução)
queoresultadosejaverdadeiroparaas
coleções de k linhas. Considere uma
coleçãodek+1linhasquesatisfaçaa
hipótesedoresultado.SejaLqualquer
umadessaslinhas.
Observequeaskoutraslinhasdividemoplanoem + + regiões.
AlinhaLinterceptacadaumadastrês
klinhaseatravessak+1regiões;portanto,ask+1linhasdividemoplano
em + + +(k+1)regiões.Isso
podeserreescritocomo
Apendice-3.indd 42
09/04/2010 19:14:17
Apêndices
Observeque
15.
13.
e, portanto, as k + 1 linhas dividem o
+
+
regiões.
planoem
A prova é por indução forte em n. O
caso básico, n = 0, é evidente porque
ambososladodaequaçãosãoestimados para 3.A equação também é verdadeira para n = 1, porque ambos os
ladossãoestimadospara5.
Suponhamos (hipótese da indução
forte) que a equação tenha sido demonstradaparan =0,1,2,...,k(onde
k≥1).Emparticular,temos
Asomadessasequaçõesresultaem
14.
Apendice-3.indd 43
que representa, precisamente, o caso
n = k+1doresultado.
Provamosissoporinduçãoemn.Para
ocasobásico,n=0,observamosque
F0 = F1 = 1, portanto o único divisor
positivodeambosé1.
Suponhamos(hipótesedaindução)
que o único divisor positivo de Fk e
Fk+1 seja 1. Devemos demonstrar que
1 é o único divisor positivo de Fk+1 e
Fk+2.Suponhamos,levando-seemconta a contradição, que haja um inteiro
d >1comd|Fk+2ed|Fk+1.ComoFk+2=
Fk+Fk+1,constatamosqueFk=Fk+2
–Fk+1e,dessemodo,seddividirtan-
43
toFk+2comoFk+1,vemosqued|Fk.No
entanto,então,d|Fked|Fk+1,masd>1.
⇒⇐Portanto,oúnicodivisorpositivo
deFk+1eFk+2é1.
(a)Considereoprimeiroladrilho.Seo
ladrilhofor1´1,entãoexistem2escolhasparaacordoladrilho,eorestante da tira pode ser completado de an –1
maneiras.Seoladrilhofor1´2,então
existem3escolhasparasuascoresean –2
maneiras de cobrir de ladrilhos o restantedatira.Comisso,há2an –1+3an –2
maneirasdecobriratiradeladrilhos.
(b)Provamosissopelainduçãoforteem
n. No caso n = 1, há apenas 2 maneirasdecobriratiradeladrilhos,e(32+
(–1)1)/4=(9–1)/4=2.Nocason–2,
há2´2maneirasdecobrircomladrilhos
utilizandodoisladrilhosde1´1e3maneirasdecobrircomladrilhosutilizando
umúnicoladrilhode1´2,paraumtotal
de7coberturascomladrilhospossíveis.
Suponhamos(hipótesedainduçãoforte)queoresultadotenhasidoprovado
paran=1,2,...,k(emquek≥2).Em
particular,sabemosque
Utilizandoaidentidadequeprovamos
em(a),obtemos
conformeexigido.
09/04/2010 19:14:17
44
Matemática Discreta
16. Prova.
Existência.Aprovaépelométododo
menorcontraexemplo[demodoalternativo,poderíamosescreveressaprova
utilizando a indução forte]. Suponhamosqueoresultadosejafalso,eseja
x um menor contraexemplo. Observe
quex≠1,vistoquepodemosescrever
1 = 20 · 1. Note também que x não é
ímpar,entãopoderíamosescrever1=
20· x.Dessemodo,podemossuporque
x é par. Nesse caso, x/2 é um inteiro
positivo menor (e, portanto, não um
contraexemplo),entãopodemosescrever =2a·b,emquebéímpar.Mas,
então,x=2a+1·b,abalandonossasuposiçãodequexéumcontraexemplo.
⇒⇐ Portanto, todo inteiro positivo n
podeserexpressonaforman=2ab,em
quebéímpar.
Singularidade: Suponha, levandoseemcontaacontradição,quehajaum
inteiro n e pares distintos de inteiros
nãonegativos(a,b)e(c,d),demodo
quebedsejamímparese
n=2ab=2cd
Se fosse o caso em que a = c, então
2ab = 2cd ⇒ b = d, contradizendo a
asserçãodeque(a,b)e(c,d)fossem
paresdiferentes.
Portanto,a ≠ c.
Semaperdadageneralidade,a < c.
Portanto,
2ab=2cd⇒b=2c–ad
17.
Apendice-3.indd 44
em que c – a > 0. Portanto, b é par,
mas também é ímpar. ⇒⇐ Portanto,
háapenasumpardeinteirosnãonegativos(a, b),deformaquen=2abe
béímpar.
(a)Provamosissoporinduçãosobreo
18.
19.
tamanhodeA.NocasoemqueAtenha
apenasumelemento,t,então,evidentemente,t|t,entãoocasobásicoéverdadeiro.
Suponhamos(hipótesedaindução)que
oresultadosejaverdadeiroparatodos
osconjuntosdeinteirospositivoscom
kelementos.SejaA umconjuntocom
k+1elementosquesatisfaçamacondição (ou seja, ∀r Î A, ∀s Î A, (r|s
ou s|r)). Seja x qualquer elemento de
A esejaA′ = A – {x}.ObservequeA′ é
umconjuntodek inteirospositivosque
satisfazacondição.Portanto,porindução,A′ contémumelementot′ parao
qual a|t′ paratodoa Î A′.Agora,visto
que x Î A, x|t′ ou t′ |x. No primeiro
caso, observe que todos os elementos
deA sãodivisoresdet′ ,eterminamos.
Casocontrário(t′ |x),ecomotodosos
elementos de A′ são divisores de t′ e
t′ |x,segue-sequetodososelementos
deAsãodivisoresdex.
(b) Suponhamos que A contenha dois
elementos t e s diferentes com a propriedade de que todos os elementos
emAsãodivisoresdesetambémde
t.Issoimplicaques|t et|s.Comos, t >
0,segue-se(verProblema3)ques = t.
⇒⇐Portanto,A contémumelemento
singularqueémúltiplodetodososelementosemA.
(c)SejaA ={–2,–1,1,2}.Éfácilverificar se para todo a, b em A, a|b ou
b|a.Contudo,A possuidoiselementos
distintos,–2e2,quesãomúltiplosde
todos.
(a)an= (–3)n+3/2(2)n
(b)an =–4·2n+8
(c)an =6n– n6n.
Aplicamos∆repetidamenteaessasequênciaedescobrimososeguinte:
09/04/2010 19:14:18
Apêndices
6.
Portanto,
Capítulo 5
1.
2.
3.
4.
5.
Apendice-3.indd 45
(a)f(2)=3
(b)f(4)éindefinida
(c)domf={1,2,3}
(d)imf={2,3,4}
(e)f–1={(2,1),(3,2),(4,3)}
(f) g–1 = {(1, 2), (1, 3), (2, 4)} não é
umafunção,porquecontémdoispares
ordenados distintos da forma (1, ?).
(Alémdisso,gnãoéumaum.)
(g)g df ={(1,1),(2,1),(3,2)}
(h)f dg ={(2,2),(3,2),(4,3)}
(a)Verdadeira.(b)Verdadeira.(c)Verdadeira.(d)Falsa.Para(d),observeque
f :A →BexigesomentequeimfÍB.
(a)43=64.(b)(4)3=4´3´2=24.
(c)nenhuma.
Não,f nãoénecessariamentesobrejetiva.Porexemplo,sejaf:Z→Zpelaf(x)
=2xesejag amesmafunção.Observe
quetantof comog sãoumaum,mas
nenhumadelasésobrejetiva.
Noentanto,seAeB sãoconjuntos
finitos, entãosucederiaque f é sobrejetiva.
(a) Primeiro, f não é um a um. Por
exemplo,f (–2)=|–2|=2,portantof (2)
=f (–2),mas,obviamente,2≠–2.
45
(b)Emsegundolugar,f ésobrejetiva.
Sejax ÎN.ComoNÍZ,certamente
x ÎZef (x)=|x|=x(vistoqueénão
negativa).Portanto,f ésobrejetiva.
(a)f éumaum.Oferecemosduasprovas.
Prova 1:Afirmamosqueféumafunçãocrescente;ouseja,sex <y,então
f (x)<f (y).Paraconstatarporque,consideramostrêscasos:
* x e y são ambas não negativas (ou
seja,0≤x<y).Nessecaso,x < yimplicaquef (x)=f 3=x . x2<y . x2<y .
y 2=y 3=f (y).
* xeysãoambasnegativas(porexemplo,x < y <0).Comox < yeambas
sãonegativas,x 2>y 2>0e,portanto,
x3<y3,portantof (x)<f (y).
* x énãonegativaey énãonegativa.
Nessecaso,f (x)=x3<0≤y3=f (y).
Emtodososcasos,x < y →f (x)<f (y).
Portanto,sex ≠y,certamenteconstatamosquef (x)≠f (y),e,assim,f éum
aum.
Prova 2: Suponha f (x) = f (y). Dessemodo,x3=y3e,portanto,x3–y3=
(x – y)(x2+xy +y2).
Afirmamosquex2+xy +y2nãopode
ser igual a zero. A partir da fórmula
quadrática,
e, como
é imaginária, não pode
havernenhumpardeinteirosx eypara
oqualx2+xy +y2=0.
Vistoquex2+xy +y2≠0e0=x3–y3
=(x – y)(x2+xy +y2)=0,entãox = y.
Portanto,fésobrejetiva.
(b)f nãoésobrejetivaporquehánenhum inteiro x de modo que f(x) =
x3=2.
09/04/2010 19:14:18
46
7.
8.
9.
10.
Matemática Discreta
A única função que é uma relação de
equivalênciaem{1,2,3,4,5}é{(1,
1),(2,2),(3,3),(4,4),(5,5)}.
Há 64 posições para um bloco de 2
´2,masapenas24=16formasdiferentesdecolorirosquadradosemum
bloco.Portanto,peloPrincípiodaCasa
dosPombos,doisblocosdevemsercoloridosdeformaidêntica.
Além disso, suponha (levando-se
emcontaacontradição),quecadauma
das 16 possíveis colorações ocorram
nomáximo3vezes.Issosópodeacontecersehouver3´16=48maneiras
ou menos 2 ´ 2 blocos. No entanto,
há 64 blocos desse tipo. ⇒⇐ Portanto,algummodelo2´2deveserepetir
quatrovezes.
Comoh(1)=3eh(1)=f [g(1)],devemosterg(1)=2ou4.Demaneira
semelhante,apartirdeh(2)=f [g(2)]
= 3, devemos ter g(2) = 2 ou 4. A
partirdeh(3)=2=f [g(3)],devemos
ter g(3) = 1.A partir de h(4) = 5 =
f [g(4)],devemosterg(4)=5.Apartir h(5) = 3 = f [g(5)], devemos ter
g(5)=2ou4.
Portanto, sabemos que g = {1, ?),
(2, ?), (3, 1), (4, 5), (5, ?)}, em que
cada?podeserum2ouum4,resultandoemoitopossíveisrespostas.
Observeque
11.
Noteque
A partir disso, sucede-se que a = 1 e
b=2.
Portanto,
12.
13.
Um matemático discreto se sentiria
confortávelcomadefinição00=1.
Primeiro, podemos considerar 00
como um produto vazio e, portanto,
iguala1(comonaSeção8).
Emsegundolugar,podemosconsiderar00comoonúmerodefunçõesdo
conjuntovazioparasipróprio.Existe
exatamente uma função desse tipo –
a saber, o conjunto vazio. De fato, o
conjunto vazio é uma função porque
satisfazadefiniçãodefunção,embora
vagamente.Odomínioeaimagemdo
conjuntovazio(comoumafunção)são
ambosoconjuntovazio.Estaéaúnica
funçãopossíveldoconjuntovaziopara
sipróprio.
A asserção f = g –1 é falsa, como demonstra o contraexemplo a seguir.
SejaA =Z,sejag(x)=2xparatodoxÎ
Zeseja
Observe que, para qualquer inteiro x,
( f d g)(x)=f [g(x)]=f [2x]=x,demodo
quef d g =idZ,Noentanto,f≠g–1.Por
Apendice-3.indd 46
09/04/2010 19:14:18
Apêndices
exemplo,(5,0)Îf,mas(0,5)Ïgou,
nanotaçãousual,f(5)=0,masg(0)≠5.
(a)[(1,3),(2,9),(3,2),(4,6),(5,5),
(6,7),(7,4),(8,1),(9,8)}
(b)p=(1,3,2,9,8)(4,6,7)(5)
(c)p–1=(1,8,9,2,3)(4,7,6)(5)
(d)pdp=(1,2,8,3,9)(4,7,6)(5)
(e)p=(1,8)d(1,9)d(1,2)d(1,3)d
(4,7)d(4,6)e,portanto,pépar.
Háapenasn!elementosdeSn,portanto,
asequênciap=p(1),p(2),p(3),...,deve-se
repetirnofinal.Sejajomenoríndice,
demodoquep(j)=p(k)paraalgumk > j.
Afirmamosquej=1.Suponha,levando-seemcontaacontradição,que
tenhamos p(j) = p(k) com 1 < j < k.A
composição de ambos os lados dessa
equaçãoàesquerdaporp–1resultaem
π
π
π
16.
17.
π
π
π
contradizendoofatodequej foioprimeiroíndicedeumelementorepetido.
⇒⇐Portanto,j =1.
Dessemodo,p = p(k) paraalgumk
>1.Acomposiçãoàesquerdaporp–1
resulta em p–1 d p = p–1 d p(k), de em
queι=p(k–1),emquek–1>0.
Sek–1=1,issosignificaqueι=
pe,portanto,p = pi–1=p(1).Casocontrário,(ouseja,k –1≥2),constatamos
queι=p(k–1)=p d p(k–2).Portanto,p(k–2)
= p–1ek–2épositivo.
A soma é estimada para 0, desde que
tantoostermospositivoscomoostermos negativos (em ordens diferentes)
sejamreorganizadospara1+2+...+n.
(a) Sabemos que podemos escrever p
como uma composição de transposições (verTeorema 26.11) da seguinte
maneira:
p=t1dt2d...dtb
Apendice-3.indd 47
47
Seti=(1,xi),oudeformaequivalente,
(xi,1),isole-o.seti=(xi, yi)comxi, yi
>1,entãoosubstituímoscom(1,xi) d
(1,yi) d(1,xi),vistoque(xi,yi)=(1,
xi) d (1, yi) d (1, xi).Após essas substituições, expressamos p como uma
composiçãodetransposiçõesdaforma
(1,x).
(b)EmS3,observeque
ι = (1, 2) d (1, 3) d (1, 2) d (1, 3) d
(1,2)d (1,3)
18.
Observe que tanto (1, 2) como (1, 3)
aparecemtrêsvezes.
Prova 1: Suponhamos que p tenha ℓ
inversões,deformaquesgnp=(–1)ℓ.
ObservequeemtodofatorP1≤i<j≤n(xj –
xi),omaiortermosubscritoprecedeo
menor. Mas em P1≤i<j≤n(xp(j) – xp(i)) há
exatamenteℓfatoresemqueomenor
termosubscritoprecedeomaior,portanto,afimderestabeleceraigualdade,podemosmultiplicarpor(–1)ℓ.
Prova 2: Decomponha p como a
composiçãodetransposições,p = t1 d
... d ta.Começandopeloprodutooriginal, P1≤i<j≤n(xj – xi), substitua os subscritosicom ta(i)parai=1,...,n.Se
ta=(p, q),entãon –2dostermosda
forma±(xp – xj)tornam-se±(xa – xj),
eoutrosn –2termosdaforma±(xq–
xj) tornam-se ±(xq – xj); não há efeito
sobreoprodutoàmedidaqueoresultadodessestermossemodifica.Noentanto,otermo±(xp – xq)torna-se±(xq
– xp),resultando em uma mudança de
sinal para todo o produto. À medida
que cada transposição subsequente é
aplicada, o sinal é alterado, portanto,
no final, mudamos os sinais a vezes.
Logo, o produto resultante é (–1)a =
sgn pvezesooriginal.
09/04/2010 19:14:18
48
19.
20.
21.
Matemática Discreta
(a)Começandoapartirdeumaposiçãoinicial,ovértice1podesertransposto para qualquer um dos quatro
ângulos.Ovértice2podesergirado
emqualquerumadastrêsposiçõese,
porfim,ovértice3podeserrefletido
emqualquerumadas2posições,de
modoquehaja4.3.2=24simetrias
diferentes. Desse modo, o conjunto
desimetriaséinteiramentecomposto
porS4.
(b)Hásomente12simetriaspossíveis
do tetraedro (quando omitimos as reflexões), e podemos classificá-las de
formaexplícita.
Observequeestassãoprecisamenteas
permutaçõesparesdeS4.
Podemos concluir que x deve ser um
inteiro.
Parademonstrarque2néO(3n),basta
notarque|2n|≤|3n|paratodososinteirospositivosn.
Suponha, levando-se em conta a
contradição,que3nsejaO(2n).Então,
existe um número positivo M de formaque|3n|≤M|2n|paratodos,masfinitamentemuitos,inteirospositivosn.
Podemos excluir as barras de valores
absolutos, porque 2n e 3n são sempre
positivose,dessemodo,temos
paratodos,masfinitamentemuitos,n.
No entanto, os valores n tornam-se
cadavezmaiores,aopassoquencresce,excedendoqualquernúmeroespecífico.⇒⇐Portanto,3nnãoéO(2n).
Apendice-3.indd 48
Capítulo 6
1.
2.
3.
4.
AsomadeP(a)paratodoaÎSdeve
ser 1. Em S, há cinco números pares,
paraosquaisP(a) = x,ecinconúmerosímpares,paraosquais
P(a)=2x.Portanto,5(x)+5(2x)=1,
deformaque15x=1e,portantox= .
(a)63.(b)64.
P(A)=P(1)+P(4)+P(7)+P(9)= +
+ + =
(a)Há10!maneirasemqueascrianças
podemformarafila,etodassãoigualmente prováveis. Existe apenas uma
ordenação em que as crianças aparecememordemalfabética,pelonome,
portantoaprobabilidadeé1/10!.
(b) Há 5! . 5! maneiras em que as
criançaspodemformarafila,demodo
quetodasasmeninasprecedamtodos
osmeninos.Portanto,aprobabilidade
é5!.5!/10!=1/252.
(c)Aprimeirameninapodeestarnaposição1a6nalinha.Umavezqueaposiçãoparaaprimeirameninafordefinida,
existem5! .5!maneirasparaascriançasocuparemsuasposições,obtendo-se
umtotalde6 .5! .5!resultadosbemsucedidos.Portanto,aprobabilidadeé6
.5!.5!/10!=1/42.
(d) Há 2 . 5! . 5! maneiras em que as
criançaspodemseposicionar,deforma
quesealternemporgênero.Portanto,a
probabilidadeé2.5!.5!/10!=1/126.
(e) SejaB o caso em que os meninos
permanecememumblococontíguo,e
seja G o caso correspondente para as
meninas.BuscamosP( Ç ).Observeque
09/04/2010 19:14:19
Apêndices
A partir da parte (c), temos P(G) =
P(B) = 1/42. Para calcular P(B Ç G),
observequehá2.5!.5!maneirasem
queascriançaspoderiamseposicionar,
emquetodososmeninospermaneçam
juntosetodasasmeninaspermaneçam
juntas,deformaqueP(B ÇG)=2.5!
.5!/10!=1/126.
Portanto,
(a) Há maneiras de escolher a mão,
cada uma das quais é igualmente provável.
Háapenasumamaneiradeescolherascartas,
se todas as 13 forem espadas. Com isso, a
probabilidadeé1/ .
(b)Há maneirasdeescolherascartas,
deformaquetodassejampretas,portantoa
probabilidadeé / .
(c)SejaBocasoemquetodasascartas
sãopretaseR ocasoemquetodasascartas
sãovermelhas;buscamosP( Ç ).Podemos
reescreverissoassim
Apartirde(b),P(R)=P(B)= / eP(R Ç B)=0,vistoquenãohácomo
escolher as cartas de forma que elas
sejamtodaspretasetodasvermelhas.
Portanto,
,
(d) Seja A o caso em que uma (ou
mais)carta(s)seja(m)umás.Há
= maneirasdeescolherumamão
semás,deformaqueP( )= / .
Apendice-3.indd 49
6.
49
Issoéestimadoparaaproximadamente30%.
(e)Há52–13–4+1=36cartasem
ummaçoquenãosãonemcopasnem
ases.Portanto,aprobabilidadedetirar
13 cartas, das quais nenhuma seja ás
oucopa,éde / .
(a)Aúnicamaneiradetirar21éescolherumásjuntamentecomumacarta
defiguraou10.Há52´51maneiras
deescolherduascartas(emsequência)
deummaço.Destas,há2´4´16sequênciasemqueumadascartaséum
ás e a outra, um dez ou uma carta de
figura.Portanto,aprobabilidadeé(2 .
4 .16)/(52 .51)=32/663,ou,aproximadamente,4,8%.
(b)Das52´51=2.652maneirasde
tirar uma carta de figura, a seguinte
tabelaforneceonúmerodeformasde
tiraromontante16,oumaior,dependendodaprimeiracarta.
Primeiracarta
Escolhasparaa
2ªcarta
Total
2,3ou4
0
0
5
4(apenasases)
16
6
20(10oumaior)
80
7
24(9oumaior)
96
8
28(8oumaior)
112
9
32(7oumaior)
128
10oudefigura
36(6oumaior)
576
ás
40(5oumaior)
160
Númerototaldemaneiras:
1.168
Portanto,aprobabilidadedequeduas
cartastiradastotalizem16oumaiséde
1.168/2.652=292/663,ou,aproximadamente,44%.
(c) Seja A o caso em que a primeira
cartaéumás,esejaFocasoemque
asegundacartaéumacartadefigura.
Buscamos P(F|A). Isso é igual a P(F
09/04/2010 19:14:19
50
Matemática Discreta
ÇA)/P(A).Onumeradoréiguala(4.
12)/(52,51)eodenominadoréiguala
4/52.Portanto
7.
8.
9.
SejaFBocasoemqueaprimeiracarta
é preta e LR o caso em que a última
cartaévermelha.BuscamosP(LR|FB),
queéigualaP(LRÇFB)/P(FB).Onumerador é igual a (26 . 26)/(52 . 51)
eodenominadoréiguala26/52=½.
Portanto,
Osdoiscasos,FBeLR,nãosãoindependentes. Mostramos anteriormente
queP(FBÇLR)=(26.26)/(52.51)
=13/51,masP(FB).P(LR) = . = .
SejaAumcasoparaoespaçoamostral
(S, P).OscasosA e sãoindependentes
seesomenteseP(A)=0ouP(A)=1.
(alternativamente, o teorema pode
concluir“...seesomenteseP(A)=0
ouP( )=0”etc.).
Prova.(⇒)SuponhamosqueAe sejamindependentes.Então,P(A)P( )=
P(A Ç ),eestespodemseriguaisa0,
vistoqueAÇ =Ø.PortantoP(A)=
0ouP( )=0eestesejaequivalentea
P(A)=1.
(⇐) Suponha P(A) = 0 ou P( ) =
1.Emqualquercaso,P(A)P( )=0e
P(Ø)=P(A Ç )e,portantoA e são
independentes.
ParaoscasosR eC,temos
Portanto,R eCsãoindependentes.
ParaoscasosR eB,temos
10.
Portanto, R e B são independentes.
Domesmomodo,CeBsãoindependentes.
ParaoscasosReC,temos
Portanto,R eC nãosãoindependentes.
ParaoscasosReB,temos
Portanto,ReBnãosãoindependentes.
Domesmomodo,CeBnãosãoindependentes.
Análise alternativa: Em vez de
escolher os quadrados em sequência,
podemosescolhê-loscomoparem maneiras,todasasquaissãoigualmenteprováveis.
ParaoscasosR eC,temos
e
Apendice-3.indd 50
09/04/2010 19:14:20
Apêndices
51
ParaoscasosR eB, temos
e
11. Suponhamos que a moeda produza
CARAS com probabilidade p e COROAS comprobabilidade1–p.SejaA
ocasoemquetiramosCARASeCOROAS,esejaB oscasosemqueduas
jogadassãodiferentes.Calculamosda
seguintemaneira:
(c)AesperançadeYéamesmaquea
deX;ouseja,E(Y)= 95/13.
(d)AvariáveisaleatóriasX eYnãosão
independentes.Porexemplo,considereaprobabilidadedequeambossejam
iguaisa2.Temos
então
Prova.SabemosqueAÍBeP(A)≠0.
Portanto,P(B)≠0.Observeque
12.
com a última igualdade, porque A Ç
B = A, visto que A Í B. O resultado
agora segue-se pela multiplicação da
equaçãoexibidaporP(B).
Como
13.
,
,
14.
Apendice-3.indd 51
,
(e)Pelalinearidadedaesperança,E(X
+ Y)=E(X)+E(Y)= + = .
(f)AprobabilidadeX=Ypodesercalculadapor
P(X=2ÙY=2)+...+P(X=11Ù Y=11)
Calculamos cada adição da seguinte
maneira:
,
,
sucede-sequeX(c)=–1,2/0,2=–6.
(a)Há32cartascomvalorpar(quatro
cadaumade2,4,6,8,10,valete,rainhaerei).Portanto,P(Xépar)=32/52
=8/13.
(b) Cada categoria de carta aparece
comprobabilidade1/13,demodoque
ovaloresperadodeX seja
09/04/2010 19:14:21
52
Matemática Discreta
(g) Utilizamos a fórmula Var (X) =
E(X2)–E(X)2.
Var(X5)(poisosXisãoindependentes).
Capítulo 7
1.
2.
3.
15.
Aanáliseémaissimplesseescrevermos X = X1 + X2 + ... + X5, em que
Xj é a alteração no preço da ação do
j-ésimodia.
(a) Observe que E(X) = E(X1) + ... +
E(X5).CadaadiçãoédadaporE(Xj)=
(0,6)(2) + (0,1)(5) + (0,3)(–4) = 0,5.
Portanto,E(X)=5(0,5)=2,5= .Esperamosqueovalordaaçãosuba$2,50.
(b)Lembre-sedequeVar(X)= E(X2)
–E(X)2.UtilizandoofatodequeosXi
são independentes, calculamos da seguintemaneira:
4.
5.
6.
,
,
,
,
,
,
,
,
,
,
Alternativamente, poderíamos usar o
fatodequeVar(X)=Var(X1)+...+
Apendice-3.indd 52
7.
q=4er =3,portanto23div5=4e23
mod5=3.
Prova. Suponha b|a. Então há um
inteiroq,demodoquea = qb.Portanto,podemosescrevera = qb+0,
então, pela definição de div, temos
q = adivb.Comoq = ,segue-seo
resultado.
Prova. Sabemos que a, b são inteiros
positivoscoma ≥2ea|(b!+1).Suponha,levando-seemcontaacontradição,
quea ≤ be,dessemodo,a|b!.Comoa
dividetantob!+1comob!,dividesua
diferença(b!+1)–b!=1,e,portanto,a
= 1;masa ≥2.⇒⇐Logo,a > b.
(⇒)Suponhamosmdc(p, q)=1,mas,
levando-se em conta a contradição, p
= q.Então,mdc(p, q)=p = q >1.⇒⇐
Portanto,p ≠q.
(⇐)Suponhap ≠q,maslevandoseemcontaacontradição,mdc(p, q)
=d>1.Então,d|p ed|q.Comod >1,
issoépossívelsomentesed = ped
= q,deemquep = q.⇒⇐Portanto,
mdc(p,q)=1.
x =4ey =–7.Outrasrespostassãopossíveis,contantoque100x+57y=1.
Apartirdoproblemaanterior,sabemos
que100´4+57´(–7)=1,portanto
–7´57≡1(mod100).Como–7≡93,
(mod100),constatamosqueorecíprocode57é93.Verificando:57´93=
5.301≡1(mod100),então57⊗93=1
emZ100.
Prova.Provamosquemdc(Fn, Fn+1)=1
porinduçãoemn.
Ocasobásico,n = 1,ésimplespor
quemdc(F1,F2)=mdc(1,2)=1.
09/04/2010 19:14:21
Apêndices
Suponhamos(hipótesedaindução)
queFkeFk+1sejamrelativamenteprimos; devemos provar que Fk+1 e Fk+2
tambémsãorelativamenteprimos.
Suponhamos,levando-seemconta
a contradição, que mdc(Fk+1, Fk+2) =
d > 1. Então, d|Fk+1 e d|Fk+2. Observe
queFk+2=Fk+Fk+1,podeserreescrito
daseguinteforma:
10.
11.
Fk=Fk+2–Fk+1
Comoddivideambosostermosàdireita,dFk.Portanto,d édivisorcomum
deFk eFk+1.⇒⇐
Logo,Fk+1eFk+2sãorelativamente
primos.
Alternativamente, podemos completaraprovadamaneiracomosegue.
Como Fk e Fk+1 são relativamente
primos,existeminteirosa eb,deformaqueaFk +bFk+1≡1.Aosubstituir
Fk=Fk+2–Fk+1,obtemos:
12.
13.
8.
9.
Portanto,Fk+1eFk+2sãorelativamente
primos,peloCorolário35.9.
Sejam n, p fornecidos no problema e
sejad=mdc(n,n + p).Comod éum
divisorcomumden + pen,sabemos
qued|n + p – n;ouseja,d|p.Então,d=
1oud = p.Aúltimaformaéimpossível,
porquesabemosquepnãodividen.
Comopéprimo,asomadosdivisores
positivos de pn é a série geométrica
(finita)
1+p +p2+...+pn
queésimplificadapara
Apendice-3.indd 53
14.
53
(a)20,(b)90,(c)95e(d)85.
Prova.ConfiamosnoTeorema36.14,
sobreofatodequeaÎZnéinvertível
se e somente se a e n forem relativamenteprimos.
(⇒)Suponhamosquensejaprimo.
Se1≤a≤n–1,entãoaennãopodem ter nenhum fator comum e, portanto,sãorelativamenteprimos.Desse
modo,aéinvertívelemZn.
(⇐) Suponhamos que todos os
elementos não nulos de Zn sejam invertíveis,mas,levando-seemcontaa
contradição, n não seja primo. Então,
existeuminteiroa,demodoque1<
a<nea|n.Issosignificaque(a,n)=
a,portantoanãoéinvertívele,contudo,éumelementonãonulodeZn.⇒⇐
Portanto,néprimo.
Ascongruênciassãosatisfeitasportodososinteirosx,demodoquex º981
(mod3264).
Prova.(⇒)Issoétrivial.
(⇐) Suponha que mdc(a, b) =
mmc(a, b) = d. Isso implica que d|a,
a|d,b|ded|b.PeloProblema3,noAutoteste do Capítulo 4, temos a = d e
b = d,e,portanto,a = b.
(a) Com n = 1010 = 210510, constatamosquen tem11´11=121divisorespositivos.
(b)Dosninteirosentre1en,existem
n/2quecompartilhamdeumfatorde2
comnen/5quecompartilhamdeum
fatorde5comn.Destes,contamosduplamente os múltiplos de 2 e 5, e há
n/10destes.Portanto,
09/04/2010 19:14:21
54
15.
Matemática Discreta
(⇐)Seaéímpar,entãoa –1épar,
então2|(a–1).Portanto, =a´ ,
ecomo éuminteiro,a| .
(⇒)Seanãoéímpar(ouseja,a é
par),entãoa–1éímpar.Comoaépar,
a = 2b´potênciasdeprimosímpares.
Então,sefatorarmos = ´(a–1)
emprimos,notamosque
Prova. Seja n um inteiro positivo. A
fatoraçãodenemprimosresultaem:
emqueospj sãoprimosdistintoseos
ajsãonúmerosnaturais.Onúmerode
divisoresden é
e,portanto,a nãopodedividir .
D =(a1+1)(a2+1)...(at+1)
16.
17.
(VerExercício38.12)
Agora,vemosqueDéímpar,see
somentese(aj+1)forímparparatodososj,seesomenteseaj forparpara
todososj e, seesomentesen forum
quadradoperfeito.
Prova.Sejama, b,cinteirospositivos
e suponha que a|bc e mdc(a, b) = 1.
Fatore a, b, c em primos da seguinte
maneira:
Como a|bc, temos xj ≤ yj + zj. Como
mdc(a, b)=1,temosxj >0→yj=0→
xj ≤zj.Obviamente,sexj=0,entãoxj
≤zj.Portanto,xj ≤zjparatodososje,
dessemodo,a|c.
Observequeasomadea inteirosconsecutivoscomeçandocomxé
Otermoaxéclaramentedivisívelpor
a,entãoasomaédivisívelpora,see
somentesea| .
éuminteiro.
Noteque =
Apendice-3.indd 54
Capítulo 8
1.
(a)3*4=
=
=5
(b) A operação * é fechada para números reais. Se x e y são números
reais, então x2 + y2 é um número real
não negativo, e, desse modo, x * y =
éumnúmeroreal.
(c)Aoperaçãoécomutativaporque
=
=y*x
x * y=
(d)Aoperação*éassociativa,pois
e,pormeiodeumaanálisesimilar,(x
.Portanto,x*
* y)*z=
(y * z)=(x * y)*z.
(e) A operação * não possui um elemento identidade. Suponhamos, levando-seemcontaacontradição,que
e sejaumelementoidentidade.Então,
(–1)*e=–1,mas
e,portanto(–1)*e≠–1.⇒⇐
09/04/2010 19:14:22
Apêndices
2.
3.
4.
Apendice-3.indd 55
={1,3,5,7,9,11,13,15,17,19,21,
23,25,27,29,31}.Emoutraspalavras,
éoconjuntodeinteirosímparesentre0e32.Dessemodo,φ(32)=16.
(a)H={1,4,11,14}
(b)K={1,4}
Suponhamos que (G, *) seja abeliano
equeHeK sejamdefinidoscomona
afirmaçãodoproblema.
(a)PrecisamosprovarqueHéfechado
sob*einversas.
Suponhaquea, b ÎH.Então,a * a
= b * b = e.Afimdedemonstrarque
a * b ÎH,observamosque(a * b) (a
* b)=a * a * b * b = e * e = e(válido
porque*écomutativoporhipótese).
Suponhamos que a Î H. Observe
quea * a=e = a * a–1,apartirdoque
constatamosquea = a–1e,dessemodo,
a –1ÎH.
Portanto,(H,*)éumsubgrupode
(G,*).
(b)PrecisamosprovarqueKéfechado
sob*einversas.
Suponhamos que a, b Î K. Então,
háx, yÎG,demodoquea = x * xe
b = y * y.Observequea * b=(x * x)
* (y * y)=(x * y)(x * y)(emquenos
valemosdofatodeque*écomutativo).Portanto,sabemosquea * b=z *
zparaalgumzÎG(asaber,z = x * y)
e,assim,a * bÎK.
SuponhamosqueaÎH.Então,a =
x * xparaalgumxÎG.Sejab = x–1*
x–1;evidentemente,bÎK peladefiniçãodeK.Notequea * b=x * x * x–1
*x–1=ee,portanto,b = a–1.Portanto,
b–1ÎK.
Dessemodo,(K,*)éumsubgrupode
(G,*).
Aseguir,apresentamososcontraexemplosparaosgruposnãoabelianos.
55
(a)ParademonstrarqueHnãoénecessariamenteumsubgrupoquando(G,*)
nãoéabeliano,seja(G,*)=S4,d).
Observeque(1,2)3(2,3)estãoem
Hporque(1,2)d(1,2)=(2,3)d(2,3)
=ι.Noentanto,considerep=(1,2) d
(2,3)=(1,2,3).Notequep d p=(1,
2,3)d(1,2,3)=(1,2,3)≠ι.Portanto,
p ÏK.Portanto,Knãoéfechadosob
aoperaçãoοdogrupoe,dessemodo,
nãorepresentaumsubgrupo.
(b)ParademonstrarqueKnãoénecessariamenteumsubgrupoquando(G,*)
nãoéabeliano,seja(G.*)=(A4,d),em
queA4éoconjuntodetodasaspermutaçõesparesemS4.Osdozeelementos
deA4sãorelacionadosaseguir.
Formaríamos o conjunto K ao computarp d pparacadap ÎA4.Quando
fazemosisso,chegamosaosseguintes
resultados.
5.
Consequentemente,semcontarasduplicatas,Ktemnoveelementos.Alegamosque(K, d)nãopodeserumsubgrupo de (A4, d) pois, caso contrário,
deacordocomoteoremadeLagrange
(Teorema 41.4), teríamos 9|12. ⇒⇐
Portanto,Knãoconstituiumsubgrupo.
SabemosqueG deveterumelemento
identidade,oqualpodemosdenominar
e;sejama ebosoutrosdoiselementos.
Comoeéaidentidade,devemoster
e * e = e, a * e = e * a = a,eb * e =
e * b = b.
Em seguida, trabalhamos em cima
dovalordea * b.
09/04/2010 19:14:22
56
Matemática Discreta
Existemapenastrêspossibilidades:e,
a e b. Demonstramos que a * b deve
serigualae,rejeitandoasoutrasduas
possibilidades.
Se a * b = b, então a operação à
direitaporb–1fornecea * b * b–1= b *
b–1⇒a = e, oqueéfalso.Damesma
maneira,a * b= alevaab = e,oque
tambéméfalso.Portanto,a * b = e.
Pelaanálisesimilar,b * a = e.
Consideramos agora a * a; deveria
sere, a oub.Sea * a=a,entãoaoperaçãopora–1forneceriaa = e,umacontradição.Sea * a = e, entãoaoperação
emambososladosporbresultaem
7.
ecomoH eKsãosubgrupos,h1*h2Î
Hek1,k2ÎK.Portanto,x * y ÎH *K.
ParademonstrarqueH eKéfechadosobinversas,sejaxÎH * K.Então,
x = h * kparaalgumh ÎH ek ÎK.
Observeque
outracontradição.Portanto,a * a = b.
Damesmamaneira,b * b = a.
Portanto, produzimos a tabela de
operações*.
e
e
e
a
a
b
b
a
a
b
e
b
b
e
a
*
6.
x–1=(h*k)–1=k–1*h–1=h–1*k–1
Agoraéfácilverificarsee ↦ 0,a ↦
1eb↦2éumisomorfismode(G,*)
para(Z3,⊗).
Considere as potências de 2 em ( ,
⊗):
8.
Portanto, a seguinte função f :
Z12éumisomorfismo:
Apendice-3.indd 56
⇒
(a)H⊕K={0,5,10,15,...,95}
(b)Prova.Suponhamosque(G,*)seja
umgrupoabelianoeH eK sejamsubgrupos.ParaprovarqueH * K também
é um subgrupo, devemos demonstrar
queH * K éfechadosob*einversas.
ParademonstrarqueH * K éfechadosob*,sejax, y ÎH * K.Issosignificaqueexistemh1,h2ÎHek1,k2ÎK,
demodoquex =h1*k1ey = h2*k2.
Observeque
ComoH eKsãosubgrupos,observamos que h–1 Î H e k–1 Î K. Portanto,
x–1ÎH * K.
Logo,H *Kéumsubgrupode(G,
*).
(c)Seja(G,*)=(S3, d)esejaH={ι,
(1,2)}eK ={ι,(1,3)}.NotequeH e
K sãosubgruposde(S3,d).
Então,oselementosdeH * Ksãoι
d ι=ι, ι d (1,3)=(1,3),(1,2)d ι=(1,
2)e(1,2)d(1,3)=(1,3,2).
Observeque,embora(1,3,2)ÎH d
K,suainversa(1,3,2)–1=(1,2,3)não
estáemH d K.Portanto,H d K nãoé
umsubgrupode(S3,d).
Oselementosde são{1,2,4,7,8,
11, 13, 14}. Calculamos g4 para cada
umdeles:
09/04/2010 19:14:23
Apêndices
g
g4
g4 (mod 15)
1
1
1
2
16
1
4
256
1
7
2.401
1
8
4.096
1
11
14.641
1
13
28.561
1
14
38.416
1
r eduzindo o módulo 9432 após cada
vezqueseelevaaoquadrado.
Suponhamos, levando-se em conta a
contradição, que ( , ⊗) seja cíclico.Então,háumelementogÎ ,de
modoqueaspotênciasdeg geremtodososelementosem .Noentanto,
comog4=1,asequência
1
9.
10.
11.
g
g2
g3
g4
g5
...
deveserepetirapósquatro(oupoucos)
passose,portanto,nãopodeincluirtodososoitoelementosde .⇒⇐Portanto,( ,⊗)nãoécíclico.
Como89éprimo,opequenoteorema
deFermat(Teorema42.1)declaraque
289 mod 89 = 2. Como 290 = 289 ´ 2,
constatamosque290mod89=4.
Sen fosseprimo,entãoopequenoteorema de Fermat (Teorema 42.1) implicaque2n≡2(modn),massabemos
que2n≢2(modn).⇒⇐Portanto,né
composto.
PeloteoremadeEuler(Teorema42.6),
seaensãorelativamenteprimos,aφ(n)
≡1(modn).Como2e38168467são
claramente relativamente primos, 2φ(n)
=238155320≡1(modn).Entretanto,somossolicitadosaestimar2φ(n)+1=2φ(n)
´2módulone,portanto,
57
13.
14.
a =874
→763876
→a2=9236
→85303696
→a4=1077
→1159929
→a8=9103
→82864609
→a16=5137
→26388769
→a32=4668
→21790224
→a64=9427
→88868329
→a128=36
→1296
256
→a =1296
quadrado
mod9432
quadrado
mod9432
quadrado
mod9432
quadrado
mod9432
quadrado
mod9432
quadrado
mod9432
quadrado
mod9432
quadrado
mod9432
Comop=883éprimoep≡3(mod
4), podemos encontrar as raízes quadradasde71utilizandoaProposição
44.3:
e,dessemodo,asraízesquadradasde
71são707e–707=176.
Seja p = 499, q = 883 e n = pq =
440617.Desejamosencontrartodosos
xÎZn,demodoquex ⊗x=1.
EmZp,temosx≡±1(modp)e,da
mesmamaneira,emZq.Issooriginaas
seguintescongruências.
238155321mod38168467=2
12.
Apendice-3.indd 57
874256mod9432=1296.
O cálculo pode ser realizado elevando 874 dez vezes ao quadrado,
09/04/2010 19:14:23
58
15.
Matemática Discreta
Estaspodemserresolvidasutilizando-seométododoteoremadorestochinês, mas observe que o primeiro fornecex ≡1(modn)eoúltimofornece
x ≡ –1 ≡ n – 1 (mod n).Além disso,
as soluções para o segundo e terceiro
são simplesmente negativas umas em
relaçãoàsoutras.
Aresoluçãodex≡1(modp)ex
≡–1(modq)resultaemx ≡429139
(mod 440617). Portanto, as quatro
raízes quadradas de 1 em Zn são 1,
–1, = 440616, 429139 e –429139 =
11478.
Recebemosquatroraízesquadradasde
1010120emZn(comn=5460947):s,
–s, t e –t.Ocálculodomdc(s + t, n)(ou
mdc(s, –t, n))revelaráumfatorprimo
den.
18.
19.
Utilizandooexpoentededecriptaçãod
=345689quedescobrimosnoProblema17,encontramosque
Onúmero190625representaapalavraSPY.
Asoluçãodopardeequações
para p e q fornece os fatores 5323 e
7537.
Capítulo 9
1.
Umafigurapossível:
2
2.
Observe que 4547 é primo e
5460947/4547=1201,portanto
5460947=4547´1201
16.
3.
Seja m uma mensagem de texto sem
formatação. Constatamos que m2 =
496410emZ713809.Descobrimosqueas
quatroraízesquadradasdem2emZn,e
elassão
160907 356083 357726 552902
17.
Apendice-3.indd 58
Destas,somenteaprimeiracorrespondeaumapalavra,eapalavraéPIG.
Comon = pq = 453899=541´839,
constatamosqueφ(n)=(p – 1)(q–1)=
540´838=452520.Então,d ée–1em
Z452520,oquerepresenta345689.
4.
5.
1
3
4
5
Não existe nenhum gráfico assim. Se
existisseumgráficoGdessetipo,então a soma dos graus dos vértices seria43,umnúmeroímpar,masasoma
deveserigualaduasvezesonúmero
dearestas,umnúmeropar.⇒⇐
Oferecemosduassoluções.
Primeira solução. EntreWi eWjhá
10´10=100arestas.Comohá =
45maneirasdeselecionarosi ej,há
4.500arestasemG.
Segunda solução. Cada vértice é
adjacenteaos90outros(os9´10em
outrosWjs).Portanto,asomadosgraus
dosvérticesemGé9.000,oquerepresentaduasvezesonúmerodearestas.
Portanto,há4500arestas.
(a)210. (b)215.
Um caminho de comprimento 5 de a
parabédaforma
09/04/2010 19:14:23
Apêndices
a ~ x1~ x2~ x3~ x4~b
6.
em que podemos escolher os xi sem
repetição dentre os vértices em K10,
excetoaeb.Há8.7.6.5=1.680
possíveiscaminhos.
(a)f (0)=0,g(0)=1,f (1)=1eg(1)=0
(b) Considere (a, b) caminhos com
a≠b.Partindodea,opróximovértice
queescolhemospoderiaounãoserb.
Se o próximo vértice for b, então há
g(k–1)maneirasdecompletarocaminho. Se o próximo vértice não for
b(eexistem8possíveismaneirasem
queissopoderiaacontecer),entãohá
f(k – 1) maneiras de completar o caminho.Portanto,
f (k)=8f (k–1)+g(k–1)
8.
9.
(c)Iniciandoapartirdea,há9escolhas para o próximo vértice em um
caminho (a, a), e existem f (k – 1)
maneiras de completar o caminho.
Portanto,
g(k) = 9f (k –1)
(d) Utilizando essas informações, podemoscriarumatabeladevalorespara
f(k)eg(k).
7.
Apendice-3.indd 59
k
f(k)
g(k)
0
0
1
1
1
0
2
8
9
3
73
72
4
656
657
5
5.905
5.904
Portanto,há5.905caminhosdecomprimento5deaatéb(coma ≠ b)emK10.
Suponhamos, levando-se em conta
a contradição, que G não é conexo.
Então, G tem dois (ou mais) compo-
10.
59
nentes. Seja A os vértices no menor
componentedeG.ComoAéomenor
componentedeG,nãoapresentamais
quen/2vértices.EscolhaxÎA.Observequexéadjacentesomenteaoutros
vértices em A (e não a si próprio) e,
dessamaneira,d(x) < n/2,contradizendoahipótesedequeδ(G)≥n/2.⇒⇐
Portanto,Géconexo.
Onúmerodeciclos3é =10.
Há4!(4.2)=3maneirasdiferentes
decriarumcírculosobrequatrovértices,demodoqueonúmerodeciclos4
seja .3=15.
Onúmerodeciclos5em5vértices
é5!/(5.2)=12.
Portanto,onúmerototaldeciclosé
10+15+12=37.
SejaG umgrafoconexocomnvértices.Suponhamosqueograumédiode
umvértice sejamenorque2.Observeque
O número de arestas em G é, portanto, n <n.ComoG éconexo,Gtem,
pelo menos, n – 1 arestas e, como G
tem menos que n arestas, deve ser o
casoemqueGtemexatamenten–1
arestas.Portanto,peloTeorema49.12,
G éumaárvore.
Asduasárvoresaseguirnãosãoisomórficas,masosgrausdeseusvértices
sãoosmesmos.
1
2
3
4
5
3
2
4
5
6
1
6
09/04/2010 19:14:24
60
11.
12.
Matemática Discreta
Um grafo não-conexo em 10 vértices
podeteraté36arestas,masnãomais
queisso.Eisoporquê:
Se G possui 10 vértices e é não-conexo,entãoGpossuidois(oumais)
componentes. Seja A os vértices em
umcomponenteeBosvérticesrestantes. Se adicionarmos duas arestas a A
ouB,nãocriaremosumgrafoconexo
(vistoquenãoháarestasentreAeB).
Portanto, supomos que G[A] e G[B]
sãografoscompletos.
Suponhamos que |A| = a em que
1 ≤ a ≤ 9. Então, G tem +
arestas. Se avaliarmos essa expressão
comváriosvaloresde a=1,2,...,9,
encontramos o maior valor quando
a =1oua =9;nessecaso,descobrimos
queGtem36arestas.
Aseguir,háumapartiçãodeE(K8)em
quatrocaminhoshamiltonianos.
1~8~2~7~3~6~4~5
2~1~3~8~4~7~5~6
3~2~4~1~5~8~6~7
4~3~5~2~6~1~7~8
13.
Apendice-3.indd 60
Cadaumadas =28arestasdeK8representaumdosquatrocaminhos.
Noentanto,nenhumapartiçãodesse tipo de K9 é possível. O grafo K9
contém =36arestas,eumcaminho
hamiltoniano de K9 contém 8 arestas.
Se uma partição de K9 estivesse dentrodepcaminhoshamiltonianospossíveis, teríamos 8p = 36, mas 36 não
é divisível por 8. Portanto, nenhuma
partiçãodessetipoépossível.
Existência. Sabemos que P e R possuem vértices em comum, visto que
a estáemambososcaminhos.Sejax
o último vértice em P (à medida que
percorremosdeaatéb)queestátambémemR. Observequexétambémo
últimovérticeemRàmedidaquenos
transpomosdeaac(sehouvesseum
vérticeapósxemRqueestivessetambém em P – por exemplo, y –, então
haveriadoiscaminhos(x, y)diferentes
emT).
c
a
x
b
Dessemodo,osegmento(b, x)dePdo
segmento(c, x)deQapresentamapenas x em comum. Se concatenarmos
esses segmentos, temos um caminho
(b, c) S (visto que os dois segmentos
nãopossuemvérticesemcomum,excetox).Comonãoháumesomenteum
caminho (b, c) em T, a saber R, deve
ser o caso em que R = S. Como x é
umvérticedeS,deveserumvérticede
R,e,portanto,x estáemtodosostrês
pontos:P, Q eR.
Unicidade: Suponhamos que P, Q
eR apresentemdois(oumais)vértices
emcomum;vamosdenominá-losx ey.
Semaperdadageneralidade,àmedida
quenostranspomosPdea até b,encontramosx antesdey.
Em T, existem um caminho (a, x)
únicoeumcaminho(x, y)único,eestesdevemserossegmentoscorrespondentesdeP.Alémdisso,existeumcaminho(a, y)único,etalcaminhodeve
conterx.
ComoRtambémcontéma,x,ey,
ossegmentos(a, x)e(x, y)deRdevem
ser idênticos aos de P, e x deve estar
entrea eyemR.Vejaafigura.
09/04/2010 19:14:24
Apêndices
c
a
y
x
b
15.
14.
Apendice-3.indd 61
Agora, observamos que o segmento
(b, y)dePnãocontémxeosegmento(y,c)deRnãocontémx.Portanto,
há um passeio (b, c) que não contém
x. Então, há um caminho (b, c) mais
curto que não contém x, e este é, necessariamente,umcaminho(b,c),que
deveestaremR.Portanto,R nãocontémx.⇒⇐Portanto,oscaminhosP,Q
eRapresentamexatamenteumvértice
comumatodosostrês.
(⇒)SuponhamosqueGsejaeuleriano.
SejaAÈBumapartiçãodeV(G)em
conjuntosnãovaziosdisjuntos.ComG
éeuleriano,deveserconexo,e,desse
modo,devehaveraomenosumaaresta
deAaB.
Se considerarmos qualquer tour
euleriano W, o número de vezes em
queWlevaumaarestadeAatéBdeve
ser igual ao número de vezes em que
W leva uma aresta de B até A (caso
contrário, o tour não começaria nem
terminaria no mesmo vértice). Desse
modo,onúmerodearestasentreAeB
deveserpar.
(⇐)SuponhamosqueGéumgrafo,
demodoqueparacadapartiçãoAÈB
= V(G), o número de arestas entre A e
B seja par, mas não zero. Observe que
isso implica que G é conexo, pelo fato
deque,casocontrário,assumiríamosA
comooconjuntodevérticesdeumcomponenteGeB=V(G)–A;nessecaso,
nãohaverianenhumaarestaentreAeB.
16.
61
Seja ʋ qualquer vértice de G. Seja
A={ʋ}eB=V(G) – A.NotequeonúmerodearestasdeAaBéexatamente
d(ʋ) e, portanto, d(ʋ) é par. Como G
éconexoetodososvérticespossuem
graupar,Géeuleriano.
Nãoédifícilencontrarumacoloração
emtrêsapropriadadeG(porexemplo,
colorirosvérticesàmaneiradeumtabuleirodexadrez,excetocomousode
uma terceira cor para o vértice mais
à direita na última fileira). Portanto,
χ(G)≤3.TambémnãoédifícilencontrarumcicloímparemG;dessemodo,
Gnãoébipartido,entãoχ(G)>2.Portanto,χ(G)>2.Portanto,χ(G)=3.
Paran≥3,temos
Prova.Senforímpar,entãoocicloem
Wncontémumnúmeropardevértices.
Estes podem ser coloridos alternadamenteutilizandoduascores,deixando
umaterceiracorparaovérticeadicional; portanto, χ(Wn) ≤ 3. Pelo menos
três cores são necessárias porque Wn
contém um grafo completo em três
vértices (quaisquer dois vértices consecutivos no ciclo mais o vértice adicional).
Senforpar,entãoocicloWncontém um número ímpar de vértices.
Esse ciclo ímpar pode ser colorido
comtrêscores,deixandoumaterceira cor para o vértice adicional; portanto, χ(Wn) ≤ 4. Alegamos que Wn
não pode ser colorido com menos
do que quatro cores. Suponhamos,
levando-se em conta a contradição,
que uma coloração desse tipo seja
possível. O vértice adicional (que é
09/04/2010 19:14:24
62
17.
18.
Apendice-3.indd 62
Matemática Discreta
adjacente a todos os outros) recebe
a mesma cor. Portanto, nenhum dos
outrosvérticespodeutilizaressacor,
deixandonomáximoduascorespara
osvérticesdociclo.Comoesseciclo
apresentaumnúmeroímpardevértices,nãopodesercoloridocomapenasduascores.⇒⇐Portanto,χ(Wn)
nãoémenorque4.
SuponhamosqueosvérticesdeCnsejamnomeados,emordem,1,2,3,...,n.
Observequeosvértices1,3,5,...,
n/2formemumcliqueem e,portanto,χ ≥n/2.
No caso em que n é par, podemos
colorirCnadequadamentecomn/2cores,atribuindoacor1aosvértices1e
2,cor2aosvértices3e4eassimpor
diante.Porconseguinte,paranpar,χ
=n/2.
Nocasoemquenéímpar,oesquemadecoresdescritoacimautilizará(n
+1)/2cores(ovérticennãoserápareadocomoutrovérticedamesmacor).
Portanto,senéímpar,χ ≤(n+1)/2.
É possível que Cn (para n ímpar)
seja colorido com menos cores? Se
issofossepossível,haveria(nomáximo)(n–1)/2coresdisponíveise,portanto,trêsvérticesdistintosreceberiam
amesmacor.Comon≥4,trêsvértices
deCn,nãopodemreceberamesmacor
em .Dessemodo,χ(G)>(n –1)/2.
Concluindo,paran ≥4,
Issopodeserrepresentadomaisconcisamentecomo[fórmula]= .
(a)(⇒)Suponhamosqueχ(G)≥k.Isso
implicaqueGpossui,pelomenos,uma
19.
coloraçãokapropriadae,dessemodo,
χ(G, k)>0.
(⇐)Suponhamosqueχ(G, k)>0.
Isso implica que G tem, pelo menos,
uma coloração k apropriada e, desse
modo,G podesercoloridopork.Portanto,χ(G)≥k.
(b)UtilizamosoEsquemadeprova25.
Aprovaéporinduçãoemn.Ocaso
básicoéquandon=1–ouseja,aárvoreapresentaapenasumvértice.Nesse
caso,sehouverkcoresdisponíveis,há
kmaneirasdiferentesdecolorirovérticeinteiro.Porconseguinte,χ(G,k)=
k = k(k–1)0,conformenecessário.
Suponhamos(hipótesedaindução)
queoresultadotenhasidoprovadopara
todos os três com ℓ vértices. Seja T
umaárvorecomn = ℓ +1vértices.Devemosprovarqueℓ(T, k)=k(k – 1)n–1
=k(k – 1)ℓ.
Seja ʋ uma folha de T e seja T′ =
T –ʋ. ObservequeT′ éumaárvoreem
ℓ vértices.Portanto,porindução,χ(T′,
k)=k(k –1)ℓ–1.
Contamos agora as colorações k
apropriadas de T. Observe que, dada
umacoloraçãoapropriadadeT,seignorarmosovérticeʋ,temosumacoloraçãoapropriadadeT′ .Existemχ(T′ ,
k)maneirasdecolorirT′ comk apropriadamente.
Para cada coloração desse tipo, há
k –1maneirasdecolorirʋ,vistoque
ʋ pode ser qualquer cor, exceto a cor
atribuídaparaseuvizinhodecor.
Com isso, χ(T, k) = χ(T′, k) ´
(k –1)=k(k –1)ℓ–1(k –1)=k(k – 1)ℓ,
conformenecessário.
O seguinte desenho demonstra que o
grafoéplano.
09/04/2010 19:14:25
Apêndices
1
= a+35arestas.PeloCorolário52.5,
constatamosque
3
6
2
5
20.
o que é simplificado para 11 ≤ a e,
portanto,a≥22.
4
Ografo contémumasubdivisãode
K3,3, conforme ilustrado no seguinte
diagrama.
1
2
3
Capítulo 10
1.
21.
Apendice-3.indd 63
5
(a)AseguintefiguraforneceodiagramadeHassedeP.
16
7
4
63
6
Observeque{1,2,3}e{4,5,6}formamasduaspartesdografobipartido
completo K3,3. Todas as arestas desse
K3,3estãopresentesem ,excetosea
arestade3a4apareçanaformadocaminhodedoispassos3~7~4.(Afim
deverificarquetodososgrausmostrados pertençam a , as arestas de C7
sãomostradascomolinhascoloridase
interrompidas).
Como contém uma subdivisão
deK3,3comoumsubgrafo,énãoplano(veroTeorema52.9).
O grafo tem n = 8 vértices e
m = –8=20arestas.Se fosseplano,teríamosm ≤3n–6(veroCorolário
52.5).Noentanto,3n–6=3´8–6=
18e20≮18.Portanto, énãoplano.
Deformaalternativa,nãoédifícildemonstrarqueK3,3éumsubgrafode .
Suponhamos que haja a vértices de
grau 5. Sabemos que existem a + 10
vérticesnessegrafoe(5a+7´10)/2
8
12
18
20
4
6
9
10
2
3
5
7
15
11
14
13
17
19
1
2.
(b)AmaiorcadeiaemPé{1,2,3,4,
8,16}
(c)AmaioranticadeiaemPé
{11,12,13,14,15,16,17,18,19,20}
(d)Oconjuntodeelementosmáximos
dePé
{11,12,13,14,15,16,17,18,19,20}
(e)Oconjuntodeelementosmínimos
deP é{1}.
(f)Oconjuntodeelementosmáximos
deP éØ.
(g)Oconjuntodeelementosmínimos
dePé{1}.
Suponhamos, levando-se em conta a
contradição, que C Ç A contém dois
elementosdistintosxey.Comox, y Î
C,sabemosquex<youy <x;ouseja,
x e y são comparáveis. No entanto,
comox, y ÎA,sabemosquex eysão
incomparáveis. ⇒⇐ Portanto, C Ç A
não pode conter dois (ou mais) elementos,e,dessemodo,|C ÇA|≤1.
09/04/2010 19:14:25
64
3.
4.
5.
Apendice-3.indd 64
Matemática Discreta
SejaA umaanticadeiadeP.Sabemos
(a partir do Problema 2) que A pode
ter,nomáximo,umelementoemC1e,
nomáximo,umelementoemC2.Portanto,Apodeternomáximodoiselementos, e, então, o tamanho máximo
de uma anticadeia de P não pode ser
maiorque2.
(⇒) Suponhamos que P = (X, ≤) seja
umaanticadeia.SejaxÎX.Comonão
existe nenhum elemento y, de modo
quey < x,constatamosquexémínimo.Damesmamaneira,x émáximo.
Portanto,todososelementosdeXsão
máximosemínimos.
(⇐)Suponhamosquetodoelemento de X seja máximo e mínimo.Alegamos que P é uma anticadeia. Caso
contrário,haveriaelementosx ≠ yem
Xcomx < y.Porém,então,x nãoémáximoeynãoémínimo.⇒⇐Portanto,
P éumaanticadeia.
(a) Seja P = (X, ≤) uma cadeia finita.
Pelo Teorema 55.4, podemos supor
queX={1,2,...,n}e≤representamenorqueouigualacomum.Parajentre
1en,sejaAj ={j}.ComoosAjcontêm
apenas um elemento, são anticadeias.
ObservequeX=A1È ...ÈAnesex Î
Ai ey ÎAjcomi < j, então,devemos
obterx < y (defato,x = i ey = j).Portanto,P éumaordemfraca.
SejaP =(X,≤)umaanticadeia.Então,simplesmente,oatodepermitirque
A1=X forneceapartiçãonecessária.
(b) Seja P = (X, ≤) um conjunto PO
finito e seja Q o conjunto PO de três
elementosilustradonafiguraparaesse
problema.
(⇒) Suponhamos que P seja uma
ordemfraca,mas,levando-seemconta
acontradição,contémQcomoumcon-
juntoPO.ComoPéumaordemfraca,
podemosdividirXemanticadeiasX =
A1È...ÈAh,demodoqueparatodos
osxÎAi eyÎAj,sei < j,entãox < y.
Considere agora elementos a, b, c de
Q.Comoa < b,devemosobtera ÎAi
e b Î Aj, em que i < j. Suponhamos
quecÎAk.Observeque,comoi < j,
devemosobterk < jouk < i.Sek <
j, teríamosc < b,esek > i,teríamos
c > a;porémc éincomparáveltantoa
a comoab.⇒⇐Portanto,Qnãoéum
subconjuntoPOdeP.
(⇐) Suponhamos que P seja um
conjunto PO finito que não contém Q
como subconjunto PO. Seja A1 o conjuntodetodososelementosmínimosde
P.SejaA2oconjuntodetodososelementosmínimosdeP – A1(ouseja,o
conjunto PO formado pela eliminação
dos elementos de A1 de P). Seja A3 o
conjunto de todos os elementos mínimosemP – A1–A2.Continuamosdesse
modo,escolhendoA1comooconjunto
de todos os elementos mínimos de P
– A1–A2–...–At–1atéquenãohaja
maisnenhumelementorestante.ObservequecadaAj éumaanticadeia(visto
queéoconjuntodeelementosmínimos
dealgumsubconjuntoPOdeP)eosAj
dividemX.Restamostrarque,sexÎAi
ey ÎAjei < j,entãox < y.
Suponhamos, levando-se em contaacontradição,quex ≮y. Noteque
x é um elemento mínimo do conjuntoPOP – A1–...–Ai–1,e,portanto,
nãopodemosterx > y.Portanto,x ey
sãoincomparáveis.Alémdisso,y não
éumelementomínimodeP – A1–...
–Ai–1(porquey ÎAj ej > i),e,dessa
maneira, existe algum elemento z em
P – A1–...–Ai –1comy > z.
09/04/2010 19:14:25
Apêndices
Nãopodeserocasoemquez < x,poisx
émínimoenãopodeserocasoemque
z ≥x,pelofatodeque,então,teríamosy
> z ≥ x,implicandoquex ey sãocomparáveis. Portanto, z e x são incomparáveis. Ou seja, temos x incomparável
tanto a y como a z, e z < y. Portanto,
obtemos uma cópia de Q (com a = z,
b = y ec = x)comoumsubconjuntoPO
deP.⇒⇐Portanto,x<ye,dessemodo,
P éumaordemfraca.
(c)EmumaextensãolineardePdevemostertodososelementosemAiabaixodetodososelementosdeAj(emque
i < j),masnãoimportaemqueordemos
elementosdeAi(ouAj)apareçamentre
si.Hák!formasdeorganizaroselementos de cada Ai, e cada uma das h anticadeiaspodeserorganizadadequalquer
forma, independentemente das outras.
Portanto,hák!h extensõeslinearesdeP.
(d)SejaP=(X,≤)umaordemfraca.A
fimdedemonstrarquedimP ≤2,encontramosduasextensõeslinearesL1=
(X, )eL2=(X, ),deformaqueR=
{L1,L2}éumrealizadordeP.
Como P é uma ordem fraca, pode
serdivididaemanticadeiasporX=A1
È...ÈAh.Sejanjsejaonúmerodeelementos em Ai e denominemos os elementosdeAidaseguintemaneira:
Ai={ai,1,ai,2,...,ai,ni}.
DefinimosL1eL2daseguintemaneira:
AordemL1édadapor
′
′
′
′
′
′
′
′
′
′
′
′
′
′
eaordemL2édadapor
Apendice-3.indd 65
′
″
6.
″
″
″
″
″
″
″
65
″
″
″
″
″
″
ObservequetantoL1comoL2sãoextensões lineares de P, visto que, para
i < j,todososelementosdeAisão<′
ou<″ todososelementosdeAj.Consequentemente,sex≤y emP,deveser
ocasoemquex ≤′ yex ≤″ y.Inversamente, se x e y forem incomparáveis
em P, então x, y Î Aj para algum j.
Nesse caso, observamos que x <′ y e
x >″ y(ouvice-versa).Portanto,Réum
realizadordeP e,portanto,dimP ≤2.
(a) SejaP = (X, ≤) uma cadeiafinita.
Pelo Teorema 55.4, podemos supor
queX={1,2,..., n}e≤émenorque
ouigualacomum.Seja[aj, bj]=[j, j
+ ] e observe que se i < j, então [ai,
bi] está totalmente à esquerda de [aj,
bj],conformenecessário.Portanto,Pé
umaordemdeintervalo.
Seja P = (X, ≤) uma anticadeia.
Paratodox ÎX,seja[ax, bx]=[0,1].
Observeque,paratodox ≠ y emX,os
elementosx ey sãoincomparáveiseos
intervalos[ax,bx]e[ay,by]seinterceptam,conformenecessário.Portanto,P
éumaordemdeintervalo.
Observação:Aparte(a)desseproblematambémprosseguecomumcoroláriodaparte(b).
(b)SejaP = (X, ≤)umaordemfraca.
Então, podemos dividir X em anticadeiasA1 È...ÈAh,demodoquepara
todoxÎAi ey ÎAj com i < j,temos
x < y.AfimdedemonstrarquePéuma
ordem de intervalo, atribuímos intervalosdaseguintemaneira:
Parax ÎAj,seja[ax, bx]=[j, j +½].
09/04/2010 19:14:26
66
Matemática Discreta
Observeque,sex, y ÎAj,entãoxe
y sãoincomparáveise[ax, bx]intercepta[ay,by],conformenecessário.Entretanto,sex ÎAi eyÎAjcomi < j,então
x < y,enoteque[ax, bx]=[i,i + ]está
completamenteàesquerdade[ay, by]=
[j, j + ],conformenecessário.
(c) Seja P o conjunto PO na figura.
Suponhamos, levando-se em conta a
contradição,quePsejaumaordemde
intervaloe,portanto,hajaintervalo[ax,
bx], [ay, by], [aw, bw] e [az, bz] com as
propriedadesdeque
1.[ax, bx]estejaàesquerdade[ay, by],
2.[aw, bw]estejaàesquerdade[az, bz],
3.[ax, bx]interceptetanto[aw, bw]como
[az, bz]e
4.[ay, by]interceptetanto[aw, bw]como
[az, bz].
Como (de acordo com o item 2) [aw,
bw] está à esquerda de [az, bz] e (de
acordo com o item 3) o intervalo [ax,
bx]deveinterceptartanto[aw, bw]como
[az, bz], portanto, o intervalo [ax, bx]
deveseestendercompletamentesobre
a lacuna entre os dois intervalos [aw,
bw]e[az, bz].
Suponhamos,levando-seemconta
acontradição,quehajaalgumaescolha
dos intervalos, de forma que todos
eles apresentem a mesma extensão.
Observe que devemos constatar que
[ax, bx] esteja à esquerda de [ay, by],
que, por sua vez, está à esquerda de
[az, bz], mas, [aw, bw] deve interceptar
osoutrostrês;vejaafigura.
[aw, bw]
[ax, bx]
7.
[ax, bx]
[aw, bw]
[az, bz]
Demodosimilar,[ay, by]tambémdeve
se estender sobre a lacuna entre [aw,
bw] e [az, bz] e, portanto, [ax, bx] deve
interceptar [ay, by], uma contradição
(para1).
(d)Nãoédifícilverificarqueoconjunto PO na figura é uma ordem de
intervalo; utilize os seguintes intervalos:
8.
[ay, by]
[az, bz]
Afimdeque[aw, bw]interceptetanto
[ax, bx]como[az, bz],devecontercompletamente [ay, by] assim como as lacunas entre [ax, bx], [ay, by] e [az, bz].
Portanto, a extensão de [aw, bw] deve
sermaiorqueaquelade[ay, by].⇒⇐
Portanto,P nãopodeserrepresentadoporintervalosquetenhamtodosa
mesmaextensão.
OconjuntoPOtem16extensõeslineares.Paracadaanticadeiadetamanho
2,háduasescolhasparaaordemdos
elementosnaextensãolinear,eessaescolhapodeserfeitaparacadaumadas
quatroanticadeiasdetamanho2,para
umtotalde24=16extensõeslineares.
(a)Osparesdeelementosquesãoincomparáveissão{a, c},{a, f},{c, d},
{b, d},{b, f},{b, e}e{d, f}
(b)EistrêsordenslinearescujaintercepçãoresultaemP:
L1: c<f<a<b<d<e
L2: a<b<d<c<f<e
L3: a<c<f<d<e <b
Atabelaaseguirmostra,paracadapar
incomparável{x, y},asextensõesem
quex < y ey < x.
Apendice-3.indd 66
09/04/2010 19:14:26
Apêndices
{x, y}
x<y
y<x
{a,c}
2,3
1
{a,f}
2,3
1
{c,d}
1,3
2
{b,d}
1,2
3
{b,f}
2
1,3
{b,e}
1,2
3
{d,f}
2
1,3
(c)suponhamosquehouvesseumaextensãolinearLemquef < aed < c.
Comoa < d emP,devemosobservar
quea < demLe,portanto,emL,f < a
< d < c, oqueimplicaquef < cemL
também. Porém, isso contradiz o fato
de que c < f em P. ⇒⇐ Consequentemente,nãopodemosterf < a juntamentecomd < c.
Suponhamos,levando-seemconta
acontradição,umaextensãolinearem
Lemqueb < fef < a.Então,b < a
emL,masa < bemP.⇒⇐Então,b
< aemL,masa < b emP.⇒⇐Dessemodo,nãopodemosterb < fjuntamentecomf < a.
Igualmente,nãopodemosterb < d
< c emumaextensãolinearL,pois,então,b < cemL,masc < b emP.
Domesmomodo,nãopodemostere
< b < demumaextensãolinearL,pois,
então,e < d emL,masd < e emP.
Porfim,nãopodemostere < b < f
emumaextensãolinearL,pois,então,
e < f emL,masf < eemP.
(d)Sequaisquerduasdasrelaçõesf <
a, d < c,b < d, e< b eb < fformantida em uma extensão linear L, então
contradizeríamos uma das afirmações
naparte(c)desseproblema.
(e)Apartirdaparte(b),sabemosque
dimP≤3;dessemodo,restademonstrar que dim P > 2. Suponhamos, levando-seemcontaacontradição,que
Apendice-3.indd 67
9.
10.
67
dimP ≤ 2,portantoP possuiumrealizadorcom(nomáximo)duasextensões lineares. Então, uma dessas extensões lineares satisfaria pelo menos
trêsdentref < a, d < c, b < d, e < b e
b < f, contradizendo a parte (d). ⇒⇐
Portanto,dimP=3.
Suponhamos, levando-se em conta a
contradição,quePcontenhadoiselementos distintos x e y. Observe que
x Ù y ≤x ≤ x Ú y,ecomox Ù y =x Ú y,
constatamosquex Ù y = x.Damesma
maneiraxÙy = y,e,dessemodo, x =
y.⇒⇐Portanto,Papresentanomáximoumelemento.
(a)P Ù Q={(1,3),(2,4),(5,7,9),(6,
8)}ePÚ Q={{1,2,3,4,5,6,7,8,9}}
(b)SejaZkÎR.ComoR=P ÙQ,ele
refina tanto P como Q. Isso significa
quetodapartedeRéumsubconjunto
de uma parte de P e, da mesma maneira, de Q. Particularmente, há um
Xi ÎP,demodoqueZkÍXieumYj Î
Q,demodoqueZkÍYj.ConsequentementeZk ÍXi C Yj.
Suponhamos,levando-seemconta
acontradição,queZk ≠Xi ÇYj.Então,
devehaveroutrapartedeR,porexemplo,Zk′ ,queintercepteXi ÇYj.IssoimplicaqueZk′ deveserumsubconjunto
tantodeXieYj,porquetodapartedeR
deveserumsubconjuntodeumaparte
dePedeumapartedeQ.
Podemos agora formar uma nova
partição a partir de R, simplesmente
combinandoZkeZk′ emumaúnicaparte
Zk ÈZk′ ;denominemosessanovapartiçãoR′ .ObservequeRéestritamente
maisrefinadoqueR′ eR′ refinatanto
P comoQ.Noentanto,issocontradiz
o fato de que R = P ÙQ (ou seja, R
éorefinamentocomummaisgrosseiro
09/04/2010 19:14:26
68
11.
12.
Apendice-3.indd 68
Matemática Discreta
deP eQ).⇒⇐Portanto,Zk=Xi ÇYj.
Aprovaéporinduçãoemn.Ocasobásico,n =1,éóbvio.Suponhamos(hipótesedaindução)queesseresultado
tenhasidoprovadoparan = k.Sejaa,
x1,...,xk+1fornecido,demodoquea ≤
xjparatodo1≤j≤k + 1.Sabemos(por
indução)quea≤x1Ù...Ùxkesabemos
quea≤xk+1(pelahipótesedaindução).
Issosignificaqueaéumlimiteinferior
parax1Ù...Ùxkexk+1,portantooaestá
abaixodomaiorlimiteinferiordex1Ù
...Ùxk exk+1;ouseja,a ≤(x1Ù...Ùxk)
Ùxk+1,conformenecessário.
ParaprovarqueaÚb = u1Ùu2Ù...Ù
un,provamosqueaÚb ≤u1Ùu2Ù...
ÙuneaÚb ≥u1Ùu2Ù...Ùun.
ParademonstrarqueaÚb ≤u1Ùu2
Ù...Ùun:sabemos,utilizandooProblema11,quea ≤u1Ùu2Ù...Ùune
b ≤ u1 Ù u2 Ù ... Ù un. Portanto, u1 Ù
u2Ù...Ùun éumlimitesuperiorpara
a eb.Comoa Úbéolimitesuperior
mínimodea eb,temosa Úb≤u1Ùu2
Ù...Ùun.
ParademonstrarqueaÚb ≥u1Ù
u2Ù...Ùun:sabemosquea ≤a Úbe
b ≤a Úb.Portanto,aÚbÎU(a, b).
Semperdadegeneralidade,u1=a Úb.
Portanto,aexpressãou1Ùu2Ù...Ùun
podeserreescrita(a Úb)Ù(u2Ù...Ù
un).Observequeessaúltimaexpressão
éomaiorlimiteinferiordea Ú beu2
Ù...Ùun,e,portanto,(a Ú b)Ù(u2Ù
...Ùun)≤a Úb.Portanto,u1Ùu2Ù...
Ùun≤a Úb.
09/04/2010 19:14:26