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