List of fractions
Martha is writing down all (reduced) fractions with denominators up to 100, i.e. all the fractions d n such that 1 ≤ n < d ≤ 1 0 0 and gcd ( d , n ) = 1 . Then she sorts the fractions from smallest to greatest. Martha claims that, in this list, the two fractions 7 5 , 8 8 6 3 sit directly next to each other in this order.
Is this true?
Example:
The sorted list of all fractions with denominators up to 7 would be
7
1
,
6
1
,
5
1
,
4
1
,
7
2
,
3
1
,
5
2
,
7
3
,
2
1
,
7
4
,
5
3
,
3
2
,
7
5
,
4
3
,
5
4
,
6
5
,
7
6
.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Do you know of a simple explanation why we will have the property that b c − a d = 1 ?
(I swapped the order because you had a/b < c/d in the first line)
Log in to reply
By induction:
Let P D be the statement for a specific maximum denominator value D . If we include the values 0 / 1 and 1 / 1 at the beginning and end of the fraction list, statement P 1 is obviously true.
Now suppose we increase D to D + 1 . A new fraction will be inserted between two neighbors a / b , c / d only if b + d = D + 1 , and this new fraction will have the form q p = b + d a + c . Now p b − a q = ( a + c ) b − a ( b + d ) = c b − a d = 1 , and likewise c q − p d = 1 , showing that the pairs involving the new fraction also have the desired property; thus P D implies P D + 1 , and the principle if induction allows us to conclude that P D is true for any value of D .
These are known properties of any Farey pair , which is precisely what this problem is about. See also this interesting document .
In general, for positive a / b < c / d , we have b a < b + d a + c < d c .
This is also known as the Mediant inequality.
Log in to reply
Yes. In my solution I proved the first half of this inequality; the second half can proven analogously.
The answer is no. The fraction 7 + 8 8 5 + 6 3 = 9 5 6 8 lies between the two given values.
In general, for positive a / b < c / d , we have b a < b + d a + c < d c . Proof: cross-multiply. b a < d c ; a d < b c ; a b + a d < a b + b c ; a ( b + d ) < ( a + c ) b ; b a < b + d a + c , and similar for the other inequality (add c d to both sides).
In a list of all fractions with denominator d ≤ D , two successive fractions a / b , c / d will always have the property that b c − a d = 1 . It is easy to check that this is the case here: 5 × 8 8 − 6 3 × 7 = 1 . If this were not the case, we could immediately have answered "No".
In fact, from 5 × 8 8 − 6 3 × 7 = 1 we may even conclude that there is no intervening fraction with a denominator less than 88. However, as shown above, there is still room for a denominator greater than that...