What is the time by now?

43 197 < α β < 17 77 \dfrac{43}{197}<\dfrac{\alpha} {\beta} <\dfrac{17}{77}

Let α \alpha and β \beta be positive integers that satisfy the inequality above. Find the minimum possible value of β \beta .

Image Credit: Flickr Jo


The answer is 32.

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.

5 solutions

Chew-Seong Cheong
Apr 20, 2015

From α β < 17 77 \dfrac{\alpha}{\beta} < \dfrac {17}{77} . We note that α = 17 77 β \alpha = \lfloor \frac {17}{77} \beta \rfloor will satisfy the upper limit condition, when β < 77 \beta < 77 . Our task is the find the β < 77 \beta < 77 such that 17 77 β β > 43 197 \dfrac {\lfloor \frac {17}{77} \beta \rfloor}{\beta} > \dfrac{43}{197} that is satisfying the lower limit condition, 17 77 β > 43 197 β \Rightarrow \lfloor \frac {17}{77} \beta \rfloor > \frac{43}{197} \beta .

Let us now check the minimum β \beta , when 17 77 β = 1 , 2 , 3 , . . . \lfloor \frac {17}{77} \beta \rfloor = 1,2,3,... and check if the condition 17 77 β > 43 197 β \lfloor \frac {17}{77} \beta \rfloor > \frac{43}{197} \beta is met.

\(\begin{array} {} \lfloor \frac {17}{77} \beta \rfloor = 1 & \Rightarrow \beta = 5 & \Rightarrow \frac{43}{197} \beta = 1.091 \color{red}{>} 1 \\ \lfloor \frac {17}{77} \beta \rfloor = 2 & \Rightarrow \beta = 10 & \Rightarrow \frac{43}{197} \beta = 2.182 \color{red}{>} 2 \\ \lfloor \frac {17}{77} \beta \rfloor = 3 & \Rightarrow \beta = 14 & \Rightarrow \frac{43}{197} \beta = 3.055 \color{red}{>} 3 \\ \lfloor \frac {17}{77} \beta \rfloor = 4 & \Rightarrow \beta = 19 & \Rightarrow \frac{43}{197} \beta = 4.147 \color{red}{>} 4 \\ \lfloor \frac {17}{77} \beta \rfloor = 5 & \Rightarrow \beta = 23 & \Rightarrow \frac{43}{197} \beta = 5.020 \color{red}{>} 5 \\ \lfloor \frac {17}{77} \beta \rfloor = 6 & \Rightarrow \beta = 28 & \Rightarrow \frac{43}{197} \beta = 6.111 \color{red}{>} 6 \\ \lfloor \frac {17}{77} \beta \rfloor = 7 & \Rightarrow \beta = 32 & \Rightarrow \frac{43}{197} \beta = 6.984 \color{blue}{<} 7 \end{array} \)

Therefore the minimum possible value of β = 32 \beta = \boxed{32} .

Patrick Corn
Apr 20, 2015

The left continued fraction is [ 0 , 4 , 1 , 1 , 18 / 7 ] [0,4,1,1,18/7 ] . The right continued fraction is [ 0 , 4 , 1 , 1 , 8 ] [0,4,1,1,8] . So the fractions in between it are of the form [ 0 , 4 , 1 , 1 , x ] [0,4,1,1,x] for some x x between 18 / 7 18/7 and 8 8 . That is, we have α β = 2 x + 1 9 x + 5 \frac{\alpha}{\beta} = \frac{2x+1}{9x+5} for some rational x x between 18 / 7 18/7 and 8 8 . (I guess I could have gotten to that last sentence without continued fractions, now that I look at it.)

Let x = p / q x = p/q with p p and q q positive coprime integers. Then β = 9 p + 5 q \beta = 9p + 5q (exercise: 2 p + q 2p+q and 9 p + 5 q 9p+5q are relatively prime!), and this is what we want to minimize. It's clear that p = 3 p =3 , q = 1 q = 1 , β = 32 \beta = 32 is best possible, since for all other p / q > 18 / 7 p/q > 18/7 , p p has to be at least 4 4 and that's already too big.

43B/197 <A<17B/77 So 43B/197 +m/197=17B/77-t/77 Giving 38B=77m +197t 38 divides 77m+197t implies 38 divides m+7t So m+7t =38 and 77m+197t=38B =2926-342t So B=77-9t and as t<or=5 B is min. when t=5 So min. B =32

Des O Carroll - 6 years, 1 month ago

Can you please elaborate "continued fraction " with respect to this problem ? Thanks.

Niranjan Khanderia - 5 years, 11 months ago
Vinod Kumar
Jul 16, 2018

Solve Diophantine equations, 197x-43y>0, 17y-77x>0, using wolfram alpha. You get ( x/y) = (7/32), (9/41), (11/50), (13/59), (15/68), (19/87) and (31/142) as possible pairs. Thus, choosing the lowest pair (7/32) gives answer = 32.

Scrub Lord
Feb 14, 2018

If a, b, c and d are positive and a b < c d \frac{a}{b} < \frac{c}{d} , then a b < a + c b + d < c d \frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d} .

This means that:

43 197 = 43 y 197 y < 43 y + 17 x 197 y + 77 x < 17 x 77 x = 17 77 \frac{43}{197} = \frac{43y}{197y} < \frac{43y + 17x}{197y + 77x} < \frac{17x}{77x} = \frac{17}{77} , where x and y are positive integers.

α β = 43 y + 17 x 197 y + 77 x \frac{\alpha}{\beta} = \frac{43y + 17x}{197y + 77x} WLOG we can assume that gcd ( x , y ) = 1 \gcd(x, y) = 1 .

gcd ( ( 43 y + 17 x ) , ( 197 y + 77 x ) ) = k \gcd((43y + 17x), (197y + 77x)) = k

gcd ( k , x ) = 1 \gcd(k, x) = 1 or gcd ( k , y ) = 1 \gcd(k, y) = 1 or both. If this wasn't true, then k k would have to divide both 17 ( x + y ) 17(x + y) and 77 ( x + y ) 77(x + y) , which means dividing both 77 and 17.

k 43 ( 197 y + 77 x ) 197 ( 43 y + 17 x ) k | 43(197y + 77x) - 197(43y + 17x) and k 17 ( 197 y + 77 x ) 77 ( 43 y + 17 x ) k | 17(197y + 77x) - 77(43y + 17x) , which means k 38 k | 38 .

If we assume k = 38 k = 38 , we must find the smallest possible positive integer pair ( x , y ) (x, y) such that 38 ( 17 x + 43 y ) 38 | (17x + 43y) and 38 ( 77 x + 197 y ) 38 | (77x + 197y) , which is ( 3 , 5 ) (3, 5) .

If we assume k = 19 k = 19 , the smallest possible integer pair that satisfies 19 ( 17 x + 43 y ) 19 | (17x + 43y) and 19 ( 77 x + 197 y ) 19 | (77x + 197y) is ( 2 , 5 ) (2, 5) .

Correct solution (the one which produces smaller β \beta ) is ( x , y ) = ( 3 , 5 ) (x, y) = (3, 5)

a = 43 197 = . 218274 , . . . . b = 17 77 = . 220779 , . . . . . . c = 2 a + b = 4.56 I f α o β < a , a n d α o β + 1 > b T h e n α > α o . M i n β , α a l s o i s m i n . A s s u m e α o , t r y β = α o c . S t a r t w i t h α o = 10 ( S i n c e 17 i s i n b ) α o = 10 , β = 10 c = 45.6 s a y 45 , α o β = . 2222 > b . α o = 8 , β = 8 c = 36.5 s a y 37 , α o β = . 216 < a . α o = 7 , β = 7 c = 31.9 s a y 32 , α o β = . 218756 b e t w e e n a a n d b . v e r y n e a r a a n d l e s s t h a n b . s o t r y β = 33. α o β = . 212121 < a . 32 a g o o d c a n d i d a t e . S e e i f α o = 6 i s p o s s i b l e . α o = 6 , β = 6 c = 27.4 s a y 28 , α o β = . 2214 > b . s o β = 29 g i v e α o β = . 207 < a . N o v a l u e b e t w e e n a a n d b . S o 7 a n d 32 i s m i n i m u m . F o r a n α if there is no value between a and b , go to higher value. I f t h e f i r s t v a l u e w a s 10 45 t a k e n o w K 10 K 45 W h e r e K = 1 , 2 , 3 , 4 , . . . . a=\frac{43}{197}=.218274,....~~b=\frac{17}{77}=.220779,......~~~c=\dfrac{2}{a+b}=4.56\\If~\dfrac{\alpha_o}{\beta}<a,~and~ \dfrac{\alpha_o}{\beta+1}>b~~Then~~\alpha>\alpha_o.~~Min~\beta,~\alpha~also~ is~ min.~\\ Assume~ \alpha_o, ~try~ \beta=\alpha_o*c. ~~~~~~~~Start ~with~\alpha_o=10~(Since~17~is~in~b)\\ \alpha_o=10,~~~\beta=10*c =45.6 ~say~45,~\dfrac{\alpha_o}{\beta}=.2222~~ >~b.\\ \alpha_o=8,~~~\beta=8*c =36.5 ~say~37,~\dfrac{\alpha_o}{\beta}=.216~~ <~a. \\\alpha_o=7,~~~\beta=7*c =31.9 ~say~\color{#D61F06}{32},~\dfrac{\alpha_o}{\beta}=.218756~\color{#3D99F6}{between~a~and~b.} \\~very ~near~a~and~less~than~b.~so~try~\beta=33.\\ \dfrac{\alpha_o}{\beta}=.212121<a. ~32~a~good ~candidate. See~if~\alpha_o=6 ~is~~ possible.\\\alpha_o=6,~~~\beta=6*c =27.4 ~say~28,~\dfrac{\alpha_o}{\beta}=.2214>b.\\so~\beta=29~give~\dfrac{\alpha_o}{\beta}=.207<a.~~No~value~between~a~and~b.\\So~7~and ~32~is~ minimum.\\ For~ an~\alpha~\text{if there is no value between a and b , go to higher value.}\\If~the~first~value~was ~\dfrac{10}{45}~take ~now~\dfrac{K*10}{K*45}~\\Where K=1,2,3,4,....

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...