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