Re: [obm-l] Parece mas nao eh
Oi salvador, Eu pensei um pouco sobre este problema, mas a unica conclusao a que eu ateh agora cheguei foi a mesma que o Claudio jah apresentou em uma outra mensagem. Sabemos que, se comecarmos com um x(1) 100, para algum n acabaremos tendo necessariamente que x(n) 100. Logo, para analisarmos o comportamento final da sequencia basta considerar os casos em que 1 = x(1) = 99. Eu tentei provar que, se sairmos de 11 = x(1) = 99 acabaremos chegando a um x(n) =9, mas nao fechei a prova. Podemos verificar que se x(n) tem 2 algarismos entao -25 = x(n+1) - x(n) = 63, mas isto nao me levou aa conclusao desejada. Voce seguiu algum caminho semelhante? Artur --- Salvador Addas Zanata [EMAIL PROTECTED] 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 = 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 = __ Do you Yahoo!? Yahoo! SiteBuilder - Free web site building tool. Try it! http://webhosting.yahoo.com/ps/sb/ = 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 =
[obm-l] Parece mas nao eh
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 = 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 =
Re: [obm-l] Parece mas nao eh
on 02.02.04 12:25, Salvador Addas Zanata at [EMAIL PROTECTED] 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 =
