[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] MMC
Oi, Rafael:
Eu achei uma solucao diferente mas que tambem nao se encaixa em nenhuma
alternativa.
Infelizmente, tambem encontrei um furo no seu raciocinio. Veja abaixo.
Um abraco,
Claudio.
on 09.06.03 18:57, Rafael at matduvidas@yahoo.com.br wrote:
> Se {r,s} representa o MMC dos inteiros positivos r e
> s, o número de ternos ordenados (a,b,c) de inteiros
> positivos qara os quais {a, b} = 1000, {b, c} = 2000 e
> {c, d} = 2000 é:
> a)50 b)70 c)100 d)170 e)200
>
Os unicos fatores primos de a, b, c, d sao 2 e 5 ==>
a = 2^x1 * 5^y1
b = 2^x2 * 5^y2
c = 2^x3 * 5^y3
d = 2^x4 * 5^y4
MMC(a,b) = 1000 ==> max(x1,x2) = max(y1,y2) = 3
MMC(b,c) = 2000 ==> max(x2,x3) = 4; max(y2,y3) = 3
MMC(c,d) = 2000 ==> max(x3,x4) = 4; max(y3,y4) = 3
x2 <= max(x1,x2) = 3 ==>
x3 = 4 (ja que max(x2,x3) = 4)
x2 = 3 ==>
x1 pode ser 0, 1, 2 ou 3 ==>
Sub-Total = 4*1*1 = 4 triplas (x1,x2,x3)
x2 = 0, 1 ou 2 ==>
x1 = 3 (ja que max(x1,x2) = 3) ==>
Sub-Total = 1*3*1 = 3 triplas (x1,x2,x3)
Resumindo:
(x1,x2,x3) pode ser (0,3,4), (1,3,4), (2,3,4), (3,3,4), (3,0,4), (3,1,4),
(3,2,4)
Total: existem 7 triplas (x1,x2,x3)
*****
y1 = 0, 1 ou 2 ==>
y2 = 3 (ja que max(y1,y2) = 3) ==>
y3 pode ser 0, 1, 2 ou 3 ==>
Sub-Total = 3*1*4 = 12 triplas (y1,y2,y3)
y1 = 3 ==>
y2 pode ser 0, 1, 2 ou 3
y2 = 0, 1 ou 2 ==> y3 = 3 (ja que max(y2,y3) = 3) ==>
Sub-Total = 1*3*1 = 3 triplas (y1,y2,y3)
y2 = 3 ==> y3 pode ser 0, 1, 2 ou 3
Sub-Total = 1*1*4 = 4 triplas (y1,y2,y3)
Total: existem 19 triplas (y1,y2,y3)
*****
Logo, existem 7*19 = 133 sextuplas (x1,x2,x3,y1,y2,y3), ou seja, 133 triplas
possiveis de inteiros positivos (a,b,c).
> Oi Pessoal!
>
> Devo estar esquecendo de alguma coisa ou não tem
> alternativa pra esta questão.
>
> Para dois números terem como MMC o número 1000, como:
> 1000 = 2³.5³
>
> Um dos números tem que ter pelo menos 2³ e o outro
> pelo menos 5³.
Nao necessariamente. Por exemplo, MMC(2^3*5^3,2*5) = 1000 mas 2*5 nao eh
divisivel nem por 2^3 nem por 5^3.
> Então comecei pelo menor e fui vendo
> quem podia ser seu par para terem MMC = 1000:
> 2³ e 5³
> 2³ e 5³.2
> 2³ e 5³.2²
> 2³ e 5³.2³
>
> Depois, continuando a ter como referência o número com
> 2³, podemos ter 2³.5, 2³.5² e por fim 2³.5³ que é o
> próprio 1000:
> 2³.5 e 5³
> 2³.5 e 5³.2
> 2³.5 e 5³.2²
> 2³.5 e 5³.2³
>
> 2³.5² e 5³
> 2³.5² e 5³.2
> 2³.5² e 5³.2²
> 2³.5² e 5³.2³
>
> Mas se você pegar o 1000, pode pegar todos os seus
> divisores que o MMC será 1000. 1000 tem 16 divisores
> (1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200,
> 250, 500, 1000)
>
> Então formará 16 pares cujo MMC é 1000. Só não podemos
> escquecer que já tínhamos 12 pares cujo MMC dava 1000
> e entre esses apareceram 3 pares onde o 1000 era um
> dos números. Então na verdade não são 16, mas 13 novos
> pares, que juntando com os 12 que já existiam
> totalizam 25.
>
> Para dois números terem MMC igual a 2000, um deles tem
> que ter o fator 2^4 e o outro o fator 5³. Mas como
> pelo problema, nossos pares têm elementos cujo MMC tem
> que dar 1000 com um número e 2000 com outro, não
> poderemos colocar nenhum número que tenha 2^4 como
> fator porque 1000 não é múltiplo de 2^4 então nunca
> seria MMC. Assim, o único divisor de 2000 que
> poderemos usar é o próprio 2000 porque aí o MMC será
> 2000 quando estiver com ele e ele tem o 2^4. Os outros
> números podem ser quaisquer divisores de 2000 (1, 2,
> 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 125, 200,
> 250, 400, 500, 1000, 2000)
>
> Mas como esses números têm que ter MMC igual a 1000,
> só poderão entrar os divisores e 1000. Ou seja, os 3
> números a, b e c só poderão ser formados pelo 2000 e
> mais um daqueles pares que vimos que têm MMC = 1000.
>
> Já vimos que são 25 pares, mas temos que contar as
> permutações porque o problema falou em pares
> ordenados. Então são 6 permutações para cada conjunto
> de 3 números. A não ser o conjunto {1000, 1000, 2000}
> que tem só 3 permutações:
> = 24.6 + 3
> = 144 + 3
> = 147 ternos ordenados.
>
> O que foi que esqueci???
>
> Abraços,
>
> Rafael.
>
> _______________________________________________________________________
> Yahoo! Mail
> Mais espaço, mais segurança e gratuito: caixa postal de 6MB, antivírus,
> proteção contra spam.
> http://br.mail.yahoo.com/
> =========================================================================
> 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
> =========================================================================
>
=========================================================================
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
=========================================================================