Re: Problema Republica Tcheca

["Bruno Leite" <bruleite@xxxxxxxxxx>]

Oi Henrique

Vamos definir a função g:N->N, mais natural e mais fácil de se lidar, da
seguinte forma:
g(n)=k pra todo inteiro com n =2^k*l , onde k eh um numero natural e l eh
impar. veja que ela é quase igual a função f, só diferindo nos ímpares
(f(impar)=1 e g(impar)=0).

Agora vamos calcular os valores iniciais de g e dispo-los de uma forma
diferente.

Considere a árvore abaixo:

g(2)
g(3)                         g(4)
g(5)         g(6)           g(7)            g(8)
g(9) g(10) g(11) g(12) g(13) g(14) g(15) g(16)

Cada linha tem 2^(n-1) elementos. Vamos dizer que g(2) é pai de g(3) e g(4),
assim como g(5) é pai de g(9) e g(10) e g(8) é pai de g(15) e g(16). de modo
geral, g(n) é pai de g(2n-1) e g(2n).

Substituindo pelos valores de g:

1
0           2
0    1     0    3
0 1 0 2 0 1 0 4

É fácil ver e provar que se g(n)=k, então os filhos de g(n) valem 0 e k+1. A
partir daí vc sabe dizer quanto dá a soma de cada linha?

Não vou terminar o problema por preguiça e porque tenho certeza que agora
não falta muito, até porque é fácil relacionar as somas de f com as de g...

Bruno Leite
brleite@ime.usp.br
bruleite@uol.com.br
http://www.ime.usp.br/~brleite

PS Aliás toda a lista de "Olimpíadas ao redor do mundo" é interessante.
Gostaria de saber se alguém sabe fazer o 72.

-----Mensagem original-----
De: Henrique Lima <santanahenrique@hotmail.com>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Quinta-feira, 19 de Julho de 2001 00:07
Assunto: Problema Republica Tcheca


>     gostaria de ajuda nesse problema
>
>Uma função f:N->N é tal q f(n)=1 se n eh ímpar e f(n)=k pra todo inteiro
par
>n =2^k*l , onde k eh um numero natural e l eh impar. determine o maior
>natural n para o qual:
>  f(1)+f(2)+...+f(n)=<123456
>
>    valeuz
>
>_________________________________________________________________________
>Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.
>