 |
|
|
|||
 |
|||||
|
|
|
|
|||
|
|
|||||
Renate Watanabe
Neste artigo vamos fazer, inicialmente, algumas afirmações sobre números naturais que são verdadeiras para os números 1, 2, 3 e muitos outros e vamos tentar responder à pergunta: elas são verdadeiras sempre? Após enunciar uma forma do princípio de indução e usá-lo em um exemplo, passaremos a descrever duas situações envolvendo indução: - uma, para ver se, de acordo com uma lenda, o mundo está para acabar, e - outra, para provar que inteligência é contagiosa, pois demonstraremos que havendo um aluno inteligente numa classe com n alunos, então todos os alunos da classe são inteligentes. O objetivo do artigo é enriquecer o estoque de fatos e problemas interessantes que professores colecionam para usar em momentos oportunos nas aulas que ministram.
1.
2.
3.
4.
5.
Vejamos: 1. “n < 100” é uma sentença verdadeira para n = 1, n = 2, n = 3 e outros, mas torna-se falsa para qualquer número natural maior do que 99. Portanto,
“ 2. “n2 + n + 41 é um número primo” é uma sentença verdadeira para n = 1, n = 2, n = 3 e outros. De fato, ela é verdadeira para todos os números naturais menores do que 40. Porém o número 402 + 40 + 41 = 40 . (40 + 1) + 41 = 41 . 41 não é primo, mostrando que a sentença
“ Em 1772, Euler mostrou que f(n) = n2 + n + 41 assumia valores primos para n = 0, 1, 2,..., 39. Observando que f(n – 1) = f( - n), vê-se que n2 + n + 41 assume valores primos para 80 inteiros consecutivos: -40, -39, ..., -1, 0, 1, ..., 39. Substituindo a variável n por n – 40, obtém-se f(n – 40) = g(n) = n2 –79n + 1 601 que assume valores primos para todos os números naturais de 0 até 79 – um “record” para trinômios do segundo grau(1). 3. “991n2 + 1 não é um quadrado perfeito” é uma sentença verdadeira para n = 1, n = 2, n = 3 e, mesmo após muitas e muitas tentativas, não se acha um número que a torne falsa. Pudera! O menor número natural n para o qual 991n2 + 1 é um quadrado perfeito é
12 055 735 790 331 359 447 442 538 767(2) e, portanto, a sentença
“ 4. “A soma dos n primeiros números ímpares é n2” é uma sentença verdadeira para n = 1, n=2, n = 3 e, como no caso anterior, após muitas e muitas tentativas, não se acha um número natural que a torne falsa. Neste caso, tal número não existe pois, como veremos adiante, esta sentença é verdadeira sempre. 5. “2n + 2 é a soma de dois números primos” é uma sentença verdadeira para n = 1, n=2, n=3 e, como nos dois exemplos anteriores, após muitas e muitas tentativas, não se encontra um número natural que a torne falsa. Mas agora temos uma situação nova: ninguém, até hoje, encontrou um número que tornasse a sentença falsa e ninguém, até hoje, sabe demonstrar que a sentença é verdadeira sempre. A sentença é a famosa conjetura de Goldbach(3) feita em 1742, em uma carta dirigida a Euler: “Tudo inteiro par, maior do que 2, é a soma de dois números primos”. Não se sabe, até hoje, se esta sentença é verdadeira ou falsa. Em suma, dada uma afirmação sobre números naturais, se encontrarmos um contra-exemplo, saberemos que a afirmação não é sempre verdadeira. E se não acharmos um contra-exemplo? Neste caso, suspeitando que a afirmação seja verdadeira sempre, uma possibilidade é tentar demonstrá-la recorrendo ao princípio da indução.
“Seja S um conjunto de números naturais, com as seguintes propriedades:
1.
0
2.
Nestas condições, S = IN”. Vamos ver como este princípio nos permite demonstrar que a sentença 4 é verdadeira.
“ Demonstração: Seja S o conjunto dos números naturais n para os quais a soma dos n primeiros números ímpares é n2.
1. 1
2. Vamos supor que k
Vamos provar que k + 1
Estamos supondo que
1 + 3 + 5 + ... + 2k – 1 = k2 e queremos provar que 1 + 3 + 5 + ... + 2k + 1 = (k + 1)2.Basta observar que 1 + 3 + 5 + ... + (2k – 1) + (2k + 1) = k2 + (2k + 1) = (k + 1)2 O princípio da indução nos garante, agora, que S = IN*, ou seja, a afirmação “a soma dos n primeiros ímpares é n2” é verdadeira para todos os números naturais maiores do que zero. No 2o. grau o professor encontra muitas oportunidades para fazer demonstrações por indução, se assim o desejar, mas não nos deteremos aqui para dar os exemplos clássicos.
Após a criação do mundo, em um mosteiro escondido na Índia, o Grande Criador colocou uma placa de bronze e nela fixou três bastões cobertos de diamantes. Em um dos bastões, em ordem decrescente de tamanho, colocou 64 discos de ouro. E assim disse aos monges: “Transfiram esta pilha de discos para outro bastão, movendo, ininterruptamente, um disco de cada vez e nunca permitindo que um disco fique acima de um menor. Quando terminarem esta tarefa e os 64 discos estiverem em outro bastão, este templo se reduzirá à pó e com um estrondo de trovões o mundo acabará.” Dizem os sábios que o mundo foi criado há 4 bilhões de anos aproximadamente e os monges, desde a criação, estão movendo os discos na razão de um disco por segundo. Será que veremos o mundo acabar? É muito difícil imaginar os movimentos feitos com uma pilha de 64 discos. Imaginemos uma pilha com 1 disco:
Para 1 disco, a transferência se dá com 1 movimento:
Dois discos
m2
= 3
Para 2 discos, a transferência se dá com 3 movimentos.
Três discos:
m3 = 7 Quatro discos:
m4
= 15
Já se pode ver como deslocar n discos, com um menor número de
movimentos possível: inicialmente, movem-se n – 1 discos para o
bastão de trás, com mn-1 movimentos; em
seguida, move-se o n-ésimo disco para o outro bastão da frente, com
1 movimento; finalmente movem-se os n – 1 discos do bastão de trás
para o da frente, com mn-1 movimentos.
Tem-se:
mn
=
mn-1 + 1 + mn-1
= 2mn-1 + 1
Façamos uma tabela com o número de discos e o número de movimentos mínimo
para mudá-los de um bastão para outro:
Precisamos descobrir o valor de m64 porque m64
segundos após a criação do mundo, ele acabará e já se passaram 4 bilhões
de anos!
Observando a segunda linha da tabela vemos que os seus números são, a
menos de 1: 2, 4, 8, 16, 32, 64, ou seja, 21, 22, 23,
24, 25, 26, o que nos leva a fazer a
seguinte conjetura:
mn
= 2n –1
Esta sentença é verdadeira para n = 1, 2, 3 ,4 5, 6, mas será
verdadeira sempre? Tentemos demonstrá-la por indução.
Seja
S o conjunto dos números naturais n tais que n discos
são movidos com 2n –1 movimentos.
Vamos provar que k + 1 Para remover k + 1 discos passamos, inicialmente, k discos para o bastão de trás com mk movimentos; em seguida, com 1 movimento, o (k + 1) –ésimo disco vai para o outro bastão da frente; com m k movimentos, os k discos de trás passam para o bastão da frente. Isto é,
mk + 1 = 2k – 1 + 1 + 2k – 1 = 2 . 2k – 1 = 2k + 1 – 1
e isto mostra que k + 1
O princípio da indução nos garante que n discos podem sempre ser
removidos com 2n – 1 movimentos e, em particular, m64
= 264 – 1.
E assim, ficamos sabendo que 264 – 1 segundos após a criação do
mundo, ele terminará. Com um pouco mais de Matemática ficaremos sabendo se
isto ocorrerá logo.
Façamos alguns cálculos.
Quantos segundos tem um ano?
Exagerando, vamos supor que os monges façam 225 movimentos por
ano (na verdade fazem
Passaram-se até hoje 4 bilhões de anos, ou seja, 4 . 109 anos.
Podemos ficar tranqüilos – faltam mais do que 508 bilhões de anos para os
monges terminarem sua tarefa – isto, supondo que eles não errem no
caminho.
Os bastões com 7, 8 ou 9 discos constituem um brinquedo conhecido como
“Torre de Hanoi”(4), inventado pelo matemático francês Edouard
Lucas (1842-1891) e já vendido como brinquedo em 1883. Um folheto o
acompanhava contando a lenda acima. E. Lucas demonstrou um teorema
conhecido como “teste de Lucas” que lhe permitiu provar, entre outros
fatos, que 2127 – 1 é um número primo e este foi, até 1952, o
maior número primo conhecido.
2127 – 1 = 170 141 183 460 469 231 731 687 303 715 884 105 727(5)
O teorema que vamos enunciar e demonstrar é uma versão mais popular de uma demonstração atribuída a A. Tarski (1902-1983) de que todos os números naturais são iguais(6). O enunciado do teorema é o seguinte:
“ Demonstração (por indução):
Seja
S o conjunto dos números naturais n tais que se numa classe
com n alunos, um for inteligente, então todos são inteligentes.
1.
1
2.
Vamos supor que k
Vamos provar que k + 1
Pelo princípio da indução, qualquer que seja n > 0, se numa classe com n alunos, um for inteligente, então todos são inteligentes. Mas, pela nossa experiência, infelizmente, isto é bobagem. E agora? Onde está o erro?
Referências
(1)
Euler e a Teoria dos Números, RPM 4, p. 12.
Mathematical Gems II,
R. Honsberger, MAA, p. 29.
(2)
Induction in Geometry, L. Golovina, I. M. Yaglom, Mir, p. 8.
(3)
A experiência matemática, P. J. Davis, R. Hersh, Francisco Alves,
p. 210.
(4)
Divertimentos Matemáticos, Martin Gardner, Ibrasa, p. 59. Matemática e Imaginação, E. Kasner, J. Newman Zahar, p. 167. A Torre de Hanói, Revista de Ensino de Ciência, 11, p. 21 (5) Elementos de Álgebra, L. H. Jacy Monteiro, Ao Livro Técnico, p. 163.
(6)
Enrichment Mathematics for High School, NCTM, p. 127.
|
n
IN, n < 100.
n
IN, n2 + n + 41 é
um número primo.
n
IN*, 991n2 +
1 não é um quadrado perfeito.
n
IN*, a soma dos n
primeiros números ímpares é n2.
n
IN*, 2n 
n
S, pois para 1 disco necessitamos de 1 = 21 – 1
movimentos.
S, isto é, 
n
IN*, se numa
classe com n alunos um for inteligente, então todos os alunos da
classe são inteligentes”.
