1) Vamos observar alguns fatos sobre uma função f:N* -> N* estritamente crescente.
(f(a)<f(b) <==> a < b) ==> f assume seu mínimo em 1; com efeito, 1 < n, para todo n!=1, o que implica f(1) < f(n), para todo n diferente de 1.
Sendo f estritamente crescente e definida em N*, se existir algum a tal que f(a) = a, então f é a identidade para todo n <= a; (prove isto)
Chame m = f(1) o valor mínimo da função f.
Se m = 1, usando a propriedade f(n + f(n))=2f(n) provamos que existem infinitos pontos fixos, o que implica que f é a função identidade. Veja só:
f(1 + f(1)) = 2f(1) <==> f(1+1) = 2 <==> f(2) = 2 (ponto fixo)
f(2 + f(2)) = 2f(2) <==> f(2 + 2) = 2*2 <==> f(4) = 4 (ponto fixo)
...
Podemos conjecturar que f(2^n) = 2^n. Vamos provar por indução finita, isto é, provar que admitindo a validade para um certo n, teremos então como conseqüência a validade para n+1 (e já mostramos que vale para um certo n).
f(2^(n+1)) = f(2*2^n) = f(2^n + 2^n) = f(2^n + f(2^n)) = 2f(2^n) = 2*2^n = 2^(n+1)
Bingo! Temos que 2^n é ponto fixo desta função. Vimos então que isso implica que f(n) = n, para todo n.
Mas e se m != 1? Seja g(n) = f(n) - m + 1 <==> f(n) = g(n) + m - 1
f(n + f(n)) = 2f(n) <==> g(n+f(n)) + m - 1 = 2*[g(n) + m - 1] <==>
<==> g(n + g(n) + m - 1) = 2g(n) + m - 1 (**)
Essa função g(n) é tal que g(1) = f(1) - m + 1 = 1 e também é estritamente crescente. Vale então o que disse acima para f no caso m=1: se g(a) = a, então g(n) = n para todo inteiro positivo menor do que e igual a a.
Vamos procurar então por pontos fixos de g:
g(1 + g(1) + m - 1) = 2g(1) + m - 1 <==> g(1 + 1 + m - 1) = 2*1 + m - 1 <==>
<==> g(m+1) = m+1
g((1+m) + g(1+m) + m - 1) = 2g(1+m) + m - 1 <==>
g(1+m + 1+m + m - 1) = 2(1+m) + m - 1 <==>
g(3m + 1) = 3m + 1
g((3m+1) + g(3m+1) + m - 1) = 2g(3m+1) + m - 1 <==>
g( 3m+1 + 3m+1 + m - 1) = 2(3m+1) + m - 1 <==>
g(7m + 1) = 7m + 1
...
Vamos conjecturar que g((-1+2^n)m + 1) = (-1+2^n)m + 1 e provar por indução. Vale para n = 1 (e também n=2). Vamos admitir que vale para um certo n e que isso implica validade para n+1:
g( (-1+2^n)m + 1 + g((-1+2^n)m + 1) + m - 1) = 2g((-1+2^n)m + 1) + m - 1 (por **)
<==> g( 2 ((-1+2^n)m + 1) + m - 1) = 2((-1+2^n)m + 1) + m - 1 <==>
<==> g( ((-2 + 2^(n+1))m + 2) + m - 1) = (-2 + 2^(n+1) + 1)m + 2 - 1
<==> g( (-2 + 2^(n+1) + 1)m + 1) = (-1 + 2^(n+1))m + 1
<==> g( (-1 + 2^(n+1))m + 1) = (-1 + 2^(n+1))m + 1
(verifique no papel, aqui é muito porco... bem que podia dar pra escrever diretamente em LaTeX no email... o que fiz foi substituir o número (-1+2^n)m no lugar do "n" da expressão (**), exatamente como fiz nos exemplos logo acima, de onde tirei a conjectura).
E chegamos onde queríamos: todo número da forma (-1+2^n)m + 1 é ponto fixo de g, logo g tem infinitos pontos fixos. Como g(1) = 1 e é estritamente crescente e tem infinitos pontos fixos g é a identidade (novamente, mesmo argumento para f no caso m=1; por quê?)
Ufa!
Temos então que:
f(n) = n + f(1) - 1, onde f(1) pode ser qualquer natural.
Caramba! será que tá certo isso, a menos de possíveis (e prováveis) erros de digitação? Alguém aí não quer verificar?
Abraço,
Bruno
On 6/3/06, Klaus Ferraz <klausferraz@yahoo.com.br > wrote:Tô precisando de ajuda nesses dois problemas.1)(Espanha-1998) Determine todas as funções estritamente crescentes f:N*-->N* tais que f(n+f(n))=2f(n), para todo n inteiro positivo.2)(Espanha-2000) Sendo N o conjunto dos inteiros positivos, prove que não existe f:N-->N tal que f(f(n))=n+1, pra todo n pertencente a NValeu.__________________________________________________
Fale com seus amigos de graça com o novo Yahoo! Messenger
http://br.messenger.yahoo.com/
--
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