Re: [obm-l] Problemas

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Caro Benedito:

Muito obrigado pela resposta e pelas dicas de livros.

Eu realmente não tinha me dado conta deste pequeno fato:
"Para cada divisor de n^2 menor do que  n, existe um divisor correspondente
maior do que n".
A demonstração é fácil:
Se n^2 = a*b com a < b, então, a < n.
Caso contrário, teríamos a >= n ==> a*b > n^2 ==> contradição
Naturalmente, a < n ==> b = n^2/a > n.
Assim, como n^2 tem um número ímpar de divisores, podemos formar pares
ordenados (a,b) de divisores de n^2 diferentes de n tais que a < n < b.
Dessa forma, estabelecemos uma bijeção entre o conjunto dos divisores de n^2
menores do que n e o conjunto dos divisores de n^2 maiores do que n.

O resto da solução (realmente belíssima) segue facilmente.

Um grande abraço,
Claudio.


----- Original Message -----
From: "benedito" <benedito@digi.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Wednesday, March 19, 2003 8:00 PM
Subject: Re: [obm-l] Problemas


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

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