Fraction with the smallest entries | India National Mathematical Olympiad 2005 Problem 2

[@failsmichael2542]

From the hypothesis we have 197a - 43b >= 1 (1) and 17b - 77a >= 1 (2). An initial bound for a is a >= 1. Using this we can deduce from inequality (2) that b >= 78/17 or b >= 5. From inequality (1) we have a >= (43 * 5 + 1)/197 or a >= 2. We can continue this procedure to "bootstrap" better lower bounds for a and b. The result is shown in the table below iteration || LB for a || LB for b 1 1 5 2 2 10 3 3 14 4 4 19 5 5 23 6 6 28 7 7 32 8 7 32 So we can't do better from iteration 7 onward, i.e we can only conclude that a >= 7 and b >= 32. Luckily, these values work.

[@stephenyip5827]

Could you share why 197a-43b>=1,but not 2 or other number?

[@MichaelRothwell1]

@@stephenyip5827 we know that a/b>43/197 so 197a>43b (since a, b>0), so 197a-43b>0. Since LHS is an integer, we get 197a-43b≥1.

[@stephenyip5827]

@@MichaelRothwell1 you are awesome man!

[@failsmichael2542]

Another idea: I think the problem has something to do with continued fraction. Note that 43/197 = [0; 4, 1, 1, 2, 1, 1, 3] 17/77 = [0; 4, 1, 1, 8] So to find a fraction in between with minimum denominator we take [0; 4, 1, 1, 3] which yields 7/32. This step needs major justification. :) Unfortunately, I forgot all the relevant theory.

[@failsmichael2542]

@@magnusPurblind Well, I have the same rough ideas but writing a fully rigourous solution is annoying because there are two continued fractions associated with a rational so we need to be careful with the inequalities and moreover, yes, we can intuitively see that appending more numbers bloats the denominator but I think to prove this we need to invoke the recurrence for the denominators of the convergents.

[@xactxx]

That's the way I worked it out too. The details are here: farrugiamaths.quora.com/What-is-the-fraction-having-the-smallest-numerator-and-denominator-that-rounds-to-the-nearest-given-decimal

[@jeanmarcbonici9525]

@@xactxx Thank you for your advice, I implemented the algorithm in wolfram language and it works on the two examples proposed by letsthinkcritically this one and this other kzbin.info/www/bejne/jKqYdp-uf8SIetU

[@prithujsarkar2010]

Feels good to see such problems back on this channel :3

[@srijanbhowmick9570]

I never knew that you can solve these problems algorithmically ! Thank you :)

[@beanhwak]

Let (5a-b)/(2a-9b) = k we can obtain a/b = (9/2) + (7/2)/(2k-1) then when b is smallest a/b take the largest possible value, so we require k to be the smallest among k = 3, 4, 5, 6, or 7. to maximize (7/2)/(2k-1).

[@TIXU-j5u]

Notice min(b)=[77a/17]+1, then [77a/17]+1

[@petersievert6830]

I mean, 32 is rather small, so it makes sense, we are fine with this number and it seems rather doable to proof, that with a smaller b, there is no solution. But is there an actual proof, this algorithm leads to the minimum solution? I mean, if we had received smth like 25/137 , it seems like being back to square one to proof there is no fraction with smaller b. Am I missing something? Thanks for any answer.

[@TheodoreBrown314]

As he says at the end, you need to prove it for smaller values afterwards. A bit tedious, but it could be worse

[@satyapalsingh4429]

Your method of finding minimum value of b is praiseworthy ,dear professor !!! Keep it up!!!

[@mathsman5219]

I solved it with floor equation, but never thought of this process. AMAZING 👍

[@sum2775]

5:24 Why 5a-b/2b-9a has to be an integer? Somebody help me understand😭

[@jofx4051]

I thibk because he has made the conparison to integer so it should be smallest integer, but I think he should explain another way so it doesn't confuse most of us

[@ha14mu]

It doesn't have to be, but picking an integer (the smallest integer) in that gap minimizes the value of b - and we're looking for the fraction with the smallest b

[@Epyxoid]

That's the instruction of the algorithm. I didn't know this algorithm, but it says "if the numbers (limits) have different integral part, pick the middle term to be the smallest possible integer" For me, it seems like this algorithm is magnifying the scale between the limits to a point where at least one of them is an integer. At that moment you can simply chose the smallest integer for the middle term and calculate the fraction, and maybe if that's not a sufficient solution you can restart with that being the upper limit... Or something like that. Good question btw.

[@davidblauyoutube]

It would help to show that you get the smallest denominator from choosing the smallest possible value of (5a-b)/(2b-9a). If you call this fraction x, so 2 < x < 8, then you can show that a/b = (2x+1)/(9x+5). It is possible that this fraction could reduce, so you need to check GCDs to be sure. As it turns out, the GCD of 2x+1 and 9x+5 is 1, so this fraction never reduces and (a,b) = (2x+1,9x+5) in lowest terms. Now you can reasonably claim that the minimum value of b happens for the minimum value of x, namely x=3 (which was "picked out of thin air" in the video) and thus a=7 and b=32.

[@failsmichael2542]

How do you know that x is an integer? If x is not an integer, how can we talk about the gcd of 2x + 1 and 9x + 5?

[@jofx4051]

It should be 3 just because a and b is natural and it is smallest number between 2 and 8

[@failsmichael2542]

@@jofx4051 But you implicitly assume that (5a - b)/(2b - 9a) is an integer. Why is it the case?

[@sum2775]

@@failsmichael2542 That's exactly what I'm thinking

[@failsmichael2542]

@@sum2775 Too much hand-waving. xD

[@sarvesh_soni]

Great Problem

[@Blabla0124]

I am missing a piece. You found a fraction between 43/197 and 17/77. How do you know this has minimum b?

[@晓阳-d3p]

but we need to find the minimum value of b ，not minimum value of （5a-b)/(2b-9a)

[@dugong369]

Sort-of proof that b=32 is the minimum: If you go 1 more step (subtract 2, take reciprocals), you get 7/4 > (2b-9a)/(23a-5b) > 1/6. Then set c/d=(2b-9a)/(25a-5b). We see c=d=1 satisfies the original inequality, since 7/4 > 1 > 1/6 (and neither c nor d can be zero). But also we can solve for a/b in terms of c and d: a/b = (2d+5c)/(23c+9d). Any other value for c or d (other than 1) will give a larger value for b. So b=32 is the minimum.

[@mathsandsciencechannel]

nice one sir. good content

[@ahmedt5734]

Good problem,would you give me the name of the software you’re using to write?

[@klausg1843]

I think we missed why you choose the fraction to be =3. I will try to explain: set (5a-b)/(2b-9a) = n, integer 3

[@klausg1843]

Hi, n does not “have” to be an integer. But as you see in my answer if you suppose n =p/q then the least b >=32. So you get the least b for n= an integer.

[@scaudelopusx105]

The minimum value of b is 32 .

[@shreyan1362]

Not gonna lie but I was stuck on this type of question and you uploaded a video 😄😊

[@vibhanarayan9668]

Mee too 🙃🙃🙃😉😉

[@hogwarts9879]

Unbelievable things that you given to us

[@ethanyap8680]

When I reached 1/8 < (2b-9a)/(5a-b) < 7/18 I did something different. Assuming 5a-b = c for some positive integer c then c/8 < 2b-9a < 7c/18 Observe c = 3 is the minimum such that we can let 2b-9a be an integer (a.k.a. 2b-9a=1) This leads us to solving 2b-9a=1,5a-b=3 => a=7,b=32

[@stephenyip5827]

Great video and thanks! It similar to a question that I want to solve ,could you advice any ways to solve? It would be great if you can make a video The problem is ,given a decimal number ,say 0.12345 How do we find a and b to approximate 0.12345 such that the fraction is as close as the decimal number? Obvious a equals 12345 and b equals 100000 will the the exact solution but I want a smaller number of a and b such that I don’t need to remember 2 large number That’s why I will impose a limitation on b ,where b

[@failsmichael2542]

Write the number as a continued fraction and take the largest convergent whose denominator is less than the required upper bound.

[@stephenyip5827]

@@failsmichael2542 perfectly solve my problem! Thanks👏🏻

[@shreyamjha3058]

Can you suggest some resources to get such problems and which country's math Olympiad problems should I do on Aops?

[@Mathcambo]

My channel also teaches a lot of math exercises. Give to you every day.

[@shreyamjha3058]

@@Mathcambo I saw them ,but is that content for math Olympiads?

[@Mathcambo]

Yes

[@mcwulf25]

If you had gone one step further you would only have 1 as the integer between the two fractions and 32a = 7b.

[@beautifulworld6163]

That was 😻

[@Peachu15838]

Can anybody please explain why the algorithm works?

[@beanhwak]

YES I CAN, HOPE YOU STILL NEED IT

[@ryanjagpal9457]

What on earth was he doing with the red writing? I mean why is it b-4a/a and why does the surroundings change

[@txikitofandango]

he's subtracting all sides by 4. b/a - 4 get a common denominator b/a -4a/a combine the fractions (b-4a)/a

[@ryanjagpal9457]

@@txikitofandango Why multiply by a?

[@ryanjagpal9457]

Also the rest of it just confusing i mean, no one is even gonna answer that in an exam

[@txikitofandango]

@@ryanjagpal9457 How do you add a fraction to a whole number?

[@ryanjagpal9457]

@@txikitofandango The whole number must have a denominator of 1

[@nickcheng2547]

197/43 > b/a > 77/17. 25/43 > (b-4a)/a > 9/17 43/25 < a/(b-4a) < 17/9 18/25 < (5a-b)/(b-4a) < 8/9 25/18 > (b-4a)/(5a-b) > 9/8 7/18 > (2b-9a)/(5a-b) > 1/8 18/7 < (5a-b)/(2b-9a) < 8 let x,y be integers s.t. x=5a-b, y=2b-9a then 18/7 < x/y < 8 and we want to minimize b = 9x+5y Since x/y > 0, and 9x+5y=b>0, x,y are postive. Since x>18y/7, as y increases, x also increases. Therefore y is equal to 1. 18/7 < x < 8, x = 3 min(b) = 9(3)+5(1) = 32 5a-32=3, a=7 It can be checked that 43/197 < 7/32 < 17/77

[@mathcanbeeasy]

"Therefore y=1" is incorect. You are lucky here that 32-5*1 is multiple of 9, but in other cases y is not 1. Practically you minimize x, not b with the assumption that y=1. To be more clear, in other case you may have 9*2+5*2 =2818y/7 than y is 1. Proving that b min is 32 is a loooot hard than you think. That's why the prove is not in the video.

[@21gamer50]

Try this take the mean of two numbers and u get the same ans

[@TechToppers]

Might be this is happening due to the bad bounds of the problem... I dunno exactly. Or it might be intended...

[@stefanopantaleoni9232]

If I understood what you meant... the mean value of 43/1997 and 17/77 is 3330/15169 (numerator and denominator already prime to each other). And 15169 > 32.

[@ryanjagpal9457]

I would’ve said the minimum of b is more than 77 and smaller than 197 so b is basically 77.1