[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Re:



Ops, quis dizer menor.
 
Não existe maior pois:
7/10 < (7a + 11b)/(10a + 15b) < 11/15  ,  a, b>0
p=7a + 11b
q =10a + 15b
Podemos aumentar a e b o quanto quisermos para obter q arbitrariamente grande.
 
A desigualdade acima me deu uma idéia para encontrar um limite inferior para q.
q = 10a + 15b.
 
Se a e b fossem inteiros livres, teríamos que o menor valor inteiro positivo que q poderia assumir é mdc(10, 15)=5
então q>=5
Mas q=5 dá a=-1 e b=1, que viola a, b>0
Como essa solução é única para q=5, temos que q>5
 
Assim precisaríamos apenas testar q=6 e q=7
 
Para chegar nas conclusões acima me baseei em teoremas sobre mdc que não sei se têm nomes. Tirei do livro "Introduction to Algorithms" de Cormen, Leiserson e Rivest.
 
Até mais
 
Vinicius Fortuna
----- Original Message -----
Sent: Tuesday, August 27, 2002 11:33 PM
Subject: Re: [obm-l] Re:

Maior?
Morgado

Vinicius José Fortuna wrote:
020301c24e37$9d078a00$0401010a@xt type="cite">
Considerando que se procura o maior valor de q.

Temos:
7/10 < (7+11)/(10+15) = 18/25 < 11/15
7/10 < (7+18)/(10+25) = 25/35 = 5/7 < 18/15 < 11/15

Por enquanto temos q=7 em 5/7. Precisamos verificar se é o melhor possível.

Para isso testamos todos os q, 1<=q<7
7/10 < p/q < 11/15
q*7/10 < p < q*11/15

p/ q=1
7/10 < p < 11/15
-> não existe p

p/ q=2
14/10 < p < 22/15
4/10 < p-1 < 7/15
-> não existe p

p/ q=3
21/10 < p < 33/15
1/10 < p-2 < 3/15
-> não existe p

p/ q=4
28/10 < p < 44/15
8/10 < p-2 < 14/15
-> não existe p

p/ q=5
35/10 < p < 55/15
5/10 < p-3 < 10/15
-> não existe p

p/ q=6
42/10 < p < 66/15
2/10 < p-4 < 6/15
-> não existe p

Só para confirmar:
p/ q=7
49/10 < p < 77/15
4+ 9/10 < p < 5 + 2/15
como p é inteiro:
5 <= p <=5
-> p=5

Até mais

Vinicius Fortuna
IC- Unicamp

----- Original Message -----
From: "Bruno F. C. Leite" <bruleite@terra.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, August 27, 2002 3:54 AM
Subject: [obm-l] Re:


At 18:37 26/08/02 -0300, you wrote:
Será que alguém poderia me ajudar neste problema:

Se p e q são inteiros positivos tais que 7/10 < p/q < 11/15 ,qual o maior
valor que q pode assumir?


Obrigado.
Acho que se trocarmos "maior" por "menor", o enunciado fica mais
interessante. Aí, saber frações de Farey (ou dar um bom chute) pode ser
útil (mas não imprescindível)

Bruno Leite
http://www.ime.usp.br/~brleite


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