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 é <[EMAIL PROTECTED]> =========================================================================