SOLUÇÕES CAPÍTILO 1- MAT DISCRETA

Prévia do material em texto

MA12
nunes
April 2020
Prinćıpio 1 (Boa-ordenação1:). Todo subconjunto não-vazio X ⊂ N possui um menor elemento. Isto significa
que existe um elemento m0 ∈ X que é menor do que todos os demais elementos de X.
Caṕıtulo 1 – 1.4 Exerćıcios2
1. O diagrama abaixo, em que a seta indica o sucessor de cada elemento, representa a estrutura dos
números naturais imposta pelos axiomas de Peano
1 2 3 4 5 6 7 · · ·
Em cada um dos diagramas a seguir, um ou mais dos axiomas de Peano são violados. Diga quais são
eles.
(a) 1 2 3 4 5 6 7 · · ·
O quarto axioma é violado. O conjunto A = {1, 2, 5, 6, . . .} ⊂ N contém o 1 e o sucessor de cada
elemento. No entanto, A não é igual a N.
(b) 1 2 3 4 5 6 7 · · ·
O terceiro axioma é violado. O elemento 2 também não é sucessor nenhum natural. O quarto
axioma é violado. O conjunto A = {1, 3, 5, 7, . . .} ⊂ N contém o 1 e o sucessor de cada elemento.
No entanto, A não é igual a N.
(c) 1 2 3 4 5 6 7 · · ·
O segundo e terceiro axiomas são violados. O número 3 é sucessor de dois números diferentes e,
além disso, 2 também não é sucessor de nenhum natural. O quarto axioma é violado. O conjunto
A = {1, 3, 4, 5, 6, 7, . . .} ⊂ N contém o 1 e o sucessor de cada elemento. No entanto, A não é igual
a N.
(d) 1 2 3 4 5 6 7
O segundo axioma é violado. O número 2 é sucessor de dois números diferentes (1 e 7).
2. Prove, por indução, que
1 + 22 + 32 + · · ·+ n2 = n(n + 1)(2n + 1)
6
.
1[1, Teorema 1.8, p.7], MA12 - Matemática Discreta 2014.pdf, página 6
2[1], página 7
1
Para n = 1, 1 = 1(1+1)(2+1)6 . Suponha que
1 + 22 + 32 + · · ·+ m2 = m(m + 1)(2m + 1)
6
.
Observe que
m(m + 1)(2m + 1)
6
+ (m + 1)2 =
m(m + 1)(2m + 1) + 6(m + 1)2
6
=
(m + 1)[m(2m + 1) + 6(m + 1)]
6
=
(m + 1)[m(2m + 1) + 2m + 2(2m + 3)]
6
=
(m + 1)[m(2m + 3) + 2(2m + 3)]
6
=
(m + 1)(m + 2)(2m + 3)
6
Portanto,
1 + 22 + 32 + · · ·+ m2 + (m + 1)2 = m(m + 1)(2m + 1)
6
+ (m + 1)2
=
(m + 1)(m + 2)(2m + 3)
6
3. Diga onde está o erro da seguinte demonstração da afirmativa
1 + 2 + 4 + 8 + · · ·+ 2n = 2n+1.
A propriedade é trivialmente válida para n = 1. Suponhamos que seja válida par n, ou seja 1 + 2 + 4 +
8 + · · ·+ 2n = 2n+1. Então,
1 + 2 + 4 + 8 + · · ·+ 2n + 2n+1 = 2n+1 + 2n+1 = 2 · 2n+1 = 2n+2.
Portanto, a propriedade também é válida para n + 1. Logo, pelo Prinćıpio da Indução Finita,
1 + 2 + 4 + 8 + · · ·+ 2n = 2n+1, ∀n ∈ N.
Na verdade, a propriedade não vale para n = 1, já que 1 + 21 6= 21+1.
4. Usando indução finita e a propriedade associativa da adição, prove a lei do corte: . . . Se m,n e p são
números naturais tais que m + p = n + p, então m = n.”
Para p = 1, a afirmativa vale pelo segundo axioma de Peano: se os sucessores m + 1 e n + 1 de m e n
são iguais, então m = n.
Suponhamos agora que a propriedade valha para algum natural p. Isto é, m + p = n + p implique
m = n. Suponhamos que m + (p + 1) = n + (p + 1). Pelas propriedades associativa e comutativa da
adição, a igualdade é equivalente a (m+1)+p = (n+1)+p. Mas pela hipótese de indução, isto implica
m + 1 = n + 1, que por sua vez implica m = n (pelo caso em que p = 1). Logo, se a propriedade vale
para p, então vale também para p + 1.
Portanto, pelo Principio da Indução, a lei do corte vale para todo p natural.
5. Demonstre a propriedade transitiva da ordem: Se m,n e p são números naturais tais que m < n e
n < p, então m < p.
Suponhamos que m < n e n < p. Então, pela definição da ordem, existem naturais r e s tais que
m + r = n e n + s = p. Substituindo a expressão de n fornecida pela primeira igualdade na segunda,
temos (m + r) + s = p, que é equivalente a m + (r + s) = p. Logo, m < p.
2
Caṕıtulo 1 – 1.6 Exerćıcios3
1. Prove, por indução, que se X é um conjunto finito com n elementos, esses elementos podem ser orde-
nados de n! modos.
Um conjunto com 1 elemento sé pode ser ordenado de 1 = 1! modo, o que mostra que a propriedade
vale para n = 1. Suponhamos que ela valha para n e consideremos um conjunto {a1, a2, . . . , an, an+1}
com n+1 elementos. As posśıveis ordenações desse conjunto podem ser obtidas tomando cada uma das
n! ordenações de {a1, a2, . . . , an, an} é inserindo an+1, em uma das n + 1 posições posśıveis, gerando
assim n!(n+1) = (n+1)! posśıveis ordenações. Logo, a propriedade também vale para n+1. Portanto,
pelo Prinćıpio da Indução, vale para todo n natural.
OU
Observe que as posśıveis ordenações de X estão associadas às diferentes bijeções definidas de In em X.
Provaremos por indução que se n(X) = n, então há n! bijeções definidas de In em X. Se n = 1, temos
apenas uma bijeção f : I1 → X, f(1) = x, x ∈ X.
Nossa hipótese de indução: se n(X) = k, então há k! bijeções definidas de Ik em X.
Seja X tal que n(X) = k + 1. Para cada x ∈ X, considere o conjunto Yx = X − {x}. Considere os
conjuntos
Gx = {g, g : Ik → Yx, g é bijeção}
Fx = {f, f : Ik+1 → X, f|Yx ∈ G§, f(k + 1) = x}
Pela HI, n(Gx) = k!. É fácil ver que também há uma bijeção entre Gx e Fx. Logo, n(Fx) = k!.
Afirmamos que o conjunto
F = {f, f : Ik+1 → X, f é bijeção}
coincide com a união
∪x∈XFx.
Sabemos que
∪x∈XFx ⊂ F .
Seja f ∈ F . Considere x = f(k + 1). Claramente f|Yx ∈ G§. Logo, f ∈ Fx. A cardinalidade da união
disjunta dos k + 1 conjuntos Fx é dada pela soma de suas cardinalidades. Portanto, F = (k + 1) · k!.
2. Prove, por indução, que se X é um conjunto com n elementos, possui 2n subconjuntos.
Neste caso, convém começar de n = 0, para o qual a propriedade vale, já que o conjunto vazio possui
1 = 20 subconjunto. Suponhamos que a propriedade valha para n e consideremos um conjunto A =
{a1, a2, . . . , an, an+1} com n+1 elementos. Cada subconjunto de A ou é um subconjunto {a1, a2, . . . , an}
ou é a união de um tal subconjunto com {an+1}. Ou seja, cada subconjunto de {a1, a2, . . . , an} dá origem
a 2 subconjuntos de A, que tem, assim, 2 · 2n = 2n+1 subconjuntos. Logo, a propriedade também vale
para n + 1. Portanto, pelo Prinćıpio da Indução, vale para todo n ≥ 0.
OU
Seja X = {x1, x2, . . . , xn}. Podemos associar cada subconjunto de X a uma n-upla ordenada perten-
cente ao conjunto P = ({0, 1})n. Isto é, vamos definir uma função f : X → P . Se Y ⊂ X, consideramos
f(Y ) a n-upla (v1, . . . , vn) tal que vi = 0 se xi /∈ Y e vi = 1, se xi ∈ Y . Dados dois subconjuntos
distintos Y1 e Y2 de X, existe ao menos um xj ∈ X que pertence a um deles e não pertence ao outro.
Consequentemente, f(Y1) 6= f(Y2). Isto é, f é injetiva. Se v = (v1, . . . , vn) ∈ ({0, 1})n, se v é o vetor
nulo, então f(∅) = v. Se v não é o vetor nulo, considere o conjunto Y = {x ∈ X,x = xi, vi = 1}. Ele é
subconjunto de X e f(Y ) = v. Logo, f é sobrejetiva. Como é bijetiva e n(P ) = 2n, a cardinalidade do
conjunto de subconjuntos de X também é 2n.
3[1], página 11
3
3. Dados 3n objetos de pesos iguais, exceto um, mais pesado que os demais, mostre que é posśıvel deter-
minar este objeto com n pesagens em uma balança de pratos.
Para n = 1, basta de fato uma pesagem, feita com dois dos objetos: se ela indicar um objeto mais
pesado do que o outro, ele é o procurado; se os objetos tiverem pesos iguais, o objeto que ficou de fora
na pesagem é o mais pesado. Suponhamos agora que seja posśıvel determinar qual é mais pesado dentre
3n objetos com n pesagens e consideremos um conjunto com 3n+1 objetos. Dividimos estes objetos em
três grupos com 3n objetos cada e comparamos o peso de dois deles. Se um deles for mais pesado, o
objeto procurado está nele: senão, está no grupo que ficou de fora da pesagem. De qualquer modo,
pela hipótese de indução, ele pode ser encontrado em n pesagens adicionais, para um total de n + 1
pesagens. Logo, a propriedade vale para conjuntos de 3n+1 objetos e, pelo Principio da Indução, para
conjuntos com 3n objetos, qualquer que seja n.
4. Prove que, dado um conjunto com n elementos, é posśıvel fazer uma fila com seus subconjuntos de tal
modo que cadasubconjunto da fila pode ser obtido a partir do anterior pelo acréscimo ou supressão de
um único elemento.
A propriedade vale para um conjunto com um único elemento a1: seus dois únicos subconjuntos são ∅
e {a1} e é posśıvel passar do primeiro ao segundo acrescentando-se a1. Suponhamos que a propriedade
seja válida para conjuntos com n elementos e consideremos o conjunto com n + 1 elementos X =
{a1, a2, . . . , an, an+1}. Consideremos a lista L dos subconjuntos de {a1, a2, . . . , an} satisfazendo as
condições do enunciado (ela existe, pela hipótese de indução) e formemos uma lista de subconjuntos
de X do seguinte modo: começamos com L e acrescentamos a lista L′ que consiste dos subconjuntos
de L em ordem reversa, acrescentando-se an+1 a cada um deles. A nova lista é formada por todos os
subconjuntos de X (ela lista primeiro todos os subconjuntos que não contém an+1 e, a seguir, todos que
o contém). Além disso, sempre é posśıvel passar de um subconjunto ao próximo da lista acrescentando-
se ou retirando-se um elemento. De fato, pela hipótese de indução isto ocorrem em L; a passagem do
último subconjunto de L para o primeiro de L′ ocorre pela adição de an+1; finalmente, a passagem de
cada subconjunto de L′ para o próximo se dá de forma inversa à ocorrida em L. Assim, a propriedade
vale também para conjuntos com n + 1 elementos. Logo, por indução, vale para qualquer conjunto
finito.
5. Diga onde está o erro na seguinte demonstração da afirmativa . . . Todas as bolas de bilhar têm a mesma
cor”.
Seja P (n) a propriedade “todas as bolas em um conjunto com n bolas têm a mesma cor”. A propriedade é
trivialmente verdadeira para n = 1. Suponhamos agora que ela seja verdadeira para n e consideremos um
conjunto com n+1 bolas B = {b1, b2, . . . , bn, bn+1}. Os subconjuntos {b1, b2, . . . , bn} e {b2, . . . , bn, bn+1}
de B têm n elementos cada: logo, pela hipótese de indução, todas as bolas em cada um deles têm a
mesma cor. Mas os elementos b2, . . . , bn são comuns a esses dois subconjuntos. Dáı, conclúımos que
todos os n + 1 elementos de B têm mesma cor, o que mostra que a propriedade vale para n + 1. Logo,
pelo Prinćıpio da Indução, em uma coleção com n bolas todas têm a mesma cor, para todo n ∈ N.
O erro está no passo de indução para n = 1. Neste caso, os subconjuntos {a1, a2, . . . , an} e {a2, . . . , an, an+1}
não tem elementos em comum.
6. Diga se cada conjunto abaixo é finito ou infinito, justificando:
• o conjunto de todas as pessoas que já viveram na Terra.
Finito.
• o conjunto de todos os múltiplos de 7 cuja representação decimal termina com 3578.
Seja n, um múltiplo de 7 cuja representação decimal termine com 3578. Não há perda de gene-
ralidade em supor que n ∈ N. Além disso, deve existir m ∈ N, tal que n = m · 10000 + 3578 e
m · 10000 deixa resto 6 na divisão por 7. Consequentemente, devemos ter
m · 10000 (mod 7) ≡ r · 4 (mod 7) ≡ 6 (mod 7), r ∈ {0, 1, . . . , 6}
Logo, r = 5 e n = 7k · 10000 + 53578, k ∈ N Infinito. Observe que se n é um múltiplo de 7 cuja
representação decimal termina com 3578, então n = m · 10000 + 3578 e m · 10000 deixa resto 6 na
divisão por 7. Isto é o conjunto indicado é dado por
M = {n ∈ Z, |n| = 7k · 10000 + 53578, k ∈ N}
4
• o conjunto de todos os números naturais cuja representação decimal tenha apenas algarismos
diferentes de zero, cuja soma seja menor que 1000.
Finito. Observe que a maior quantidade n de algarismos de tais números é 999 correspondendo
ao número em que todos os 999 algarismos são iguais a 1. Para cada 1 ≤ k ≤ n, a quantidade de
soluções positivas de
x1 + · · ·+ xk ≤ 1000, xi ∈ {1, 2, 3, . . . , 9}
é finita.
• o conjunto de todos os números racionais que podem ser escritos como fração com denominador
menor que 1000.
Infinito. Todos os naturais pertencem a tal conjunto.
• o conjunto de todos os números primos.
Infinito.
7. Sejam X e Y dois conjuntos infinitos enumeráveis. Isto significa que existem sequências (x1, x2, x3, . . .)
e (y1, y2, y3, . . .) incluindo todos os elementos de X e Y , respectivamente. Explique como construir uma
sequência incluindo todos os elementos de X ∪ Y , mostrando assim que X ∪ Y também é enumerável.
A sequência {x1, y1, x2, y2, x3, y3, . . .} inclui todos os elementos de X ∪Y , que é, portanto, enumerável.
8. Considere o conjunto N2 de todos os pares ordenados de números naturais. Encontre uma sequência
que inclua todos os elementos de N2, mostrando assim que N2 é enumerável. Isto mostra que o conjunto
dos números racionais também é enumerável. Por quê?
Um modo de construir tal sequência é ordenar os pares ordenados de números naturais de acordo com a
soma das coordenadas: primeiro, os que têm soma 2, depois 3, e assim diante, dando origem à sequência
{(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), . . .},
o que nos mostra que N × N é enumerável. Cada par (m,n) corresponde aos números racionais em
−m/n e m/n. Logo, a partir dessa sequência podemos construir uma outra sequência que inclui todos os
números racionais, o que mostra que o conjunto dos racionais também é enumerável. Por exemplo,
{(1, 1), (−1, 1), (1, 2), (−1, 2), (2, 1), (−2, 1), (1, 3), (−1, 3), (2, 2), (−2, 2), (3, 1), (−3, 1), . . .},
9. Mostre que o conjunto de todos os subconjuntos de N é não enumerável. [Sugestão: associe cada
subconjunto de N a uma sequência em que os termos são iguais a 0 ou 1.]
Cada subconjunto X de N corresponde a uma sequência (xn) em que xn = 1 se n ∈ X e xn = 0 caso
contrário. Como o conjunto de tais sequências é não enumerável, o conjunto de todos os subconjuntos
de N também é não enumerável. (ver Exemplo 1.4, página 10 de [1])
Referências
[1] Paulo Cezar Pinto Carvalho and Augusto César Morgado. Matemática discreta. SBM, 2015.
5