Re: Problema Republica Tcheca

["Bruno Leite" <bruleite@xxxxxxxxxx>]

-----Mensagem original-----
De: Bruno Leite <bruleite@uol.com.br>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Quinta-feira, 19 de Julho de 2001 00:46
Assunto: Re: Problema Republica Tcheca


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

Não sei se eu fui claro, então vou dar uma consertada.

A soma da i-esima linha da arvore da função g é 2^(i-1) (indução)

Então a soma das linas da arvore até a linha k é 1+2+4+...+2^(k-1)=2^k -1

Se fizéssemos a arvore de f em vez de g, todos os zeros virariam uns. Então
a soma até a linha k é
2^k + 2^(k-1) - 1, pois há 2^(k-1) zeros até a linha k ( vamos lembrar que
f(1) não está na árvore, mas é um zero que se converte em um, e deve ser
contado)


Isso mostra que f(1)+f(2)+...+f(2^k)=2^k + 2^(k-1) - 1
Em particular, f(1)+f(2)+...+f(2^16)=2^16 + 2^15 - 1=98303

Logo sabemos que o n do problema está entre 2^16 e 2^17. Agora só falta
somar o começo da linha 17 até dar 123456.

Agora não é difícil terminar.

Estou vendo **agora** que tem outro modo de se fazer este problema: fixe n.
Quantos k, de 1  a n, satisfazem
f(k)=1? e f(k)=2? Seja h_i o número de inteiros de 1 a n com f(k)=i. Então

f(1)+...+f(n)=h_1 + 2h_2 + 3h_3 +... ( a soma é infinita, mas a partir de um
ponto os termos sao todos nulos)

Com essa formula em mente podemos achar por tentativa  e erro o valor de n
pedido. Vou fazer as contas com mais cuidado no papel, mas acredito que isso
está certinho.

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



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