Sent: Wednesday, August 28, 2002 12:27
AM
Subject: 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>
=========================================================================