Re: [obm-l] Funcao definida recursivamente

["Bruno França dos Reis" <bfreis@xxxxxxxxx>]

Claudio

Isso aí se assemelha ao "Problema de Collatz". Veja no Mathworld: http://mathworld.wolfram.com/CollatzProblem.html

(provar que f é função é equivalente a demonstrar a conjectura de collatz, isto é, que a partir de qualquer semente inicial natural a seqüência de collatz devolve o valor 1.)

Acredito que no caso da conjectura de Collatz ser verdadeira e portanto sua f estar definida, ela seja a função constante igual a 1, já que nunca poderá chegar a outro valor.

Se a conjectura de Collatz for falsa, então f não é função, pois existirá algum k natural para o qual a seqüência de Collatz não passa por NENHUM dos naturais que já se verificou que vão para 1 (os quais tem imagem 1), e então vc não permite calcular o valor de f(k) com essa definição de f.



Abraço
Bruno

On 8/24/06, claudio.buffara <claudio.buffara@terra.com.br> wrote:

Segue abaixo a tentativa de se definir uma funcao f: N -> N
(N = conjunto dos inteiros positivos)

f (1) = 1;
Se n eh par, entao f (n) = f (n/2);
Se n eh impar, entao f (n) = f (3n + 1).

Perguntas:
1) As condicoes acima realmente definem uma tal f (ou seja, permitem que, A CADA elemento de N seja associado EXATAMENTE UM
elemento de N)?
2) Em caso afirmativo, a funcao assim definida eh unica?

O problema parece ser que o valor de f(n) para n impar eh definido em termos do valor de f num argumento maior do que n (3n+1, para
ser exato), de modo que nao se pode aplicar o principio da inducao (pelo menos nao diretamente).

[]s,
Claudio.


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================

-- 
Bruno França dos Reis
email: bfreis - gmail.com
gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
icq: 12626000

e^(pi*i)+1=0