Re: [obm-l] Problemas

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

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?"

Eu fiz o seguinte:

d divide n^2 <==> d = 2^a * 3^b com 0 <= a < = 62 e 0 <= b <= 38
d não divide n ==> a > 31 ou b > 19
d < n ==> 2^a * 3^b < 2^31 * 3^19 ==>
a*log(2) + b < 31*log(2) + 19 (logs na base 3) ==>
b < (31*log(2) + 19) - (log(2))*a

Assim, o número pedido é igual ao número de elementos (a,b) de Z x Z que
satisfazem simultaneamente às três condições seguintes:
i) 0 <= a <= 62  E  0 <= b <= 38
ii) a >= 32  OU  b >= 20
iii) b < (31*log(2) + 19) - (log(2))*a

Ou seja, agora é só contar os pontos de um reticulado ("lattice") sujeitos
às condições acima.

Condições (i) e (ii) são tratadas facilmente (por inclusão-exclusão) ou
apenas dividindo em casos.

No entanto, a condição (iii), por ter coeficientes irracionais, não admite
(tanto quanto eu saiba) nenhum tipo de contagem que não seja a enumeração
braçal. O problema é que, para cada valor de a, precisariamos achar o valor
de:
[ (31*log(2) + 19) - (log(2))*a ] = [ (31 - a)*log(2) ] + 19  ( [x] = parte
inteira de x) e, devido à irracionalidade de log(2), a determinação dessa
parte inteira seria problemática.

Por computador, eu achei 589, e com certeza conseguiria chegar nesse
resultado com papel e lápis (e saco!) mas levaria um tempão.

Alguém tem uma solução mais inteligente?

Um abraço,
Claudio.

----- Original Message -----
From: "benedito" <benedito@digi.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Monday, March 03, 2003 9:31 PM
Subject: [obm-l] Problemas


>
> >Do livro   "102 Combinatorial Problems - From the Training of the  USA
IMO
> > > Team" , de Titu Andreescu e Zuming Feng - Birkhäuser. 2003,  dois
> > problemas
> > > interessantes:
> > >
> > > 1) Uma aranha tem uma meia e um sapato para cada uma de suas  8
pernas. De
> > > quantas maneiras diferente a aranha pode colocar as meias e os
sapatos,
> > > supondo  que , em cada perna, a meia tem de ser calçada antes do
sapato?
> > >
> > > 2) 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?
> > >
> > > (Nota:  n^2 =  n elevado a dois)
> > >
> > > Benedito Freire
>

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