Exercícios resolvidos sobre indução e função do 2º/2013

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 1
1. Prove que, para todo inteiro positivo n, 23
n
+ 1 e´ divis´ıvel por 3n+1.
Resposta: A prova e´ por induc¸a˜o. Para n = 1, a afirmac¸a˜o e´ verdadeira, pois 23
n
+ 1 =
23 + 1 = 9 e´ divis´ıvel por 3n+1 = 32 = 9.
Supomos agora que a afirmac¸a˜o e´ verdadeira para n = k. Enta˜o, existe p ∈ N tal que
23
k
+ 1
3k+1
= p. (1)
Seguidamente, provamos que a afirmac¸a˜o e´ verdadeira para n = k + 1. Podemos escrever
23
(k+1)
+ 1
3k+2
=
(23
k
)3 + 1
3k+2
. (2)
Usamos a Eq. (1) para substituir 23
k
= 3k+1m− 1 en Eq. (2), e obtemos
23
(k+1)
+ 1
3k+2
=
(3k+1p− 1)3 + 1
3k+2
=
33(k+1)p3 − 3 · 32(k+1)p2 + 3 · 3k+1p
3k+2
= 32k+1p3 − 3k+1p2 + p
= q,
onde q ∈ N . Portanto, 23(k+1) + 1 e´ divis´ıvel por 3k+2.
2. Sejam 3 nu´meros inteiros positivos consecutivos. Prove que o cubo do maior nu´mero na˜o
pode ser igual a` soma dos cubos dos outros dois nu´meros.
Resposta: A prova e´ por contradic¸a˜o. Sejam os nu´meros inteiros positivos consecutivos
p− 1, p e p + 1, onde p ∈ N e p > 1. Supondo a afirmac¸a˜o verdadeira, enta˜o
(p + 1)3 = (p− 1)3 + p3
p3 + 3p2 + 3p + 1 = p3 − 3p2 + 3p− 1 + p3
3p2 + 1 = −3p2 − 1 + p3
2 = p2(p− 6)
Na u´ltima equac¸a˜o, p2 e´ um inteiro positivo. Como p− 6 deve ser fator de 2, enta˜o ha´ dois
casos a considerar: p−6 = 1 e p−6 = 2. Se p−6 = 1, enta˜o p = 7; no entanto, 83 6= 63 +73.
Se p− 6 = 2, enta˜o p = 8; no entanto, 93 6= 73 + 83. Temos, assim, uma contradic¸a˜o, o que
implica que a afirmac¸a˜o deve ser falsa.
3. Suponha que A e B sa˜o conjuntos e f : A → B. Para um subconjunto S de A, definimos
f(S) = {f(x)|x ∈ S}. Sejam S e T subconjuntos de A.
(a) Prove que f(S ∪ T ) = f(S) ∪ f(T ).
Resposta: Primeiro provamos que todo elemento de f(S∪T ) tambe´m esta´ em f(S)∪
f(T ): Suponha f(x) ∈ f(S ∪ T ). Enta˜o, x ∈ S ∪ T . Se x ∈ S, enta˜o f(x) ∈ f(S) e, se
x ∈ T , enta˜o f(x) ∈ f(T ). Portanto, f(x) ∈ f(S) ∪ f(T ).
Seguidamente, provamos que todo elemento de f(S)∪ f(T ) tambe´m esta´ em f(S ∪T ):
Suponha f(x) ∈ f(S) ∪ f(T ). Se f(x) ∈ f(S), enta˜o x ∈ S e, se f(x) ∈ f(T ), enta˜o
x ∈ T . Portanto, x ∈ S ∪ T e, enta˜o, f(x) ∈ f(S ∪ T ).
(b) Prove que f(S ∩ T ) ⊆ f(S) ∩ f(T ) mas na˜o necessariamente f(S ∩ T ) = f(S) ∩ f(T ).
Resposta: Primeiro provamos que todo elemento de f(S∩T ) tambe´m esta´ em f(S)∩
f(T ): Suponha f(x) ∈ f(S∩T ). Enta˜o, x ∈ S∩T . Sendo que x ∈ S, enta˜o f(x) ∈ f(S)
e tambe´m, sendo que x ∈ T , enta˜o f(x) ∈ f(T ). Portanto, f(x) ∈ f(S) ∩ f(T ).
Para provar que na˜o necessariamente f(S ∩ T ) = f(S) ∩ f(T ), consideramos um con-
traexemplo: f(x) = 1, S = {2} e T = {3}. Assim, S ∩ T = ∅ e f(S ∩ T ) = ∅. No
entanto, f(S) = f(T ) = {1} e f(S) ∩ f(T ) = {1} 6= ∅.
4. Seja A qualquer conjunto de 20 inteiros diferentes escolhidos da progressa˜o aritme´tica
1, 4, 7, 10, 13, . . . , 100. Prove que A deve conter dois inteiros diferentes cuja soma e´ 104.
Resposta: Cada inteiro da progressa˜o tem a forma 3n + 1, onde n = 0, 1, 2, . . . , 33. Pro-
curamos dois nu´meros diferentes 3p + 1 e 3q + 1 tais que (3p + 1) + (3q + 1) = 104, de
onde obtemos p + q = 34. Existem 17 pares de inteiros positivos diferentes que soman 34:
{0, 34}, {1, 33}, . . . , {16, 18}. O par {0, 34} na˜o serve, pois 3 · 34 + 1 > 100 e na˜o pertence
a A. Temos assim 16 pares poss´ıveis, e um total de 20 nu´meros em A. Pelo princ´ıpio das
casas dos pombos, onde os pares sa˜o as “casas” e os nu´meros de A sa˜o os “pombos”, existem
pelo menos dois nu´meros que correspondem ao mesmo par e que, portanto, somam 104.