Re: obm 2000

["Eduardo Casagrande Stabel" <dudasta@xxxxxxxxxxxx>]

Tente encontrar s(n-1) dentro de s(n), escrevendo da seguinte maneira:

SUM{ n mod k , k=1...n }=
SUM{ n mod k , k=1...(n-1) }

Isso por que o ultimo termo eh "n mod n = 0".
Agora tente desmembrar n mod k, em (n-1) mod k + 1, e veja que:
n mod k = (n-1) mod k + 1 se e somente se k nao divide n;
e que se k divide n, entao n mod k = 0

Dai reescreva o ultimo somatorio como:

SUM{ (n-1 mod k) + 1 , k=1...n } - SUM{ (n-1 mod k) + 1, k divide n e k<n }

Veja que sempre que k divide n, (n-1) mod k = k-1, e podemos reescrever o
somatorio como:

SUM{ (n-1 mod k) + 1 , k=1...n-1 } - SUM{ k , k divide n e k<n }=
SUM{ (n-1 mod k), k=1...n-1 } + (n-1) - SUM{ k , k divide n e k<n }

Note que SUM{ k , k divide n e k<n } = o(n) - n, pois temos todos os
divisores positivos de n exceto o proprio n. Segue que o somatorio da:

SUM{ (n-1 mod k), k=1...n-1 } + (n-1) - ( o(n) - n ) =
SUM{ (n-1 mod k), k=1...n-1 } + (2n-1) - o(n) =
s(n-1) + (2n -1) - o(n)

Ou seja:
s(n) = s(n-1) + (2n-1) - o(n)

Segue que s(n) = s(n-1) se e somente se (2n-1) - o(n) = 0, ou seja, se n eh
quase perfeito.

Quanto a questao que voce levanta eu nao sei dizer. Talvez seja um problema
em aberto.

Esta certa essa soluccao?

Obrigado!
Eduardo Casagrande Stabel.




From: <thiago-sobral@bol.com.br>
>   A respeito do problema 2 da 3a fase da obm
> nivel 3, do ano passado:
>
>  PROBLEMA 2:
>
> Seja o(n) a soma de todos os divisores
> positivos de n,  onde n é um inteiro positivo
> (por exemplo, o(6)=12 e o(11)=12 e Dizemos
> que n é quase perfeito se o(n)=2n-1 (por
> exemplo, 4 é quase perfeito, pois o(4) = 7).
> Sejam s(n)=sum(n mod k), k=1 a n (por
> exemplo: s(6) = 0 + 0 + 0 + 2 + 1 + 0 = 3 e s
> (11) = 0 + 1 + 2 + 3 + 1 + 5 + 4 + 3 + 2 + 1
> + 0 = 22).
>
> Prove que s(n)=s(n-1) sss n é quase perfeito.
>
> Na prova, conjecturei que isso aconteceria
> somente para n sendo potencia de 2. Alguem
> poderia provar ou desprovar isso?
>
> [],
>
> Thiago Sobral
>
>
>
>
>
> __________________________________________________________________________
> Acesso pelo menor preço do mercado! R$ 14,90 nos 3 primeiros meses!
> ASSINE AGORA! http://www.bol.com.br/acessobol/
>
>
>