wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Fractions
        
(Message started by: jollytall on Nov 6^th, 2013, 1:38pm)

Title: Fractions
Post by jollytall on Nov 6^th, 2013, 1:38pm

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.

Title: Re: Fractions
Post by towr on Nov 6^th, 2013, 10:35pm

[hide]Stern-Brocot Tree[/hide]?

Title: Re: Fractions
Post by jollytall on Nov 7^th, 2013, 12:24pm

Not really.
As said above, solve first the original question, before even thinking to generalise it.

Title: Re: Fractions
Post by towr on Nov 7^th, 2013, 12:45pm

on 11/07/13 at 12:24:38, jollytall wrote:

Not really.

Hehe.. Maybe. [hide]Because: continued fractions, 1 (http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree) + 1 (http://en.wikipedia.org/wiki/Golden_ratio#Alternative_forms) = 2[/hide]

Title: Re: Fractions
Post by jollytall on Nov 7^th, 2013, 12:59pm

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?

Title: Re: Fractions
Post by towr on Nov 7^th, 2013, 10:54pm

[hide]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 (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif=0) before we get to F(n)/F(n+1); we don't, so there isn't.[/hide]

Title: Re: Fractions
Post by jollytall on Nov 8^th, 2013, 10:18am

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.

Title: Re: Fractions
Post by towr on Nov 8^th, 2013, 12:20pm

For a completely general result, given two fractions q, r
[hide]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[/hide]

Title: Re: Fractions
Post by Grimbal on Nov 9^th, 2013, 1:19am

[hideb]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.
[/hideb]

Title: Re: Fractions
Post by jollytall on Nov 9^th, 2013, 6:09am

on 11/08/13 at 12:20:26, 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.

Title: Re: Fractions
Post by towr on Nov 9^th, 2013, 12:22pm

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.

Title: Re: Fractions
Post by jollytall on Nov 11^th, 2013, 12:40pm

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.