Re: [obm-l] Problemas

[benedito <benedito@xxxxxxxxxxx>]

At 12:48 19/3/2003 -0300, you wrote:
>Caro Benedito e demais colegas:
>
>Gostaria de saber se alguém tem uma solução mais inteligente para o 2o.
>problema:
>
>"Seja  n =  2^31 . 3^19. Quantos são os divisores inteiros positivos de  n^2
>que são menores do que  n  mas  não dividem  n?"

Prezado Cláudio,

A resposta  é  589.
O raciocínio vale para o caso geral  em que  n = p^r . q^s,  onde  p, q são 
primos distintos.
É fácil ver que  n^2  possui  (2r+1).(2s+1)   divisores.
Para cada divisor  menor do que  n, existe um divisor correspondente maior 
do que n.
De sorte que, o número de divisores de  n^2  que são menores do que  n é:

    [(2r+1).(2s+1) - 1]/2 = 2rs + s + r

Como  n  possui  (r + 1).(s+1)  divisores, incluindo o próprio  n,  e  como 
todo divisor de  n é também divisor  de  n^2,  o número de 
divisores  de  n^2 que são menores do que  n  é igual  a:

         2rs + r + s - [(r+1) (s+1) - 1] = rs.

No problema, r = 31  e  s = 19. Portanto,  rs = 589.

Observações:
1) Essa belíssima solução acima é apresentada pelos autores Titu Adreescu/ 
Zuming Feng  no livro:
"102  Combinatorial Problems". Birkhäuser. 2003.
2) Meu livro preferido de Combinatória é o do Morgado. Se alguém conseguir 
resolver os problemas de lá, vai estar muito bem. Depois, pode pegar o 
livro do Titu Andreescu e se deliciar com problemas de dois tipos: 
Problemas Introdutórios  e Problemas Avançados.

Benedito

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================