Buscar

Exercícios resolvidos sobre indução do 1º/2013

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 1
Prove que, para todo nu´mero primo p,
√
p e´ irracional. Dica: suponha que
√
p e´ racional, e prove
por contradic¸a˜o.
Resposta: Suponha
√
p racional. Enta˜o,
√
p =
m
n
onde m e n sa˜o nu´meros naturais que na˜o possuem fatores em comum. Elevando ao quadrado,
p =
m2
n2
e, portanto,
pn2 = m2
Sendo que m e n na˜o tem fatores em comum, esta u´ltima equac¸a˜o nos diz que m deve ser um
divisor de p, o que contradiz o fato de p ser primo.
Usando induc¸a˜o, prove que n3 + (n+ 1)3 + (n+ 2)3 e´ divis´ıvel por 9, para todo inteiro n ≥ 0.
Resposta: Para n = 0,
n3 + (n+ 1)3 + (n+ 2)3 = 9
que e´ divis´ıvel por 9.
Para n = k, a expressa˜o acima e´ k3 + (k + 1)3 + (k + 2)3, e suponhamos que e´ divis´ıvel por
9. Enta˜o, existe um inteiro a tal que k3 + (k + 1)3 + (k + 2)3 = 9a
Para n = k + 1, obtemos
n3 + (n+ 1)3 + (n+ 2)3 = (k + 1)3 + (k + 2)3 + (k + 3)3
= (k + 1)3 + (k + 2)3 + k3 + 9k2 + 27k + 27
= 9a+ 9(k2 + 3k + 3)
= 9(a+ k2 + 3k + 3)
que e´ divis´ıvel por 9.
Use o princ´ıpio das “casas dos pombos” para provar que, se escolhemos n + 1 nu´meros inteiros
diferentes entre 1 e 2n, dois desses nu´meros sa˜o consecutivos. Dica: os n+ 1 nu´meros escolhidos
sa˜o os “pombos”, pense quais seriam as n ”casas”.
Resposta: Os nu´meros inteiros entre 1 e 2n podem ser agrupados em n conjuntos (“casas”)
{1, 2}, {3, 4}, . . . , {2n− 1, 2n}. Cada um dos n+1 nu´meros escolhidos (os “pombos”) pertence
a um dos n conjuntos. Como ha´ mais “pombos” que “casas”, necessariamente dois nu´meros
pertencem a mesmo conjunto e, portanto, sa˜o consecutivos.
Prove que log
4
9 e´ irracional. Dica: suponha que log
4
9 e´ racional e prove por contradic¸a˜o.
Resposta: Suponha log
4
9 racional. Enta˜o,
log
4
9 =
m
n
onde m e n sa˜o nu´meros naturais que na˜o possuem fatores em comum. Por definic¸a˜o de
logaritmo
4
m
n = 9
e, portanto,
4m = 9n
O termo na esquerda da igualdade e´ par, e o termo na direita e´ ı´mpar. A igualdade e´ imposs´ıvel,
o que implica que log
4
9 na˜o pode ser racional.
No Brasil, todas as placas de carros teˆm treˆs letras e quatro d´ıgitos. Considere uma turma de 40
alunos, na qual cada aluno possui um carro, e suponha que cada aluno soma os quatro d´ıgitos
da placa de seu carro. Prove que ha´ dois alunos que obte´m o mesmo valor da soma. Dica: use o
princ´ıpio da “casa dos pombos”.
Resposta: O menor valor poss´ıvel para a soma dos quatro d´ıgitos e´ 0 + 0 + 0 + 0 = 0, e
o maior valor poss´ıvel e´ 9 + 9 + 9 + 9 = 36. Assim, temos um total de 37 valores poss´ıveis
(“casas”). Por outro lado, temos 40 placas (“pombos”). Como ha´ mais “pombos” que “casas”,
necessariamente duas placas produzira˜o o mesmo valor para a soma de seus quatro d´ıgitos.
Usando induc¸a˜o, prove que n4 − 4n2 e´ divis´ıvel por 3, para todo inteiro n ≥ 1.
Resposta: Para n = 1,
n4 − 4n2 = −3
que e´ divis´ıvel por 3.
Para n = k, a expressa˜o acima e´ k4−4n2, e suponhamos que e´ divis´ıvel por 3. Enta˜o, existe
um inteiro a tal que k4 − 4k2 = 3a
Para n = k + 1, obtemos
(k + 1)4 − 4(k + 1)2 = k4 + 4k3 + 2k2 − 4k − 3
= 3a+ 4k3 + 6k2 − 4k − 3
= 3(a+ 2k2 − 1) + 4k(k + 1)(k − 1)
Na u´ltima expressa˜o, o primeiro termo e´ divis´ıvel por 3. No segundo termo, temos:
se k mo´dulo 3 =


0, enta˜o k e´ divis´ıvel por 3,
1, enta˜o k − 1 e´ divis´ıvel por 3,
2, enta˜o k + 1 = (k − 2) + 3 e´ divis´ıvel por 3,
Assim, todos os termos sa˜o divis´ıveis por 3.

Outros materiais