I think the last step should add something like this: Let (b-5a)/(6a-b) = p/q for some integers p, q with 11/5 < p/q < 43/9, which simplifies to a/b = (p+q)/(6p+5q) Now we want to minimize 6p + 5q. If q = 1, then p = 3 or 4 If q >= 2, then p > 11q/5 >= 22/5, hence p >= 5 which clearly makes 6p+5q larger than the previous case Hence, we can conclude that q = 1 and p = 3 is the minimum, that is, b = 23
@@wesleydeng71 I actually wrote the exact same comment and then deleted it after thinking. I think its not necessary that p,q be co-prime (b-5a)/(6a-b) = p/q is the definition of p,q But for example, the minimum "b" and corresponding "a" could be such that gcd(b-5a, 6a+b) is not 1 MakST's proof is complete without making the restrictive assumption about gcd(p,q)=1
Can you please explain why you consider only integer values for (b - 5a)/ (6a -b) ? I am not getting the rationale here. Am I missing out on something critical ?
Suppose (b-5a) / (6a-b) = k, where k€Q From this, a/b = (1+k) / (6k+5) ==> a = 1+k and b = 6k+5 Then k = a-1 ==> k is a natural number, given that 'a' is natural and k0.
@@霍金本人 of course p+q k. In fact, k=p/q Please consider m/n = 2/3 We are looking for two integers m, n>0, satisfying this equation, so we can state with no error that m=2 and n=3. On our case, a/b = (1+k) / (6k+5) and we can state with no error that a = 1+k and b= 6k+5 and we find out that k is integer.
If we have (b-5a)/(6a-b)=p/q b=5a+ a*(p/(q+p)) As we can assume that gcd(p,q)=1 WLOG then p does not divide p+q So a| p+q ..a>=p+q. p>=3 as p/q>2 a is min when p+q is min. And b is min when a is is min. I think we only needed to use p=3 and q=1.
By the Euclidean method, we have 1 = 74*16 - 13*91 = 57*13 - 10*74 = 40*10 - 7*57 = 23*7 - 4*40 = 6*4 - 1*23. We have a chain of rational numbers 52/303 < 4/23 < 7/40 < 10/57 < 13/74 < 16/91. 1/6 is inappropriate. Then we have to prove that there is no fractional number a/b such that b < 23, 52/303 < a/b < 4/23. We may prove that easily because 4/23 is very close to 52/303.
Assume that a/b satisfies 52/303 < a/b < 4/23. Then we have 52b < 303a, 23a < 4b. This implies 299a < 52b < 303a. We see that b does not exist when a = 1, 2, 3. So a >= 4 and 23*4 23.
A far faster (but not-so-elegant) solution, would be to find the smallest value of "a", by guess-and-check, starting at a=2. Since the fractions are a bit larger than 1/6, just use b=6a-1. Takes a very short time to reach 4 as the smallest "a", with b=23, which is also, then, the smallest "b". i.e. Values 2/11, and 3/17 don't work, but 4/23 appears with less than a minute's work, and no algebra.
You can directly add 1/4 everywhere after the first reciprocal, And you get: 95/16 < (4b+a)/(4a) < 316/52 Then: you choose (4b+a)/(4a) = 6 and find a/b = 4/23
I take you added 1/4 to the 3 fractions to ensure the 1st one to be strictly smaller than 6, while the 3rd one to be strictly larger, right? Interesting shortcut. However, can this be proven to yield the minimum value of b?
Yeah, I'm confused about this. Why could (b-5a)/(6a-b) not be equal to 7/2, for example? Through some rigorous testing, 23 is indeed the min(b), but that last step feels very strange.
Suppose (b-5a) / (6a-b) = k, where k€Q From this, a/b = (1+k) / (6k+5) ==> a = 1+k and b = 6k+5 Then k = a-1 ==> k is a natural number, given that 'a' is natural and k0.
@@MataMaticas why can we assume a = 1+k and b = 6k+5? how are we allowed to set the numerators and denominators equal to each other? because 3/6 = 4/8 but 3=4 and 6=8 clearly isnt true
letsthinkcritically : please explain why u say that values of 3 and 4 for the ratio will minimise the value of b. This is the most critical logical step, so incumbent upon you to explain it properly before making another video
A proof I’d put on a contest: Farey fractions say that 1/6, 4/23, and 3/17 have no fractions of any smaller denominator between them. But 52/303 is the mediant of 16/96 and 36/207, which are equal to 1/6 and 4/23, and 16/91 is the mediant of 4/23 and 12/68, which are equal to 4/23 and 3/17. So 1/6
52/303 > 52/312, which is 4/24. 16/91 < 16/88, which is 4/22. and we can easily check 4/23 satisfy the condition. and if a < 4 ie. 1 or 2 or 3, can easily check no answer. basically the idea is we see common factors of (52,16) is 4, so try to make both the numerators equal to 4, and then find b between the denominators.
When choosing the integer at the last step, the smallest integer in the interval should always be chosen. This minimises both the numerator and the denominator of the answer
@@stevenwilson5556 We can consider the algorithm in the following equivalent way. To find the minimal fraction in an interval (A to B) subtract the largest integer N smaller than both of these limits then take the reciprocals. This gives us a wider interval (1/(B-N) to 1/(A-N)). This step is repeated until there is an integer in the interval. The minimal fraction in this interval at the last step is the lowest integer in the interval (divided by 1). Now perform each step on this result in reverse, starting with the last step, by taking the reciprocal and adding the integer. This gives the minimal fraction in the interval at each step, because the actions of taking reciprocals and adding integers preserve this property of minimality. Finally we have the minimal fraction in the original interval.
actually it could be much simpler, after reciprocal, considering that the gap is kinda large, just let a = 1, 2, 3, 4, respectively, whatever a that fits in first, that corresponding b will be the ans. In this case, a = 4, so it is not much work tbh
@@田村博志-z8y Never learned Euclidean method just went with the logical that 1/6, which is 2/12 is smaller than 2/11 but thats not in the range 1/6, which is 3/18 is smaller than 3/17 but thats not in the range 1/6, which is 4/24 is smaller than 4/23 which is in the range Now if you think about it at the beginning we chose the closest ratio which 1/6 and went with logical algorithm in which you cannot miss any fractions you can be pretty sure that 4/23 is a fraction with a smallest divider(?).
I did this way: notice that gcd(52, 16) =4. Then 52/303 = 4/23.30 and 16/91=4/22.75. So a/b = 4/23 is a solution. Easy to check no solutions for a=1,2,3.
An easy way is to just let "b" be the sum of the numerators, and "a" be the sum of the denominators. So, let b=91+303=394, and a=16+52=68. Then, b/a=394/68 is between 91/16 and 303/52.
I think the last step should add something like this:
Let (b-5a)/(6a-b) = p/q for some integers p, q with 11/5 < p/q < 43/9, which simplifies to
a/b = (p+q)/(6p+5q)
Now we want to minimize 6p + 5q.
If q = 1, then p = 3 or 4
If q >= 2, then p > 11q/5 >= 22/5, hence p >= 5 which clearly makes 6p+5q larger than the previous case
Hence, we can conclude that q = 1 and p = 3 is the minimum, that is, b = 23
Thanks a lot u cleared my confusion!
Just want to add that b = 6p+5q since gcd(p+q, 6p+5q) = gcd(p+q, p) = gcd(q, p) = 1.
@@wesleydeng71 I actually wrote the exact same comment and then deleted it after thinking.
I think its not necessary that p,q be co-prime
(b-5a)/(6a-b) = p/q is the definition of p,q
But for example, the minimum "b" and corresponding "a" could be such that gcd(b-5a, 6a+b) is not 1
MakST's proof is complete without making the restrictive assumption about gcd(p,q)=1
Thanks bro
Can you please explain why you consider only integer values for (b - 5a)/ (6a -b) ? I am not getting the rationale here. Am I missing out on something critical ?
Suppose (b-5a) / (6a-b) = k, where k€Q
From this, a/b = (1+k) / (6k+5) ==> a = 1+k and b = 6k+5
Then k = a-1 ==> k is a natural number, given that 'a' is natural and k0.
can it be 3.5 also?
Of course maybe simplest to use the integers.
anyway it looks very clever method.
@@MataMaticas why a should be 1+k? If k=p/q, then (1+k)/(6k+5)=(q+p)/(6p+5q)
a could be p+q≠k
@@霍金本人 of course p+q k. In fact, k=p/q
Please consider m/n = 2/3
We are looking for two integers m, n>0, satisfying this equation, so we can state with no error that m=2 and n=3.
On our case, a/b = (1+k) / (6k+5) and we can state with no error that a = 1+k and b= 6k+5 and we find out that k is integer.
If we have (b-5a)/(6a-b)=p/q
b=5a+ a*(p/(q+p))
As we can assume that gcd(p,q)=1 WLOG then p does not divide p+q
So a| p+q ..a>=p+q.
p>=3 as p/q>2
a is min when p+q is min.
And b is min when a is is min.
I think we only needed to use p=3 and q=1.
By the Euclidean method, we have
1 = 74*16 - 13*91
= 57*13 - 10*74
= 40*10 - 7*57
= 23*7 - 4*40
= 6*4 - 1*23.
We have a chain of rational numbers
52/303 < 4/23 < 7/40 < 10/57 < 13/74 < 16/91.
1/6 is inappropriate.
Then we have to prove that there is no fractional number a/b such that
b < 23,
52/303 < a/b < 4/23.
We may prove that easily because 4/23 is very close to 52/303.
Assume that a/b satisfies
52/303 < a/b < 4/23.
Then we have
52b < 303a,
23a < 4b.
This implies
299a < 52b < 303a.
We see that b does not exist when a = 1, 2, 3.
So a >= 4 and
23*4 23.
@@田村博志-z8y neat
This is really nice. I believe this is deeply related to continued fraction expansion of rational numbers ^-^
A far faster (but not-so-elegant) solution, would be to find the smallest value of "a", by guess-and-check, starting at a=2. Since the fractions are a bit larger than 1/6, just use b=6a-1. Takes a very short time to reach 4 as the smallest "a", with b=23, which is also, then, the smallest "b". i.e. Values 2/11, and 3/17 don't work, but 4/23 appears with less than a minute's work, and no algebra.
Fair idea, but what if the smallest b turned out to be 597? That's a lot of "brute force"…
@@stevenwilson5556 Steve - Yeah. If I'd gotten up to about a=6 with no result, I'd probably have given up and tried some more analytical way.
You can directly add 1/4 everywhere after the first reciprocal,
And you get:
95/16 < (4b+a)/(4a) < 316/52
Then: you choose (4b+a)/(4a) = 6 and find a/b = 4/23
I take you added 1/4 to the 3 fractions to ensure the 1st one to be strictly smaller than 6, while the 3rd one to be strictly larger, right? Interesting shortcut.
However, can this be proven to yield the minimum value of b?
Why did we need to choose integer values for the fraction at the end?
Not for a whole fraction, only for denominator. It is written in the problem.
right. i dont get it either
Yeah, I'm confused about this. Why could (b-5a)/(6a-b) not be equal to 7/2, for example? Through some rigorous testing, 23 is indeed the min(b), but that last step feels very strange.
Suppose (b-5a) / (6a-b) = k, where k€Q
From this, a/b = (1+k) / (6k+5) ==> a = 1+k and b = 6k+5
Then k = a-1 ==> k is a natural number, given that 'a' is natural and k0.
@@MataMaticas why can we assume a = 1+k and b = 6k+5? how are we allowed to set the numerators and denominators equal to each other? because 3/6 = 4/8 but 3=4 and 6=8 clearly isnt true
letsthinkcritically : please explain why u say that values of 3 and 4 for the ratio will minimise the value of b.
This is the most critical logical step, so incumbent upon you to explain it properly before making another video
A proof I’d put on a contest: Farey fractions say that 1/6, 4/23, and 3/17 have no fractions of any smaller denominator between them. But 52/303 is the mediant of 16/96 and 36/207, which are equal to 1/6 and 4/23, and 16/91 is the mediant of 4/23 and 12/68, which are equal to 4/23 and 3/17. So 1/6
I love your method for finding the fraction but I don't see how you validated that this is the minimum b.
We ask
\[Alpha]=52/303 and \[Beta]=16/91
The algorithm :
b=1 ;
While[Ceiling[\[Alpha], 1/b] >= \[Beta] && \[Alpha] >= Floor[\[Beta], 1/b], ++b] ;
written in Wolfram-Language
provides
b=23
52/303 > 52/312, which is 4/24. 16/91 < 16/88, which is 4/22. and we can easily check 4/23 satisfy the condition. and if a < 4 ie. 1 or 2 or 3, can easily check no answer.
basically the idea is we see common factors of (52,16) is 4, so try to make both the numerators equal to 4, and then find b between the denominators.
When choosing the integer at the last step, the smallest integer in the interval should always be chosen. This minimises both the numerator and the denominator of the answer
Is there some theorem that backs up this idea? It makes sense but why would that be the case?
@@stevenwilson5556 We can consider the algorithm in the following equivalent way.
To find the minimal fraction in an interval (A to B) subtract the largest integer N smaller than both of these limits then take the reciprocals. This gives us a wider interval (1/(B-N) to 1/(A-N)). This step is repeated until there is an integer in the interval. The minimal fraction in this interval at the last step is the lowest integer in the interval (divided by 1). Now perform each step on this result in reverse, starting with the last step, by taking the reciprocal and adding the integer. This gives the minimal fraction in the interval at each step, because the actions of taking reciprocals and adding integers preserve this property of minimality. Finally we have the minimal fraction in the original interval.
actually it could be much simpler, after reciprocal, considering that the gap is kinda large, just let a = 1, 2, 3, 4, respectively, whatever a that fits in first, that corresponding b will be the ans. In this case, a = 4, so it is not much work tbh
Very nice. Thanks!
5:56 but why?
You can tell 1/6 is closest
to up it a little you go 2/(6*2-1)
then 3/(6*3-1)
and finally 4/(6*4-1) which is 4/23
Nice! You mean
52/303 < n/( 6n - 1 ) < 16/91
Solving n/( 6n - 1 ) < 16/91, we have
91n < 96n - 16
16 < 5n
Then n = 4 is minimum.
@@田村博志-z8y Never learned Euclidean method
just went with the logical that
1/6, which is 2/12 is smaller than 2/11
but thats not in the range
1/6, which is 3/18 is smaller than 3/17
but thats not in the range
1/6, which is 4/24 is smaller than 4/23
which is in the range
Now if you think about it at the beginning we chose the closest ratio which 1/6 and went with logical algorithm in which you cannot miss any fractions you can be pretty sure that 4/23 is a fraction with a smallest divider(?).
@@khamza8926
Good idea, anyway.
It is easy to prove that b = 23 is smallest.
We almost finish this problem when we find 4/23.
@@田村博志-z8y Just saw the edited part. Yeah right, did not see it that way, but I guess it is the same logic.
I did this way: notice that gcd(52, 16) =4. Then 52/303 = 4/23.30 and 16/91=4/22.75. So a/b = 4/23 is a solution. Easy to check no solutions for a=1,2,3.
An easy way is to just let "b" be the sum of the numerators, and "a" be the sum of the denominators. So, let b=91+303=394, and a=16+52=68. Then, b/a=394/68 is between 91/16 and 303/52.
Interrsting div 4 and change a/4 to a, get the answer.quicker
You lost your mojo.
7/40 , 9/52 , 10/57 are 3 more possibilities. 4/23 is the smallest using a C program. So something is not 100% right , I think.
Repeat of another of authors video
This is how I did it-
I took common numerator which is 208/1212 and 208/1183
Then I calculated min of (deno/(hcf(208 and denominator ))) using python