Re: [obm-l] Funcao definida recursivamente

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

Nossa! Ainda bem que eu não perdi muito tempo com este problema...

 

De qualquer forma, acho interessante pensar num problema correlato.

Seja A um subconjunto de N (naturais = inteiros positivos) tal que:

(i) se n pertence a M e n é par, então n/2 pertence a A

e

(ii) se n pertence a M e n é ímpar, então 3n+1 pertence a A.

Determinar se existe um subconjunto finito X de N tal que, se além das condições (i) e (ii) acima, tivermos também "X está contido em A", então poderemos garantir que A = N.

 

Por exemplo, se X for igual ao conjunto dos naturais pares, então isso será verdade. Só que neste caso X não é finito (obviamente).

Mesmo deixando X ser infinito, o problema não é trivial. Por exemplo, se X = conjunto dos naturais ímpares ou então X = conjunto dos primos.

 

[]s,

Claudio.

 

De:	owner-obm-l@mat.puc-rio.br

Para:

obm-l@mat.puc-rio.br

Cópia:

Data:

Thu, 24 Aug 2006 21:46:09 -0300

Assunto:

Re: [obm-l] Funcao definida recursivamente

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.