Re: [obm-l] Parece mas nao eh

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 02.02.04 12:25, Salvador Addas Zanata at sazanata@ime.usp.br wrote:

> 
> Oi gente,
> 
> Acabei de resolver um probleminha, que a primeira vista me pareceu
> impossivel, mas na verdade eh facil.
> 
> 
> Dado um natural, digamos 13, o proximo eh 1²+3²=10, depois vem 0²+1²=1 e
> ficamos no 1,1,1,....
> 
> 
> Se comecarmos com 4, vamos para 16, depois 37, 58, 89, 145, 42, 20, 4, 16,
> 37, 58, 89,.... , 20, 4, 16,.... e indefinidamente nesta sequencia.
> 
> 
> O problema eh: Prove que todo numero, ou termina no 1, ou nessa seq.
> 4,16,37,58,89,145,42,20,4,...
> 
> 
> Disse que parecia impossivel, pois me lembrou na hora o seguinte problema:
> 
> se n for par, divida por 2, se for impar, multiplique por 3 e some 1.
> 
> 
> Exemplo:
> 
> 
> 7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4,2,1,...
> 
> 
> Prove que todo n converge para o loop 4,2,1,4,2,1,...
> 
> 
> Esse esta em aberto, e pelo que eu sei longe de ser resolvido.
> 
> 
> 
> Abraco,
> 
> Salvador
> 
> 
Oi Salvador:

Legal, esse ai!

A sequencia comeca com um x(1) arbitrario e eh dada por:
x(n+1) = soma dos quadrados dos algarismos de x(n).

Eu consegui provar que x(n) eh eventualmente periodica.

Pra comecar, repare que se x(n) >= 100, entao x(n+1) < x(n), pois se x(n) =
a_0 + a_1*10 + ... + a_r*10^r, com r >= 2, entao x(n+1) = a_0^2 + a_1^2 +
... + a_r^2 e, portanto:
x(n) - x(n+1) = a_0*(1 - a_0) + a_1*(10 - a_1) + ... + a_r*(10^r - a_r).
No pior caso, teremos:
a_0 = 9 ==> a_0*(1 - a_0) = -72;
a_1 = 0 ==> a_1*(10 - a_1) = 0;
a_2 = 1 ==> a_2*(100 - a_2) = 99;
a_k = 0, para k > 2;
de forma que x(n) - x(n+1) >= -72 + 99 = 27.
Isso quer dizer que existem infinitos n para os quais x(n) tem 1 ou 2
algarismos.

Como existem apenas 99 inteiros positivos de 1 ou 2 algarismos, concluimos
que existem r e s tais que r < s e x(r) = x(s) = inteiro positivo de 2
algarismos. Ou seja, a sequencia x(n) eh eventualmente periodica.

Agora soh falta provar que sempre existira n tal que x(n) = 1 ou x(n) = 4.
Eh claro que tem a demonstracao bracal, mas essa eu me recuso...

Um abraco,
Claudio.



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