[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Problema Republica Tcheca
-----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 01:47
Assunto: Re: Problema Republica Tcheca
>
>-----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.
Fui pensar e descobri que esse método acima não é bom. O primero jeito que
eu sugeri está correto.
Há um terceiro modo. Seja g a função definida lá no começo do email. Sabemos
que, para n par,
soma(g(k),k=1...n)=[n/2]+[n/4]+[n/8]+[n/16]+...=n/2+[n/4]+[n/8]+[n/16]+...
Então,
soma(f(k),k=1...n)=n/2+n/2+[n/4]+[n/8]+[n/16]+...=n+[n/4]+[n/8]+[n/16]+...
Agora sim, com esta fórmula certamente achamos o n pedido.
Seja z(n)=n+[n/4]+[n/8]+[n/16]+...
Fazendo umas continhas, vemos que z(82308)=123457
Logo
soma(f(k),k=1...82308)=123457=soma(f(k),k=1...82307)+f(82308)=soma(f(k),k=1.
..82307)+f(82308)=
soma(f(k),k=1...82307)+2
Logo soma(f(k),k=1...82307)=123455 e n=82307
Espero que não esteja errado pois mandar um quarto email para consertar as
coisas já é muita vergonha...
Bruno
>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.
>>>
>>
>