All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Minimizing the Denominator (Posted on 2019-03-08) Difficulty: 3 of 5
Let a and b be positive integers such that 43/197 < a/b < 17/77. Find the minimum possible value of b.

No Solution Yet Submitted by Danish Ahmed Khan    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Analytic Solution Comment 3 of 3 |
If you know about continued fractions then this is actually a pretty straightforward problem. Express 43/197 and 17/77 as continued fractions:
43/197: [0;4,1,1,2,1,1,3]
17/77: [0;4,1,1,8]

Then make a new continued fraction keeping matching terms and where the terms differ then increment the smaller one by 1 and stop.
Then the continued fraction for a/b becomes [0;4,1,1,3].  This is the continued fraction for 7/32.

What if you are like me and barely know of continued fractions? There is a fairly effective algorithm that can find the answer to the question with not too much work.

Start with r1 < a/b < r2 (all values assumed to be positive)

Is there at least one integer in the interval from r1 to r2?  

If so set a/b equal to the smallest such integer and solve for a and b.

If not then take the reciprocals of everything (r1, r2, and a/b).  Find the largest integer less than the new interval. 
Then make a new r1, r2, and a/b fraction by subtracting that integer and head back to the start.

For this problem we start with 43/197 < a/b < 17/77

There is no integer in the interval.  
Then 1/r2=77/17 and 1/r1=197/43 and 1/(a/b)=b/a.  
4 is the largest integer less than 77/17.  
Then 9/17 < a/(b-4a) < 25/43

There is no integer in the interval.  
Then 1/r2=43/25 and 1/r1=17/9 and 1/(a/(b-4a))=(b-4a)/a.  
1 is the largest integer less than 43/25.  
Then 18/25 < (5a-b)/(b-4a) < 8/9

There is no integer in the interval.  
Then 1/r2=9/8 and 1/r1=25/18 and 1/((5a-b)/(b-4a))=(b-4a)/(5a-b).  
1 is the largest integer less than 9/8.
Then 1/8 < (2b-9a)/(5a-b) < 7/18

There is no integer in the interval.  
Then 1/r2=18/7 and 1/r1=8 and 1/((2b-9a)/(5a-b))=(5a-b)/(2b-9a).  
2 is the largest integer less than 18/7.
Then 4/7 < (23a-5b)/(2b-9a) < 6

There is an integer in the interval.  The smallest is 1.
Then (23a-5b)/(2b-9a)=1 reduces to 32a=7b, which makes a/b=7/32.

Note, if we take some other integers in this interval, like 2, we get a different but not ideal answer.  (23a-5b)/(2b-9a)=2 reduces to 41a=9b, implying a/b=9/41, which is precisely the second-best answer that Charlie's program found.

  Posted by Brian Smith on 2021-05-01 10:51:44
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information