Re: [obm-l] Eureka 18 e Olimpiada Cearense

["Will" <will@xxxxxxxxxx>]

Não consegui resolver, mas andei um tanto...
Mais abaixo...

----- Original Message -----
From: "Claudio Buffara" <claudio.buffara@terra.com.br>


Eureka 18:

Problema Proposto no. 83:
Seja N = {0,1,2,3, ..}.
Determine quantas funções de N em N satisfazem:
f(2003) = 2003,
f(n) <= 2003 para todo n <= 2003, e
f(m + f(n)) = f(f(m)) + f(n) , para todo m,n pertence N.

*****

Passo a passo, pra não ficar impossível de entender.

Afirmação 1:   f(0) = 0
Dem:
f(0 + f(0)) = f(f(0)) + f(0)
f(f(0)) = f(f(0)) + f(0)
0 = f(0)

Afirmação 2:  f(n) = f(f(n)) para todo n natural
Dem:
f(n + f(0)) = f(f(n)) + f(0)
f(n) = f(f(n))

Afirmação 3: Se f(n) = k para algum k natural , Então f(k)=k
Dem:
f(n) = f(f(n))
f(n) = f(k)

Afirmação 4:  Se f(n) = n para algum n natural, Então f(kn) = kn para todo k
natural
Dem: (indução em k)
hipotese: f((k-1)n) = (k-1)n
f(n + f((k-1)n)) = f(n) + f((k-1)n)
f(n + (k-1)n) = n + (k-1)n
f(kn) = kn

Afirmação 5: f(1) = 0 ou 1 ou 2003
Dem:
Suponha f(1) = b , onde 1 < b < 2003
Então f(b) = b (afir 3)
e também f(kb) = kb (afir 4)
Seja k o maior inteiro tal que kb < 2003
f(1 + f(kb)) = f(1) + f(kb)
f(1 + kb) = b + kb  > 2003 (absurdo)

Afirmação 6: Se f(1) = 1 , então f(n) = n para todo n
Dem: Decorre diretamente da afirmação 4.

Suspeito que as outras possibilidades são arranjos de 0´s e 2003´s , o que
dariam mais umas 2^2002 funçoes, mas tá tarde e eu tenho uma prova pra fazer
amanhã de manhã e a cabeça tá pifando. (além do que, acaba de chegar um mail
do Domingos, vou olhar a solução dele e matar a curiosidade...)

Saudações
Will



=========================================================================
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
=========================================================================