Author |
Topic: Fractions (Read 2185 times) |
|
jollytall
Senior Riddler
   

Gender: 
Posts: 585
|
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 |
|
|
|
jollytall
Senior Riddler
   

Gender: 
Posts: 585
|
 |
Re: Fractions
« Reply #2 on: Nov 7th, 2013, 12:24pm » |
Quote 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: 
Posts: 13730
|
 |
Re: Fractions
« Reply #3 on: Nov 7th, 2013, 12:45pm » |
Quote Modify
|
on Nov 7th, 2013, 12:24pm, jollytall wrote: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: 
Posts: 585
|
 |
Re: Fractions
« Reply #4 on: Nov 7th, 2013, 12:59pm » |
Quote 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: 
Posts: 13730
|
 |
Re: Fractions
« Reply #5 on: Nov 7th, 2013, 10:54pm » |
Quote 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: 
Posts: 585
|
 |
Re: Fractions
« Reply #6 on: Nov 8th, 2013, 10:18am » |
Quote 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: 
Posts: 13730
|
 |
Re: Fractions
« Reply #7 on: Nov 8th, 2013, 12:20pm » |
Quote 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: 
Posts: 7527
|
 |
Re: Fractions
« Reply #8 on: Nov 9th, 2013, 1:19am » |
Quote 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: 
Posts: 585
|
 |
Re: Fractions
« Reply #9 on: Nov 9th, 2013, 6:09am » |
Quote 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: 
Posts: 13730
|
 |
Re: Fractions
« Reply #10 on: Nov 9th, 2013, 12:22pm » |
Quote 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: 
Posts: 585
|
 |
Re: Fractions
« Reply #11 on: Nov 11th, 2013, 12:40pm » |
Quote 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 |
|
|
|
|