wu :: forums
« wu :: forums - Fractions »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 4:34am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: william wu, SMQ, Grimbal, Eigenray, Icarus, towr, ThudnBlunder)
   Fractions
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Fractions  (Read 2159 times)
jollytall
Senior Riddler
****





   


Gender: male
Posts: 585
Fractions  
« on: Nov 6th, 2013, 1:38pm »
Quote Quote Modify Modify

There are two fractions, 34/55 and 55/89. We are looking for a third fraction of positive integers a/b, where 34/55>a/b>55/89. What is the smallest b where it is possible.
Once you have the solution, can you proof it generally?
Do not ask now, how to generalise the question. Once you have the solution to the first question, you will know the generalisation part too.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Fractions  
« Reply #1 on: Nov 6th, 2013, 10:35pm »
Quote Quote Modify Modify

Stern-Brocot Tree?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
jollytall
Senior Riddler
****





   


Gender: male
Posts: 585
Re: Fractions  
« Reply #2 on: Nov 7th, 2013, 12:24pm »
Quote Quote Modify Modify

Not really.
As said above, solve first the original question, before even thinking to generalise it.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Fractions  
« Reply #3 on: Nov 7th, 2013, 12:45pm »
Quote Quote Modify Modify

on Nov 7th, 2013, 12:24pm, jollytall wrote:
Not really.
Hehe.. Maybe. Because: continued fractions, 1 + 1 = 2
« Last Edit: Nov 7th, 2013, 12:46pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
jollytall
Senior Riddler
****





   


Gender: male
Posts: 585
Re: Fractions  
« Reply #4 on: Nov 7th, 2013, 12:59pm »
Quote Quote Modify Modify

I still do not see the Stern-Brocot tree in it, but you might be right one way. Since the two fractions are A/B and B/C=B/(A+B) they are even on different levels of the tree.
The 1+1=2 is much closer to the answer. I guess you have the answer to the first question and the quess for the generalisation. But how to prove that that is the smallest b?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Fractions  
« Reply #5 on: Nov 7th, 2013, 10:54pm »
Quote Quote Modify Modify

We're going left-right-left-right down the Stern-Brocot tree, which tells us a number of things. For one, each fraction lies between the previous two. Secondly, for any given precision there are no better approximations (with smaller divisor) for any real numbers than the ones we encounter on that path. So in particular if there were some a/b with smaller b, then we should encounter that in the Stern-Brocot tree if we search for it (=0) before we get to F(n)/F(n+1); we don't, so there isn't.
« Last Edit: Nov 7th, 2013, 10:58pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
jollytall
Senior Riddler
****





   


Gender: male
Posts: 585
Re: Fractions  
« Reply #6 on: Nov 8th, 2013, 10:18am »
Quote Quote Modify Modify

Now I see, thanks.
I approached it from the Fibonacci series. These fractions are two consequtive ratios of two consequtive Fibonacci numbers, converging to Phi. The solution is the third consequtive ratio.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Fractions  
« Reply #7 on: Nov 8th, 2013, 12:20pm »
Quote Quote Modify Modify

For a completely general result, given two fractions q, r
if q and r are parent and child in the SB-tree, then their mediant has the least denominator of all fractions between q and r
if q and r are ancestor and descendant in the SB-tree (but not parent-child), then the ancestor's child has the least denominator of all fractions between q and r
if q and r are not ancestor and descendant in the SB-tree, then their lowest common ancestor has the least denominator of all fractions between q and r
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Fractions  
« Reply #8 on: Nov 9th, 2013, 1:19am »
Quote Quote Modify Modify

hidden:
More about the Stern-Brocot tree:
For any interval (a,b), if you go down the SB tree to find a p/q in [a,b], (i.e. if the node is >=b, go left, if it is <=a, go right, else return the node), then you find the fraction p/q that has the smallest denominator q but also the smallest numerator p among all fractions in (a,b).
It doesn't matter whether a and b are rational or not.
« Last Edit: Nov 12th, 2013, 2:43am by Grimbal » IP Logged
jollytall
Senior Riddler
****





   


Gender: male
Posts: 585
Re: Fractions  
« Reply #9 on: Nov 9th, 2013, 6:09am »
Quote Quote Modify Modify

on Nov 8th, 2013, 12:20pm, towr wrote:

if q and r are ancestor and descendant in the SB-tree (but not parent-child), then the ancestor's child has the least denominator of all fractions between q and r

 
Can ancestor-descendant be left-right down the tree? If yes, and the second descendant is a step to the other direction then the first dscendant is, then the first descendant is not even between q and r. It might be that none of the ones in between are falling into the interval. In this case we are back to the mediant.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Fractions  
« Reply #10 on: Nov 9th, 2013, 12:22pm »
Quote Quote Modify Modify

For some odd reason I only considered left-only or right-only descendants. Which is silly.
You're right, if the second descendant is in the other direction than the first, we need the mediant again.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
jollytall
Senior Riddler
****





   


Gender: male
Posts: 585
Re: Fractions  
« Reply #11 on: Nov 11th, 2013, 12:40pm »
Quote Quote Modify Modify

I am afraid, even this is not true.
If there are Left-s and Right-s in the Ancestor-Descendant chain, then the smallest denominator in-between is the highest element under the Ancestor from which we go the same direction as from the Ancestor. E.g. if the tree is LRRLRLRLR, then 4th element is the smalest denominator, as this is the first where we went left like from the first. This includes the all-Left or all-Right cases where indeed the second in the chain is the one.
If there is no such an element in between at all (e.g. LRRRR), then the mediant is to be used as you said in the last post.
« Last Edit: Nov 11th, 2013, 12:41pm by jollytall » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board