Re: [obm-l] FUNÇÃO

[Ricardo Bittencourt <ricbit@xxxxxxxxxxxx>]

Andre wrote:

> 
> Seja f: N* - N* um fç tal que:
>  
> I) f(1)=1
> II)f(2n+1)=f(2n) + 1
> III)f(2n)=3f(n)
> O valor de f(1992) é:

	Ah, essa aqui é uma função que troca bits por trits!
Pra achar o valor da função, você escreve o número em binário,
copia pra ternário, e depois desconverte pra decimal

1992 em binário = 11111001000

11111001000 em ternário =
3^10+3^9+3^8+3^7+3^6+3^3 =
88236

	Pra demonstrar é só fazer indução nos bits de n,
mas a notação fica complicada:

base de indução: f(1)=f(2^0)=3^0=1 ok

passo indutivo:

	Suponha que pra todo n<2^(x+1) vale
f(ax*2^x+...+a1*2^1+a0*2^0)=ax*3^x+...+a1*3^1+a0*3^0
onde todos os an são 0 ou 1 (n pode ser escrito de
uma única maneira desse jeito)

	Se pegarmos agora um k tal que
2^(x+1)<=k<2^(x+2), então esse k poderá ser
escrito como k=1*2^(x+1)+ax*2^x+...+a1*2^1+a0*2^0.

	Se a0=0, então k é par e k=2p => f(2p)=3f(p) =
3*f(1*2^x+ax*2^(x-1)+...+a1*2^0). O número aí
dentro está na faixa que foi suposta válida, então

3*f(1*2^x+ax*2^(x-1)+...+a1*2^0)=
3*(1*3^x+ax*3^(x-1)+...+a1*3^0)=
1*3(x+1)+ax*3^x+...+a1*3^1 (+a0*2^0 pois a0=0)
e isso concluí pra a0=0.

	Se a0=1, então k é ímpar e k=2p+1 =>
f(2p+1)=f(2p)+1 => f(2p+1)=3f(p)+1 =>
3*f(1*2^x+ax*2^(x-1)+...+a1*2^0)+1. O número aí
dentro é o mesmo do caso anterior, então:

3*f(1*2^x+ax*2^(x-1)+...+a1*2^0)+1=
3*(1*3^x+ax*3^(x-1)+...+a1*3^0)+1=
1*3(x+1)+ax*3^x+...+a1*3^1 +a0*3^0 (pois a0*3^0=1)
e isso concluí pra a0=1 e completa a indução.

----------------------------------------------------------------
Ricardo Bittencourt                   http://www.mundobizarro.tk
ricbit@700km.com.br           "tenki ga ii kara sanpo shimashou"
------ União contra o forward - crie suas proprias piadas ------
=========================================================================
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
=========================================================================