Re: [obm-l] Olimpiada

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

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 N

 

Valeu.

__________________________________________________
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